Efficient parallel branch-and-bound algorithm for constructing minimum ultrametric trees

The construction of evolutionary trees is important for computational biology, especially for the development of biological taxonomies. The ultrametric tree (UT) is a commonly used model for evolutionary trees assuming that the rate of evolution is constant (molecular clock hypothesis). However, the construction of minimum ultrametric trees (MUTs, principle of minimum evolution) has been shown to be NP-hard even from a metric distance matrix. The branch-and-bound algorithm is generally used to solve a wide variety of NP-hard problems. In previous work, a sequential branch-and-bound algorithm for constructing MUTs (BBU) was presented and the experimental results showed that it is useful for MUT construction. Hence, in this study, an efficient parallel branch-and-bound algorithm (PBBU) for constructing MUTs or near-MUTs from a metric distance matrix was designed. A random data set as well as some practical data sets of Human + Chimpanzee Mitochondrial and Bacteriophage T7 DNAs were used to test the PBBU. The experimental results show that the PBBU found an optimal solution for 36 species on 16 PCs within a reasonable time. To the best of our knowledge, no algorithm has been found to solve this problem even for 25 species. Moreover, the PBBU achieved satisfying speed-up ratios for most of the test cases.