© 2004 Society of Systematic Biologists
Column Sorting: Rapid Calculation of the Phylogenetic Likelihood Function
1 Department of Mathematics, University of Arizona Tucson Arizona 85721, USA
2 Bioinformatics Research Center and Department of Statistics, North Carolina State University Raleigh North Carolina 27695–7566, USA; E-mail: muse{at}stat.ncsu.edu
Edited by John Huelsenbeck: Associate Editor
 |
Abstract |
|---|
Likelihood applications have become a central approach for molecular evolutionary analyses since the first computationally tractable treatment two decades ago. Although Felsenstein's original pruning algorithm makes likelihood calculations feasible, it is usually possible to take advantage of repetitive structure present in the data to arrive at even greater computational reductions. In particular, alignment columns with certain similarities have components of the likelihood calculation that are identical and need not be recomputed if columns are evaluated in an optimal order. We develop an algorithm for exploiting this speed improvement via an application of graph theory. The reductions provided by the method depend on both the tree and the data, but typical savings range between 15% and 50%. Real-data examples with time reductions of 80% have been identified. The overhead costs associated with implementing the algorithm are minimal, and they are recovered in all but the smallest data sets. The modifications will provide faster likelihood algorithms, which will allow likelihood methods to be applied to larger sets of taxa and to include more thorough searches of the tree topology space.
Keywords: DNA sequence; graph theory; likelihood; phylogeny; traveling salesman problem
Received October 24, 2002; Revised April 21, 2003; Accepted April 5, 2004
3 Current Address: Antiviral Research Center, University of California San Diego, California, USA
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  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]
|
|