PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences

By Kazutaka Katoh, Hiroyuki Toh. 2007

126 citations recorded by the source corpus.

MOTIVATION To construct a multiple sequence alignment (MSA) of a large number (> approximately 10,000) of sequences, the calculation of a guide tree with a complexity of O(N2) to O(N3), 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 approximately 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/). SUPPLEMENTARY INFORMATION Supplementary information is available at Bioinformatics online.

Subfields: Artificial Intelligence, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

MAFFT Multiple Sequence Alignment Software Version 7: Improvements in Performance and Usability (2013, methodology): “The application of a computationally expensive method based on L-INS-1 ( ––localpair ––add ) has no advantage, because the extra computational time is spent on the comparison of nonoverlapping fragmentary sequences, which have no reasonable solutions.”
Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega (2011, background): “…Citation: Molecular Systems Biology 7: 539 & 2011 EMBO and Macmillan Publishers Limited All rights reserved 1744-4292/11 www.molecularsystemsbiology.com & 2011 EMBO and Macmillan Publishers Limited Molecular Systems Biology 2011 1 about 10 000 sequences is MAFFT/PartTree (Katoh and Toh, 2007).”
MAFFT online service: multiple sequence alignment, interactive sequence choice and visualization (2017, methodology): “PartTree and DPPartTree (Figure 1A) [6] are highly approximate options.”
Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features (2008, methodology): “Out of the alignment programs tested, Kalign2 was almost as fast as the speed oriented methods like the PartTree option of MAFFT (32) or the fast mode of Muscle (26), but significantly faster than the rest of the methods tested (Figure 1A–C).”
FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments (2010, methodology): “To improve scalability further, it might be possible to use a divide-and-conquer method to find clusters of closely related sequences in O(N log Nð ÞL) time, as in PartTree [30].”
SATe-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees. (2012, methodology): “Due to the high number of taxa in the 16S.T and 16S.B.ALL data sets, we used the PartTree (Katoh and Toh 2007) algorithm in MAFFT and the Quicktree (Thompson et al. 1994) option in ClustalW to estimate multiple sequence alignments and RAxML to estimate ML trees on each alignment.”
Recent developments in the MAFFT multiple sequence alignment program (2008, methodology): “MAFFT Version 6 has two major new features, the PartTree algorithm for handling a large number ( > (cid:1) 10 000) of sequences and the Four-way Consistency objective function for multiple structural alignmentof ncRNAs.”
FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix (2009, methodology): “For example, PartTree ( Katoh and Toh, 2007 ) uses a divide-and-conquer algorithm and k-mer distances to compute a (lower accuracy) guide tree on unaligned sequences in O(N log(N)L) time.”