Ant-Based Phylogenetic Reconstruction (ABPR): A new distance algorithm for phylogenetic estimation based on ant colony optimization
AUTOR(ES)
Vittori, Karla, Delbem, Alexandre C.B., Pereira, Sérgio L.
FONTE
Genetics and Molecular Biology
DATA DE PUBLICAÇÃO
2008-12
RESUMO
We propose a new distance algorithm for phylogenetic estimation based on Ant Colony Optimization (ACO), named Ant-Based Phylogenetic Reconstruction (ABPR). ABPR joins two taxa iteratively based on evolutionary distance among sequences, while also accounting for the quality of the phylogenetic tree built according to the total length of the tree. Similar to optimization algorithms for phylogenetic estimation, the algorithm allows exploration of a larger set of nearly optimal solutions. We applied the algorithm to four empirical data sets of mitochondrial DNA ranging from 12 to 186 sequences, and from 898 to 16,608 base pairs, and covering taxonomic levels from populations to orders. We show that ABPR performs better than the commonly used Neighbor-Joining algorithm, except when sequences are too closely related (e.g., population-level sequences). The phylogenetic relationships recovered at and above species level by ABPR agree with conventional views. However, like other algorithms of phylogenetic estimation, the proposed algorithm failed to recover expected relationships when distances are too similar or when rates of evolution are very variable, leading to the problem of long-branch attraction. ABPR, as well as other ACO-based algorithms, is emerging as a fast and accurate alternative method of phylogenetic estimation for large data sets.
Documentos Relacionados
- An ant colony algorithm applied to lay-up optimization of laminated composite plates
- CVTree: a phylogenetic tree reconstruction tool based on whole genomes
- Maximization of Fundamental Frequency of Laminated Composite Cylindrical Shells by Ant Colony Algorithm
- An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem
- A new probabilistic public key algorithm based on elliptic logarithms