title: FastJoin, an improved neighbor-joining algorithm.
abstract: Reconstructing the evolutionary history of a set of  species is an elementary problem in biology, and methods for solving this  problem are evaluated based on two characteristics: accuracy and efficiency.  Neighbor-joining reconstructs phylogenetic trees by iteratively picking a pair  of nodes to merge as a new node until only one node remains; due to its good  accuracy and speed, it has been embraced by the phylogeny research community.  With the advent of large amounts of data, improved fast and precise methods for  reconstructing evolutionary trees have become necessary. We improved the  neighbor-joining algorithm by iteratively picking two pairs of nodes and  merging as two new nodes, until only one node remains. We found that another  pair of true neighbors could be chosen to merge as a new node besides the pair  of true neighbors chosen by the criterion of the neighbor-joining method, in  each iteration of the clustering procedure for the purely additive tree. These  new neighbors will be selected by another iteration of the neighbor-joining  method, so that they provide an improved neighbor-joining algorithm, by  iteratively picking two pairs of nodes to merge as two new nodes until only one  node remains, constructing the same phylogenetic tree as the neighbor-joining  algorithm for the same input data. By combining the improved neighbor-joining  algorithm with styles upper bound computation optimization of RapidNJ and  external storage of ERapidNJ methods, a new method of reconstructing  phylogenetic trees, FastJoin, was proposed. Experiments with sets of data  showed that this new neighbor-joining algorithm yields a significant speed-up  compared to classic neighbor-joining, showing empirically that FastJoin is  superior to almost all other neighbor-joining implementations.
authors.affiliation: School of Computer Science and Technology, Harbin Institute of Technology, Harbin, Heilongjiang, PR China. wangjuanangle@hit.edu.cn
authors.forename: J
authors.initials: J
authors.lastname: Wang
authors.forename: M-Z
authors.initials: MZ
authors.lastname: Guo
authors.forename: L L
authors.initials: LL
authors.lastname: Xing
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D010802:Phylogeny