Phylogeny Methods: Artificial Intelligence and Genetic Algorithms

Team Members

Ralph Mills

Abstract

The goal of this project is to survey methods that estimate phylogeny. One is an artificial intelligence-based program that simulates natural selection to choose among phylogenies. The other two programs use genetic algorithms, one involving metapopulations and the other a heuristic search under the General Time Reversible (GTR) model. The execution time and validity of the results will be checked against a more traditional algorithm for finding maximum likelihood phylogenies.

Project Plan

I plan to create several test cases of protein sequence data, each containing a different combination of species from the link below. The data will need to be converted to suit each program (i.e. GARLI uses sequences of the PHYLIP format). The experiments will consist of running each program against the test cases and measuring the execution time. The similarity and accuracy of the results, as well as the relative performance of each program, will be compared against that of a traditional algorithm.

Program Links:

PTP (Phylogenetic Tree Project) FTP Download
MetaPIGA (Phylogeny Inference using the MetaGA) Website
GARLI (Genetic Algorithm for Rapid Likelihood Inference) Website

Data Links:

Ensembl project Download Page

References

Lemmon, A.R. and M.C. Milinkovitch. 2002. The metapopulation genetic algorithm: An efficient solution for the problem of large phylogeny estimation. Proceedings of the National Academy of Sciences, USA 99: 10516-10521.
Zwickl, D.J. 2006. Genetic algorithm approaches for the phylogenetic analysis of large biological sequence datasets under the maximum likelihood criterion. Ph.D. dissertation, The University of Texas at Austin.