Fast NeighborNet: Improving the Speed of the Neighbor-Net Phylogenetic Network Algorithm with Multithreading and a Relaxed Search Strategy

Abstract

Fast Neighbor-Net is a command-line Java program that has fast implementations of the popular Neighbor-Net phylo-genetic split network approach. This allows more efficiency in computationally intensive tasks such as larger scale data analysis and bootstrapping. The canonical search phase iteratively finds a pair of connected components that minimizes a distance function in {Theta}(n3) time in the input taxa count. A relaxed search strategy has been implemented that has averagecase time complexity of[O] (n2 log n) but with {Theta}(n3) worst-case time complexity. This search strategy sacrifices some accuracy for speed. The original approachs implementation has been improved by using good programming practice. These improvements increased run-time performance by a constant factor of approximately 2 and reduced memory requirements by a constant factor of approximately 6. These search strategies allow multithreading to better use modern CPU hardware. PFAM data of 2000-30,000 taxa were used for testing performance. The canonical implementation with three threads improved average performance by approximately 2.1. The relaxed search has good quality, and the accuracy was tested on a mammal and a eukaryote data set. Kendall tau distance was used as a rough measure of topological similarity for the relaxed and canonical search strategies.