Bioinformatics Advance Access originally published online on September 18, 2006
Bioinformatics 2006 22(22):2823-2824; doi:10.1093/bioinformatics/btl478
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Clearcut: a fast implementation of relaxed neighbor joining
Department of Biological Sciences, University of Idaho Moscow, ID, USA
*To whom correspondence should be addressed.
Summary: Clearcut is an open source implementation for the relaxed neighbor joining (RNJ) algorithm. While traditional neighbor joining (NJ) remains a popular method for distance-based phylogenetic tree reconstruction, it suffers from a O(N3) time complexity, where N represents the number of taxa in the input. Due to this steep asymptotic time complexity, NJ cannot reasonably handle very large datasets. In contrast, RNJ realizes a typical-case time complexity on the order of N2logN without any significant qualitative difference in output. RNJ is particularly useful when inferring a very large tree or a large number of trees. In addition, RNJ retains the desirable property that it will always reconstruct the true tree given a matrix of additive pairwise distances. Clearcut implements RNJ as a C program, which takes either a set of aligned sequences or a pre-computed distance matrix as input and produces a phylogenetic tree. Alternatively, Clearcut can reconstruct phylogenies using an extremely fast standard NJ implementation.
Availability: Clearcut source code is available for download at: http://bioinformatics.hungry.com/clearcut
Contact: sheneman{at}hungry.com
Supplementary information: http://bioinformatics.hungry.com/clearcut
Received on June 8, 2006; revised on September 5, 2006; accepted on September 6, 2006
This article has been cited by other articles:
![]() |
C. L. Lauber, M. Hamady, R. Knight, and N. Fierer Pyrosequencing-Based Assessment of Soil pH as a Predictor of Soil Bacterial Community Structure at the Continental Scale Appl. Envir. Microbiol., August 1, 2009; 75(15): 5111 - 5120. [Abstract] [Full Text] [PDF] |
||||
![]() |
R. M. Bowers, C. L. Lauber, C. Wiedinmyer, M. Hamady, A. G. Hallar, R. Fall, R. Knight, and N. Fierer Characterization of Airborne Microbial Communities at a High-Elevation Site and Their Potential To Act as Atmospheric Ice Nuclei Appl. Envir. Microbiol., August 1, 2009; 75(15): 5121 - 5130. [Abstract] [Full Text] [PDF] |
||||
![]() |
M. Hamady and R. Knight Microbial community profiling for human microbiome projects: Tools, techniques, and challenges Genome Res., July 1, 2009; 19(7): 1141 - 1152. [Abstract] [Full Text] [PDF] |
||||
![]() |
M. R. Aniba, S. Siguenza, A. Friedrich, F. Plewniak, O. Poch, A. Marchler-Bauer, and J. D. Thompson Knowledge-based expert systems and a proof-of-concept case study for multiple sequence alignment construction and analysis Brief Bioinform, January 1, 2009; 10(1): 11 - 23. [Abstract] [Full Text] [PDF] |
||||
![]() |
N. Fierer, M. Hamady, C. L. Lauber, and R. Knight The influence of sex, handedness, and washing on the diversity of hand surface bacteria PNAS, November 18, 2008; 105(46): 17994 - 17999. [Abstract] [Full Text] [PDF] |
||||
![]() |
Z. Liu, T. Z. DeSantis, G. L. Andersen, and R. Knight Accurate taxonomy assignments from 16S rRNA sequences produced by highly parallel pyrosequencers Nucleic Acids Res., October 1, 2008; 36(18): e120 - e120. [Abstract] [Full Text] [PDF] |
||||




