Shortest triplet clustering: reconstructing large phylogenies using representative sets.
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/.


CONCLUSIONS
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.
Vinh
Le Sy
le S
Heinrich-Heine-Universität Düsseldorf, WE Informatik, Universitätstr. 1, D-040225 Düsseldorf, Germany. vinh@cs.uni-duesseldorf.de
von Haeseler
Arndt
A
D000465:Algorithms; D001483:Base Sequence; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D003201:Computers; D003627:Data Interpretation, Statistical; D019143:Evolution, Molecular; D020407:Internet; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D010363:Pattern Recognition, Automated; D010802:Phylogeny; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012984:Software