.png){kind=icon}
返回
Efficient parallel branch-and-bound algorithm for constructing minimum ultrametric trees
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2009.04.008.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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. (C) 2009 Elsevier Inc. All rights reserved.
Keyword:
Parallel branch-and-bound algorithm
Evolutionary tree construction
Distance matrix
Minimum ultrametric tree
Load-balancing
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
.png){kind=icon}
分享收藏Audio-visual underdetermined blind source separation algorithm based on Gaussian potential function
PREAI
分享收藏
<title>Pulsed-laser deposition as a novel preparation technique for chemical microsensors</title>
PREAI
分享收藏
查看更多内容