pNJTree: A parallel program for reconstruction of neighbor-joining tree and its application in ClustalW

Neighbor-joining (NJ) is a distance-based method for tree construction. It is the most widely used method with polynomial time complexity at present. However, a fundamental problem with the previous implementations of this method is its limitation to handle large taxa sets within a reasonable time and memory resources. In this paper, we present a parallel implementation, pNJTree, for fast construction of very large phylogenetic trees. In comparison, pNJTree gets near-linear speedup for large taxa sets. It can be used to improve the speedup of the parallelized ClustalW methods.