main page

    Fast Computation of Distance Estimators

    Isaac Elias and Jens Lagergren

    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(n^3)$. Unfortunately, the fastest practical algorithms known for computing the distance matrix, from $n$ sequences of length $l$, takes time proportional to $l\cdot n^2$. 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.

    Conclusions: 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.

    Download Supplementary Material

    Supplementary Material - Fast Computation of Distance Estimators
    Contains additional figures for the tests run on the ambiguity approaches.
    (PDF)

    Simulated Test Data for Ambiguities
    (Tar archive)

    Biological Test Data
    (Tar archive)

    Command file used for running Paup
    (Nexus file)

    Download Source Code

    Download from fastphylo at Source forge.

    BibTex 

    @Article{EliasLagergren_fastdist
  author =      {Isaac Elias and Jens Lagergren},
  title =	{Fast Computation of Distance Estimators},
  journal =	{BMC Bioinformatics},
  year =        {2007},
  pages =       {89},
  volume =      {8}
}