BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data
BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data
复制标题
DOI：
10.1093/oxfordjournals.molbev.a025808
复制
发表时间：
1997-07-01
影响因子：
10.7
通讯作者：
Gascuel, O
中科院分区：
文献类型：
--
作者：
Gascuel, O
我们提出了一个改进的版本的邻居加入（NJ）算法的Saitou和Nei。这种新算法BIONJ遵循与NJ相同的凝聚方案，其包括迭代地挑选一对分类群，创建代表这些分类群的新节点，并通过用该节点替换两个分类群来减少距离矩阵。此外，BIONJ使用一个简单的一阶模型的方差和协方差的进化距离估计。当从比对序列获得这些估计时，该模型很好地适应。在每一步，它允许选择，从类的可接受的减少，减少最小化新的距离矩阵的方差。通过这种方式，我们获得了更好的估计，以选择在接下来的步骤中要聚集的类群对。此外，与NJ的估计相比，这些估计随着算法的进行而变得越来越好。BIONJ保留了NJ的优良特性，特别是其低运行时间。计算机模拟已经进行了12分类模型树，以确定BIONJ的效率。当替换率低时（最大成对差异接近每个位点0.1个替换）或当它们在谱系之间恒定时，BIONJ仅略优于NJ。当替代率较高并且在谱系之间变化时，BIONJ显然具有更好的拓扑准确性。在后一种情况下，对于模型树和测试的进化条件，拓扑错误减少平均约20%。对于高变化率的树和高替换率（最大成对发散近似于每个位点1.0个替换），错误减少甚至可以上升到50%以上，而找到正确树的概率可以增加多达15%。
We propose an improved version of the neighbor-joining (NJ) algorithm of Saitou and Nei. This new algorithm, BIONJ, follows the same agglomerative scheme as NJ, which consists of iteratively picking a pair of taxa, creating a new node which represents the cluster of these taxa, and reducing the distance matrix by replacing both taxa by this node. Moreover, BIONJ uses a simple first-order model of the variances and covariances of evolutionary distance estimates. This model is well adapted when these estimates are obtained from aligned sequences. At each step it permits the selection, from the class of admissible reductions, of the reduction which minimizes the variance of the new distance matrix. In this way, we obtain better estimates to choose the pair of taxa to be agglomerated during the next steps. Moreover, in comparison with NJ's estimates, these estimates become better and better as the algorithm proceeds. BIONJ retains the good properties of NJ-especially its low run time. Computer simulations have been performed with 12-taxon model trees to determine BIONJ's efficiency. When the substitution rates are low (maximum pairwise divergence approximate to 0.1 substitutions per site) or when they are constant among lineages, BIONJ is only slightly better than NJ. When the substitution rates are higher and vary among lineages, BIONJ clearly has better topological accuracy. In the latter case, for the model trees and the conditions of evolution tested, the topological error reduction is on the average around 20%. With highly-varying-rate trees and with high substitution rates (maximum pairwise divergence approximate to 1.0 substitutions per site), the error reduction may even rise above 50%, while the probability of finding the correct tree may be augmented by as much as 15%.