Limits...
Taxon ordering in phylogenetic trees by means of evolutionary algorithms.

Cerutti F, Bertolotti L, Goldberg TL, Giacobini M - BioData Min (2011)

Bottom Line: 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).Biological relationships between samples are also easier to observe.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Animal Production, Epidemiology and Ecology, Faculty of Veterinary Medicine, University of Torino, Via Leonardo da Vinci 44, 10095, Grugliasco (TO), Italy. mario.giacobini@unito.it.

ABSTRACT

Background: In in a typical "left-to-right" phylogenetic tree, the vertical order of taxa is meaningless, as only the branch path between them reflects their degree of similarity. To make unresolved trees more informative, here we propose an innovative Evolutionary Algorithm (EA) method to search the best graphical representation of unresolved trees, in order to give a biological meaning to the vertical order of taxa.

Methods: 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.

Results: 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).

Conclusions: 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.

No MeSH data available.


Related in: MedlinePlus

WNV original tree. WNV phylogenetic tree obtained by the Bayesian approach within MrBayes software and used as starting tree for all the algorithms performed in this work [12].
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3142222&req=5

Figure 1: WNV original tree. WNV phylogenetic tree obtained by the Bayesian approach within MrBayes software and used as starting tree for all the algorithms performed in this work [12].

Mentions: 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 the phylogenetic relationship (soft politomy) [2,3]. Trees with many politomies are called unresolved trees, as they do not resolve the full history of evolution that they represent. The order in which the labels of the tips are drawn can differ without changing the meaning of the tree itself. This because in a tree the branches can be freely rotated without modifying the relationship among taxa [4,5]. The so called additive trees have branches containing information about the degree of difference between nodes, and they are used to show evolutionary features. In this case, information in the tree is contained in the branch direction, in the pattern of linkages between branches and nodes or, in other words, in its topology. Indeed in the representation commonly used by phylogenetic softwares, with the root on the left and the tips on the right (Figure 1), the order of taxa is meaningless, and the degree of similarity between taxa is only reflected by the branch path between them [5,6]. A second important feature of phylogenetic trees is the node's degree: in a fully resolved tree, all internal nodes have a degree equal to three, but, because of polytomies, trees may be hard to interpret and then being misinterpreted, assigning unfounded meaning to the proximity of taxa or clades. If the order of taxa on phylogenetic trees is flexible, ascribing biological meaning to it without altering the topology is possible [2,5].


Taxon ordering in phylogenetic trees by means of evolutionary algorithms.

Cerutti F, Bertolotti L, Goldberg TL, Giacobini M - BioData Min (2011)

WNV original tree. WNV phylogenetic tree obtained by the Bayesian approach within MrBayes software and used as starting tree for all the algorithms performed in this work [12].
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3142222&req=5

Figure 1: WNV original tree. WNV phylogenetic tree obtained by the Bayesian approach within MrBayes software and used as starting tree for all the algorithms performed in this work [12].
Mentions: 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 the phylogenetic relationship (soft politomy) [2,3]. Trees with many politomies are called unresolved trees, as they do not resolve the full history of evolution that they represent. The order in which the labels of the tips are drawn can differ without changing the meaning of the tree itself. This because in a tree the branches can be freely rotated without modifying the relationship among taxa [4,5]. The so called additive trees have branches containing information about the degree of difference between nodes, and they are used to show evolutionary features. In this case, information in the tree is contained in the branch direction, in the pattern of linkages between branches and nodes or, in other words, in its topology. Indeed in the representation commonly used by phylogenetic softwares, with the root on the left and the tips on the right (Figure 1), the order of taxa is meaningless, and the degree of similarity between taxa is only reflected by the branch path between them [5,6]. A second important feature of phylogenetic trees is the node's degree: in a fully resolved tree, all internal nodes have a degree equal to three, but, because of polytomies, trees may be hard to interpret and then being misinterpreted, assigning unfounded meaning to the proximity of taxa or clades. If the order of taxa on phylogenetic trees is flexible, ascribing biological meaning to it without altering the topology is possible [2,5].

Bottom Line: 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).Biological relationships between samples are also easier to observe.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Animal Production, Epidemiology and Ecology, Faculty of Veterinary Medicine, University of Torino, Via Leonardo da Vinci 44, 10095, Grugliasco (TO), Italy. mario.giacobini@unito.it.

ABSTRACT

Background: In in a typical "left-to-right" phylogenetic tree, the vertical order of taxa is meaningless, as only the branch path between them reflects their degree of similarity. To make unresolved trees more informative, here we propose an innovative Evolutionary Algorithm (EA) method to search the best graphical representation of unresolved trees, in order to give a biological meaning to the vertical order of taxa.

Methods: 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.

Results: 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).

Conclusions: 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.

No MeSH data available.


Related in: MedlinePlus