A Flexible Variant of the Neighbor-Joining for Building Phylogenetic Trees

An important problem in Computational Biology is to rebuild a phylogenetic tree from a set of species $S$ and the respective evolutionary distances between each pair of specie in S. The most used methods for accomplishing this task are those distance-based due to their efficiency and accuracy. Find a phylogenetic tree can be performed by Neighbor-Joining (NJ) method, a high accuracy distance-based method, but whose running can be impractical when the amount of species is large, since it is a cubic time algorithm in the worst case. The Unweighted Pair Group Method Arithmetic Mean (UPGMA) is another distance-based method faster than Neighbor-Joining whose complexity is quadratic whether good data structures are used, however its accuracy is not so good when compared to Neighbor-Joining. In this article we present a flexible variant of the NJ algorithm that is faster than the NJ and can construct phylogenetic trees with good accuracy. Through experimental tests we demonstrate that with a good calibration our Flexible Neighbor-Joining reach solutions with accuracy better than UPGMA and with time performance better than both NJ and UPGMA methods.