Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins.
Inferring phylogeny is a difficult computational problem. For example, for only 13 taxa, there are more then 13 billion possible unrooted phylogenetic trees. Heuristics are necessary to minimize the time spent evaluating non-optimal trees. We describe here an approach for heuristic searching, using a genetic algorithm, that can reduce the time required for weighted maximum parsimony phylogenetic inference, especially for data sets involving a large number of taxa. It is the first implementation of a weighted maximum parsimony criterion using amino acid sequences. To validate the weighted criterion, we used an artificial data set and compared it to a number of other phylogenetic methods. Genetic algorithms mimic the natural selection's ability to solve complex problems. We have identified several parameters affecting the genetic algorithm. Methods were developed to validate these parameters, ensuring optimal performance. This approach allows the construction of phylogenetic trees with over 200 taxa in practical time on a regular PC.
Department of Neuroscience, Pharmacology, Biomedical Center, 75 124 Uppsala, Sweden.
Tobias
T
Hill
Andor
A
Lundgren
Robert
R
Fredriksson
Helgi B
HB
Schiöth
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D016013:Likelihood Functions; D010802:Phylogeny; D011506:Proteins / Q000235:genetics*; D012984:Software
D011506:Proteins