4.7 Article

Clearcut: a fast implementation of relaxed neighbor joining

Journal

BIOINFORMATICS
Volume 22, Issue 22, Pages 2823-2824

Publisher

OXFORD UNIV PRESS
DOI: 10.1093/bioinformatics/btl478

Keywords

-

Funding

  1. NCRR NIH HHS [1P20 RR16448, P20 RR16454] Funding Source: Medline

Ask authors/readers for more resources

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(N-3) 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 N(2)logN 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@hungry.com Supplementary information: http://bioinformatics.hungry.com/clearcut.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available