title: Clearcut: a fast implementation of relaxed neighbor joining.
abstract: CONCLUSIONS
  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.
  
  
  BACKGROUND
  Clearcut source code is available for download at: http://bioinformatics.hungry.com/clearcut
authors.affiliation: Department of Biological Sciences, University of Idaho, Moscow, ID, USA. sheneman@hungry.com
authors.forename: Luke
authors.initials: L
authors.lastname: Sheneman
authors.forename: Jason
authors.initials: J
authors.lastname: Evans
authors.forename: James A
authors.initials: JA
authors.lastname: Foster
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny; D011381:Programming Languages; D012984:Software