Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2007 Feb 1;23(3):372-4.
doi: 10.1093/bioinformatics/btl592. Epub 2006 Nov 21.

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

Kazutaka Katoh  1 , Hiroyuki Toh
Affiliations

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

Kazutaka Katoh et al. Bioinformatics. .

Abstract

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.

PubMed Disclaimer

Publication types

LinkOut - more resources