Fast computation of distance estimators.

Full Abstract

BACKGROUND:
Some distance methods are among the most commonly used methods for reconstructing phylogenetic trees from sequence data. The input to a distance method is a distance matrix, containing estimated pairwise distances between all pairs of taxa. Distance methods themselves are often fast, e.g., the famous and popular Neighbor Joining (NJ) algorithm reconstructs a phylogeny of n taxa in time O(n3). Unfortunately, the fastest practical algorithms known for Computing the distance matrix, from n sequences of length l, takes time proportional to l.n2. Since the sequence length typically is much larger than the number of taxa, the distance estimation is the bottleneck in phylogeny reconstruction. This bottleneck is especially apparent in reconstruction of large phylogenies or in applications where many trees have to be reconstructed, e.g., bootstrapping and genome wide applications.

RESULTS:
We give an advanced algorithm for Computing the number of mutational events between DNA sequences which is significantly faster than both Phylip and Paup. Moreover, we give a new method for estimating pairwise distances between sequences which contain ambiguity Symbols. This new method is shown to be more accurate as well as faster than earlier methods.

CONCLUSION:
Our novel algorithm for Computing distance estimators provides a valuable tool in phylogeny reconstruction. Since the running time of our distance estimation algorithm is comparable to that of most distance methods, the previous bottleneck is removed. All distance methods, such as NJ, require a distance matrix as input and, hence, our novel algorithm significantly improves the overall running time of all distance methods. In particular, we show for real world biological applications how the running time of phylogeny reconstruction using NJ is improved from a matter of hours to a matter of seconds.

Learn Faster Today Improve your study skills

Author information

Author/s: Elias, Isaac (I); Lagergren, Jens (J);

Affiliation: Dept. of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, SE-106 91, Sweden. isaac(-atsign-)csc.kth.se

Journal and publication information

Publication Type: Comparative Study; Evaluation Studies; Journal Article

Journal: BMC bioinformatics (BMC Bioinformatics), published in England. (Language: eng)

Reference: 2007-; vol 8 (issue ) : pp 89

Dates: Created 2007/03/26; Completed 2007/04/25; Revised 2008/11/20;

PMID: 17355623, status: MEDLINE (last retrieval date: 12/26/2008)

Sourced from the National Library of Medicine. Abstract text and other information may be subject to copyright.

External Links for this article (including full text providers, if available):

Click Electronic Full-text Provider Links to see options for finding the electronic full text links to this article. Note there may be a subscription or fee required for access to the full text. See our FAQ for information on finding FREE full text articles.

This article may also be located in paper journal collections available in many libraries. Use the Journal and Publication Information above to find the full article.

MeSH headings (categories)

This article was linked to the MESH Headings shown below.

Algorithms
Animals
Computational Biology - methods
DNA Mutational Analysis - methods

These are the highest related articles currently in the database:

See 100+ related articles.