TY - JOUR

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

AU - Yu, Kun Ming

AU - Zhou, Jiayi

AU - Lin, Chun Yuan

AU - Tang, Chuan Yi

PY - 2009/11

Y1 - 2009/11

N2 - 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.

AB - 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.

KW - Distance matrix

KW - Evolutionary tree construction

KW - Load-balancing

KW - Minimum ultrametric tree

KW - Parallel branch-and-bound algorithm

UR - http://www.scopus.com/inward/record.url?scp=70349446325&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2009.04.008

DO - 10.1016/j.jpdc.2009.04.008

M3 - 文章

AN - SCOPUS:70349446325

SN - 0743-7315

VL - 69

SP - 905

EP - 914

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 11

ER -