IQPNNI: Moving fast through tree space and stopping in time
IQPNNI: Moving fast through tree space and stopping in time
复制标题
DOI：
10.1093/molbev/msh176
复制
发表时间：
2004-08-01
影响因子：
10.7
通讯作者：
von Haeseler, A
中科院分区：
文献类型：
--
作者：
Vinh, LS;von Haeseler, A
引入了一种高效的树重建方法（IQPNNI），用于基于DNA或氨基酸序列数据重建系统发育树。我们的方法结合了各种快速算法来生成潜在候选树的列表。关键要素是所谓重要四分体（IQs）的定义，它允许在O(n²)时间内为n个序列计算一棵中间树。然后通过应用最近邻交换（NNI）操作进一步优化所得的树。随后从到目前为止找到的最佳树中删除一部分随机序列。然后使用重要四分体拼图（IQP）算法将删除的序列重新插入到较小的树中。这些步骤重复多次，根据似然准则，最佳的树被视为推断出的系统发育树。此外，我们提出了一个规则，用于指示何时停止搜索。模拟表明，IQPNNI比其他测试程序具有略高的准确性。此外，我们将该方法应用于218个小亚基rRNA序列和500个rbcL序列。我们发现与其他人的结果相比，这些树具有更高的似然性。一个用于重建基于DNA或氨基酸的系统发育树的程序可在网上获取（http://www.bi.uni - duesseldorf.de/software/iqpnni）。
An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast algorithms to generate a list of potential candidate trees. The key ingredient is the definition of so-called important quartets (IQs), which allow the computation of an intermediate tree in O(n(2)) time for n sequences. The resulting tree is then further optimized by applying the nearest neighbor interchange (NNI) operation. Subsequently a random fraction of the sequences is deleted from the best tree found so far. The deleted sequences are then re-inserted in the smaller tree using the important quartet puzzling (IQP) algorithm. These steps are repeated several times and the best tree, with respect to the likelihood criterion, is considered as the inferred phylogenetic tree. Moreover, we suggest a rule which indicates when to stop the search. Simulations show that IQPNNI gives a slightly better accuracy than other programs tested. Moreover, we applied the approach to 218 small subunit rRNA sequences and 500 rbcL sequences. We found trees with higher likelihood compared to the results by others. A program to reconstruct DNA or amino acid based phylogenetic trees is available online (http://www.bi.uni-duesseldorf.de/software/iqpnni).