Skip Navigation



Bioinformatics Advance Access published online on September 18, 2006
Bioinformatics, doi:10.1093/bioinformatics/btl478
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow All Versions of this Article:
22/22/2823    most recent
btl478v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Sheneman, L.
Right arrow Articles by Foster, J. A.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Sheneman, L.
Right arrow Articles by Foster, J. A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2006). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org
Received June 8, 2006
Revised September 5, 2006
Accepted September 6, 2006

Applications note

Clearcut: a fast implementation of relaxed neighbor joining

Luke Sheneman 1 *, Jason Evans 1, and James A. Foster 1

1 Department of Biological Sciences, University of Idaho, Moscow, Idaho, USA

* To whom correspondence should be addressed.
Luke Sheneman, E-mail: sheneman{at}hungry.com


  Abstract

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. By 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 neighbor joining implementation.

Availability: Clearcut source code is available for download at: http://bioinformatics.hungry.com/clearcut.

Supplementary Information: http://bioinformatics.hungry.com/clearcut.

Associate Editor: Keith A Crandall
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Appl. Environ. Microbiol.Home page
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]

Home page
 Appl. Environ. Microbiol.Home page
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]

Home page
 Genome ResHome page
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]

Home page
 Brief BioinformHome page
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]

Home page
 Proc. Natl. Acad. Sci. USAHome page
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]

Home page
 Nucleic Acids ResHome page
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]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.