Format

Send to

Choose Destination
See comment in PubMed Commons below
BMC Bioinformatics. 2005 Apr 8;6:92.

Shortest triplet clustering: reconstructing large phylogenies using representative sets.

Author information

1
Heinrich-Heine-Universität Düsseldorf, WE Informatik, Universitätstr. 1, D-040225 Düsseldorf, Germany. vinh@cs.uni-duesseldorf.de

Abstract

BACKGROUND:

Understanding the evolutionary relationships among species based on their genetic information is one of the primary objectives in phylogenetic analysis. Reconstructing phylogenies for large data sets is still a challenging task in Bioinformatics.

RESULTS:

We propose a new distance-based clustering method, the shortest triplet clustering algorithm (STC), to reconstruct phylogenies. The main idea is the introduction of a natural definition of so-called k-representative sets. Based on k-representative sets, shortest triplets are reconstructed and serve as building blocks for the STC algorithm to agglomerate sequences for tree reconstruction in O(n2) time for n sequences. Simulations show that STC gives better topological accuracy than other tested methods that also build a first starting tree. STC appears as a very good method to start the tree reconstruction. However, all tested methods give similar results if balanced nearest neighbor interchange (BNNI) is applied as a post-processing step. BNNI leads to an improvement in all instances. The program is available at http://www.bi.uni-duesseldorf.de/software/stc/.

CONCLUSION:

The results demonstrate that the new approach efficiently reconstructs phylogenies for large data sets. We found that BNNI boosts the topological accuracy of all methods including STC, therefore, one should use BNNI as a post-processing step to get better topological accuracy.

PMID:
15819989
PMCID:
PMC1097715
DOI:
10.1186/1471-2105-6-92
[Indexed for MEDLINE]
Free PMC Article
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for BioMed Central Icon for PubMed Central
    Loading ...
    Support Center