PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences
PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences
复制标题
DOI：
10.1093/bioinformatics/btl592
复制
发表时间：
2007-02-01
期刊：
影响因子：
5.8
通讯作者：
Toh, Hiroyuki
中科院分区：
文献类型：
--
作者：
Katoh, Kazutaka;Toh, Hiroyuki
动机：为了构建大量的多序列比对（MSA），在序列数大于10000的情况下，计算引导树的复杂度为O（N-2）到O（N-3），其中N为序列数。为了克服这个限制，我们开发了一个近似算法，PartTree，一个时间复杂度为O（N log N）的引导树。新的MSA方法与PartTree算法可以在几分钟内在标准台式计算机上比对类似的60000个序列。可用性：本算法已经在MAFFT序列比对包（http：//align.bmr.kyushu-u.ac. jp/mafft/software/）。联系方式：katoh@ biorg.kyushu-u.ac. jp补充信息：补充信息可在Bioinformatics online获得。
Motivation: To construct a multiple sequence alignment (MSA) of a large number (>similar to 10 000) of sequences, the calculation of a guide tree with a complexity of O(N-2) to O(N-3), where N is the number of sequences, is the most time-consuming process.Results: To overcome this limitation, we have developed an approximate algorithm, PartTree, to construct a guide tree with an average time complexity of O( N log N). The new MSA method with the PartTree algorithm can align similar to 60 000 sequences in several minutes on a standard desktop computer. The loss of accuracy in MSA caused by this approximation was estimated to be several percent in benchmark tests using Pfam.Availability: The present algorithm has been implemented in the MAFFT sequence alignment package (http://align.bmr.kyushu-u.ac. jp/mafft/software/).Contact: katoh@ bioreg.kyushu-u.ac.jpSupplementary information: Supplementary information is available at Bioinformatics online.