title: PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences.
abstract: BACKGROUND
  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.
  
  
  BACKGROUND
  The present algorithm has been implemented in the MAFFT sequence alignment package (http://align.bmr.kyushu-u.ac.jp/mafft/software/).
  
  
  BACKGROUND
  Supplementary information is available at Bioinformatics online.
authors.affiliation: Digital Medicine Initiative, Kyushu University, Fukuoka 812-8582, Japan. katoh@bioreg.kyushu-u.ac.jp
authors.forename: Kazutaka
authors.initials: K
authors.lastname: Katoh
authors.forename: Hiroyuki
authors.initials: H
authors.lastname: Toh
mesh_terms: D000465:Algorithms; D017124:Conserved Sequence; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*