Clearcut: a fast implementation of relaxed neighbor joining

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Traditional Neighbor Joining (NJ) has limitations in handling large datasets due to its O(N^3) time complexity.
• The Relaxed Neighbor Joining (RNJ) algorithm offers a more efficient alternative with a typical-case time complexity of O(N^2 log N).

Purpose of the Study:

• To introduce Clearcut, an open-source C program implementing the RNJ algorithm.
• To provide a computationally efficient tool for phylogenetic tree reconstruction, especially for large datasets.

Main Methods:

• Clearcut implements the RNJ algorithm for phylogenetic tree reconstruction.
• The software accepts aligned sequences or distance matrices as input.
• It also includes a fast standard NJ implementation for comparison.

Main Results:

• RNJ achieves a typical-case time complexity of O(N^2 log N), outperforming NJ for large datasets.
• RNJ maintains the ability to reconstruct the true tree from additive pairwise distances.
• Clearcut offers a practical implementation of RNJ for inferring large phylogenetic trees.

Conclusions:

• Clearcut is a valuable open-source tool for efficient phylogenetic tree reconstruction using the RNJ algorithm.
• The software addresses the scalability limitations of traditional NJ methods.
• RNJ provides a computationally advantageous approach without compromising the accuracy of phylogenetic inference.