Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix

Kun Ming Yu; Jiayi Zhou; Chun Yuan Lin; Oman Yi Tang

doi:10.1109/HPCASIA.2005.65

Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix

Kun Ming Yu^*, Jiayi Zhou, Chun Yuan Lin, Oman Yi Tang

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005
Pages	66-72
Number of pages	7
DOIs	https://doi.org/10.1109/HPCASIA.2005.65
State	Published - 2005
Externally published	Yes
Event	8th International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005 - Beijing, China Duration: 30 11 2005 → 03 12 2005

Publication series

Name	Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005
Volume	2005

Conference

Conference	8th International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005
Country/Territory	China
City	Beijing
Period	30/11/05 → 03/12/05

Keywords

Branch-and-bound
Distance matrices
Evolutionary tree
Minimum ultrametric trees
Parallel computing

Access to Document

10.1109/HPCASIA.2005.65

Cite this

Yu, K. M., Zhou, J., Lin, C. Y., & Tang, O. Y. (2005). Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix. In Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005 (pp. 66-72). Article 1592252 (Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005; Vol. 2005). https://doi.org/10.1109/HPCASIA.2005.65

Yu, Kun Ming ; Zhou, Jiayi ; Lin, Chun Yuan et al. / Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix. Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005. 2005. pp. 66-72 (Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005).

@inproceedings{0c826c023cc14d56832c22001ed382ed,

title = "Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix",

abstract = "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.",

keywords = "Branch-and-bound, Distance matrices, Evolutionary tree, Minimum ultrametric trees, Parallel computing",

author = "Yu, {Kun Ming} and Jiayi Zhou and Lin, {Chun Yuan} and Tang, {Oman Yi}",

year = "2005",

doi = "10.1109/HPCASIA.2005.65",

language = "英语",

isbn = "0769524869",

series = "Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005",

pages = "66--72",

booktitle = "Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005",

note = "8th International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005 ; Conference date: 30-11-2005 Through 03-12-2005",

}

Yu, KM, Zhou, J, Lin, CY & Tang, OY 2005, Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix. in Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005., 1592252, Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005, vol. 2005, pp. 66-72, 8th International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005, Beijing, China, 30/11/05. https://doi.org/10.1109/HPCASIA.2005.65

Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix. / Yu, Kun Ming; Zhou, Jiayi; Lin, Chun Yuan et al.
Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005. 2005. p. 66-72 1592252 (Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix

AU - Yu, Kun Ming

AU - Zhou, Jiayi

AU - Lin, Chun Yuan

AU - Tang, Oman Yi

PY - 2005

Y1 - 2005

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

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

KW - Branch-and-bound

KW - Distance matrices

KW - Evolutionary tree

KW - Minimum ultrametric trees

KW - Parallel computing

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

U2 - 10.1109/HPCASIA.2005.65

DO - 10.1109/HPCASIA.2005.65

M3 - 会议稿件

AN - SCOPUS:33847144208

SN - 0769524869

SN - 9780769524863

T3 - Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005

SP - 66

EP - 72

BT - Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005

T2 - 8th International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005

Y2 - 30 November 2005 through 3 December 2005

ER -

Yu KM, Zhou J, Lin CY, Tang OY. Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix. In Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005. 2005. p. 66-72. 1592252. (Proceedings - Eighth International Conference on High-Performance Computing in Asia-Pacific Region, HPC Asia 2005). doi: 10.1109/HPCASIA.2005.65

Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this