We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Shortest triplet clustering: reconstructing large phylogenies using representative sets.
- Authors
Le Sy Vinh; von Haeseler, Arndt
- 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.
- Subjects
PHYLOGENY; BIOINFORMATICS; ALGORITHMS; COMPUTER simulation; ELECTRONIC data processing
- Publication
BMC Bioinformatics, 2005, Vol 6, p92
- ISSN
1471-2105
- Publication type
Article
- DOI
10.1186/1471-2105-6-92