Taxon ordering in phylogenetic trees by means of evolutionary algorithms

Starting from a West Nile virus phylogenetic tree, in a (1 + 1)-EA we evolved it by randomly rotating the internal nodes and selecting the tree with better fitness every generation. The fitness is a sum of genetic distances between the considered taxon and the r (radius) next taxa. After having set the radius to the best performance, we evolved the trees with (λ + μ)-EAs to study the influence of population on the algorithm.The (1 + 1)-EA consistently outperformed a random search, and better results were obtained setting the radius to 8. The (λ + μ)-EAs performed as well as the (1 + 1), except the larger population (1000 + 1000).The trees after the evolution showed an improvement both of the fitness (based on a genetic distance matrix, then close taxa are actually genetically close), and of the biological interpretation. Samples collected in the same state or year moved close each other, making the tree easier to interpret. Biological relationships between samples are also easier to observe.A central goal of evolutionary biology is to describe the "Tree of Life", inferring relationships among all living organisms. First appeared in the XIX century, trees were often used to describe relationships among organisms, but only Charles Darwin, in his revolutionary Origin of the Species [1], was the first to define them as evolutionary trees. Instead of using phenotypic characters, as Darwin did first, nowadays such trees are commonly built on genetic information and models of molecular evolution.A phylogenetic tree is a mathematical structure to represent the evolutionary history of sequences or individuals. It consists of nodes connected by branches (or edges). The terminal nodes represent the "leaves" of the tree (or tips of the branches) and are also called taxa. Internal nodes represent ancestors, and can be connected to many branches; in this case the node is a politomy and represents either simultaneous divergence of descendants (hard politomy) or uncertainty about t