The average common substring approach to phylogenomic reconstruction
The average common substring approach to phylogenomic reconstruction
复制标题
DOI：
10.1089/cmb.2006.13.336
复制
发表时间：
2006-03-01
影响因子：
1.7
通讯作者：
Chor, B
中科院分区：
文献类型：
--
作者：
Ulitsky, I;Burstein, D;Chor, B
我们描述了一种新的方法，有效地重建系统发育树，基于整个基因组或蛋白质组的序列，其长度可能会有很大的变化。我们的方法的核心是一个新的衡量序列之间的成对距离。这种度量是基于计算最大公共子串的平均长度，这与信息理论工具（Kullback-Leibler相对熵）有本质的联系。我们提出了一个算法，有效地计算这些距离。一般来说，两个l长序列的距离可以在O（l）时间内计算。我们使用后缀数组实现了该算法，我们的实现速度足够快，可以构建数百个物种的蛋白质组系统基因组树和近两千种病毒的基因组系统基因组森林。对结果的初步分析显示出与“可接受的系统发育和分类学事实”的惊人一致。“为了评估我们的方法，我们的结果与传统的（单基因或基于蛋白质的）最大似然方法进行了比较。所获得的树进行了比较，实现了一些替代方法，包括两个以前发表在文献中，并公布的结果的第三种方法。比较他们的结果和运行时间，我们的，使用一个“传统”的树和一个标准的树比较方法，我们的算法改进了“竞争”的大幅利润。我们的方法的简单性和速度允许全基因组分析与迄今为止尝试的最大范围。我们在这里描述了五种不同的应用程序的方法，这不仅表明了该方法的有效性，但也提出了一些新的系统发育的见解。
We describe a novel method for efficient reconstruction of phylogenetic trees, based on sequences of whole genomes or proteomes, whose lengths may greatly vary. The core of our method is a new measure of pairwise distances between sequences. This measure is based on computing the average lengths of maximum common substrings, which is intrinsically related to information theoretic tools (Kullback-Leibler relative entropy). We present an algorithm for efficiently computing these distances. In principle, the distance of two l long sequences can be calculated in O(l) time. We implemented the algorithm using suffix arrays our implementation is fast enough to enable the construction of the proteome phylogenomic tree for hundreds of species and the genome phylogenomic forest for almost two thousand viruses. An initial analysis of the results exhibits a remarkable agreement with "acceptable phylogenetic and taxonomic truth." To assess our approach, our results were compared to the traditional (single-gene or protein-based) maximum likelihood method. The obtained trees were compared to implementations of a number of alternative approaches, including two that were previously published in the literature, and to the published results of a third approach. Comparing their outcome and running time to ours, using a "traditional" trees and a standard tree comparison method, our algorithm improved upon the "competition" by a substantial margin. The simplicity and speed of our method allows for a whole genome analysis with the greatest scope attempted so far. We describe here five different applications of the method, which not only show the validity of the method, but also suggest a number of novel phylogenetic insights.