Parallel Branch-and-Bound Algorithm for Constructing Evolutionary Trees from Distance Matrix

摘要

An ultrametric tree is an evolutionary tree in which the distances from the root to all leaves in the tree are equal. The Minimum Ultrametric Tree construction problem is the problem of constructing an ultrametric tree from distance matrices with minimum cost. It is shown that to construct a minimum cost ultrametric tree is NP-hard. In this paper, we present an efficient parallel branch and bound algorithm to construct a minimum ultrametric tree with less cost. The experimental results show that our proposed algorithm can discover optimal solutions for 38 species within reasonable time with 16 computing nodes.