Evolutionary tree reconstruction is notoriously difficult because the number of potential solutions increases explosively with the number of analysed species/sequences. Indeed, there are nearly 32 billion different possible tree topologies among just 14 species/sequences… and about 3 x 1084 trees (i.e., more than the number of atoms in the universe) for 55 species/sequences. This makes the task of phylogeneticists very difficult especially since major advances in molecular biology and biotechnology have caused a dramatic increase in the number of DNA sequences available. Hence, much of the current research in phyloinformatics (i.e., computational phylogenetics) concentrates on the development of more efficient heuristic approaches, i.e., algorithms that yield optimal or near-optimal solutions with high probability… and in practical computing times.
MetaPIGA2 implements the metaGA (metapopulation Genetic Algorithm)
We report here on the release of the software metaPIGA2, integrating the ‘metaGA’ algorithm that implements a set of operators mimicking processes of biological evolution such as mutation, recombination, selection, and reproduction. Here, evolving “individuals” are tree topologies and model parameters that need to be optimized. A mutation is a stochastic alteration of one component of the individual, and the fitness of an individual is a function of the Likelihood (a mathematical function) for that tree. Because of selection, the mean score of the population of trees improves over time, i.e., across iterations in the computer.
MetaPIGA2 vastly improves the speed and efficiency with which trees are found such that hundreds or thousands of sequences/species can be analyzed in practical computing times. The essence of the procedure relies on the cooperation among the populations of trees to search for the optimal tree.
- MetaPIGA2 is described in:
Helaers R. & M.C. Milinkovitch
MetaPIGA v2.0: maximum likelihood large phylogeny estimation using the metapopulation genetic algorithm and other stochastic heuristics
BMC Bioinformatics 2010, 11: 379
- The software and its manual are freely available at www.metapiga.org.
- The metaGA algorithm is described in:
Lemmon A. R. & M. C. Milinkovitch
The metapopulation genetic algorithm: an efficient solution for the problem of large phylogeny estimation
PNAS, 99: 10516-10521 (2002)