Molecular Biology and Evolution, Vol 15, 277-283, Copyright © 1998 by Society for Molecular Biology and Evolution
PO Lewis
Phylogeny reconstruction is a difficult computational problem, because the
number of possible solutions increases with the number of included taxa.
For example, for only 14 taxa, there are more than seven trillion possible
unrooted phylogenetic trees. For this reason, phylogenetic inference
methods commonly use clustering algorithms (e.g., the neighbor-joining
method) or heuristic search strategies to minimize the amount of time spent
evaluating nonoptimal trees. Even heuristic searches can be painfully slow,
especially when computationally intensive optimality criteria such as
maximum likelihood are used. I describe here a different approach to
heuristic searching (using a genetic algorithm) that can tremendously
reduce the time required for maximum-likelihood phylogenetic inference,
especially for data sets involving large numbers of taxa. Genetic
algorithms are simulations of natural selection in which individuals are
encoded solutions to the problem of interest. Here, labeled phylogenetic
trees are the individuals, and differential reproduction is effected by
allowing the number of offspring produced by each individual to be
proportional to that individual's rank likelihood score. Natural selection
increases the average likelihood in the evolving population of phylogenetic
trees, and the genetic algorithm is allowed to proceed until the likelihood
of the best individual ceases to improve over time. An example is presented
involving rbcL sequence data for 55 taxa of green plants. The genetic
algorithm described here required only 6% of the computational effort
required by a conventional heuristic search using tree
bisection/reconnection (TBR) branch swapping to obtain the same
maximum-likelihood topology.
ORIGINAL ARTICLE
A genetic algorithm for maximum-likelihood phylogeny inference using nucleotide sequence data
Department of Biology, University of New Mexico, Albuquerque 87131- 1091, USA. lewisp@unm.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  G. B. Fogel Computational intelligence approaches for pattern discovery in biological systems Brief Bioinform, July 1, 2008; 9(4): 307 - 316. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Zhao, F. Zhao, T. Li, and D. A. Bryant A new pheromone trail-based genetic algorithm for comparative genome assembly Nucleic Acids Res., June 1, 2008; 36(10): 3455 - 3462. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. Yuri, R. T. Kimball, E. L. Braun, and M. J. Braun Duplication of Accelerated Evolution and Growth Hormone Gene in Passerine Birds Mol. Biol. Evol., February 1, 2008; 25(2): 352 - 361. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. A. Morrison Increasing the Efficiency of Searches for the Maximum Likelihood Tree in a Phylogenetic Analysis of up to 150 Nucleotide Sequences Syst Biol, December 1, 2007; 56(6): 988 - 1010. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Whelan New Approaches to Phylogenetic Tree Search and Their Application to Large Numbers of Protein Alignments Syst Biol, October 1, 2007; 56(5): 727 - 740. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 W. Hordijk and O. Gascuel Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood Bioinformatics, December 15, 2005; 21(24): 4338 - 4347. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Guindon, F. Lethiec, P. Duroux, and O. Gascuel PHYML Online--a web server for fast maximum likelihood-based phylogenetic inference Nucleic Acids Res., July 1, 2005; 33(suppl_2): W557 - W559. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. M. Jarvis and R. Goodacre Genetic algorithm optimization for pre-processing and variable selection of spectroscopic data Bioinformatics, April 1, 2005; 21(7): 860 - 868. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. L. K. Pond and S. D. W. Frost A Genetic Algorithm Approach to Detecting Lineage-Specific Variation in Selection Pressure Mol. Biol. Evol., March 1, 2005; 22(3): 478 - 485. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Stamatakis, T. Ludwig, and H. Meier RAxML-III: a fast program for maximum likelihood-based inference of large phylogenetic trees Bioinformatics, February 15, 2005; 21(4): 456 - 463. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. J. Brauer, M. T. Holder, L. A. Dries, D. J. Zwickl, P. O. Lewis, and D. M. Hillis Genetic Algorithms and Parallel Processing in Maximum-Likelihood Phylogeny Inference Mol. Biol. Evol., October 1, 2002; 19(10): 1717 - 1726. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. R. Lemmon and M. C. Milinkovitch The metapopulation genetic algorithm: An efficient solution for the problem of large phylogeny estimation PNAS, August 6, 2002; 99(16): 10516 - 10521. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Posada and K. A. Crandall Simple (Wrong) Models for Complex Trees: A Case from Retroviridae Mol. Biol. Evol., February 1, 2001; 18(2): 271 - 275. [Full Text]
|
|
|
|
|
|
D. D. Pollock, J. A. Eisen, N. A. Doggett, and M. P. Cummings A Case for Evolutionary Genomics and the Comprehensive Examination of Sequence Biodiversity Mol. Biol. Evol., December 1, 2000; 17(12): 1776 - 1788. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. W. Diaconis and S. P. Holmes Matchings and phylogenetic trees PNAS, December 8, 1998; 95(25): 14600 - 14602. [Abstract] [Full Text] [PDF]
|
|