Fast computation of distance estimators
Fast computation of distance estimators
复制标题
DOI：
10.1186/1471-2105-8-89
复制
发表时间：
2007-03-13
影响因子：
3
通讯作者：
Lagergren, Jens
中科院分区：
文献类型：
--
作者：
Elias, Isaac;Lagergren, Jens
背景：一些距离方法是从序列数据重建系统发育树最常用的方法之一。距离方法的输入是一个距离矩阵，其中包含所有分类群对之间的估计成对距离。距离方法本身通常速度很快，例如，著名且流行的邻接法（NJ）算法在O(n³)时间内重建n个分类群的系统发育树。不幸的是，已知的从n个长度为l的序列计算距离矩阵的最快实用算法，其时间与l·n²成正比。由于序列长度通常比分类群的数量大得多，距离估计是系统发育重建的瓶颈。在大型系统发育树的重建中，或者在许多树需要被重建的应用中，例如自举法和全基因组应用中，这个瓶颈尤其明显。
结果：我们给出了一种先进的算法，用于计算DNA序列之间的突变事件数量，它比Phylip和Paup都要快得多。此外，我们给出了一种新的方法，用于估计包含模糊符号的序列之间的成对距离。这种新方法被证明比早期的方法更准确且更快。
结论：我们用于计算距离估计量的新算法为系统发育重建提供了一个有价值的工具。由于我们的距离估计算法的运行时间与大多数距离方法相当，之前的瓶颈被消除了。所有的距离方法，如NJ，都需要一个距离矩阵作为输入，因此，我们的新算法显著提高了所有距离方法的总体运行时间。特别是，我们针对现实世界的生物学应用展示了使用NJ进行系统发育重建的运行时间如何从数小时提高到数秒。
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(.)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.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.