An efficient parallel algorithm for ultrametric tree construction based on 3PR

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

doi:10.1007/11942634_23

An efficient parallel algorithm for ultrametric tree construction based on 3PR

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

^*Corresponding author for this work

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

1 Scopus citations

Abstract

In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.

Original language	English
Title of host publication	Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings
Pages	215-220
Number of pages	6
DOIs	https://doi.org/10.1007/11942634_23
State	Published - 2006
Externally published	Yes
Event	Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006 - Sorrento, Italy Duration: 04 12 2006 → 07 12 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4331 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006
Country/Territory	Italy
City	Sorrento
Period	04/12/06 → 07/12/06

Keywords

3-point relationship
4-point relationship
Minimum ultrametric tree
Parallel branch-and-bound algorithm
Phylogenetic tree

Access to Document

10.1007/11942634_23

Cite this

Yu, K. M., Zhou, J., Lin, C. Y., & Tang, C. Y. (2006). An efficient parallel algorithm for ultrametric tree construction based on 3PR. In Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings (pp. 215-220). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4331 LNCS). https://doi.org/10.1007/11942634_23

Yu, Kun Ming ; Zhou, Jiayi ; Lin, Chun Yuan et al. / An efficient parallel algorithm for ultrametric tree construction based on 3PR. Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings. 2006. pp. 215-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c2919bb535b442408d7d124f03c16058,

title = "An efficient parallel algorithm for ultrametric tree construction based on 3PR",

abstract = "In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.",

keywords = "3-point relationship, 4-point relationship, Minimum ultrametric tree, Parallel branch-and-bound algorithm, Phylogenetic tree",

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

year = "2006",

doi = "10.1007/11942634_23",

language = "英语",

isbn = "3540498605",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "215--220",

booktitle = "Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings",

note = "Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006 ; Conference date: 04-12-2006 Through 07-12-2006",

}

Yu, KM, Zhou, J, Lin, CY & Tang, CY 2006, An efficient parallel algorithm for ultrametric tree construction based on 3PR. in Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4331 LNCS, pp. 215-220, Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006, Sorrento, Italy, 04/12/06. https://doi.org/10.1007/11942634_23

An efficient parallel algorithm for ultrametric tree construction based on 3PR. / Yu, Kun Ming; Zhou, Jiayi; Lin, Chun Yuan et al.
Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings. 2006. p. 215-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4331 LNCS).

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

TY - GEN

T1 - An efficient parallel algorithm for ultrametric tree construction based on 3PR

AU - Yu, Kun Ming

AU - Zhou, Jiayi

AU - Lin, Chun Yuan

AU - Tang, Chuan Yi

PY - 2006

Y1 - 2006

N2 - In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.

AB - In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologists to observe existent species. One of popular model is ultrametric tree, and it assumed the evolution rate is constant. UPGMA is one of well-known ultrametric tree algorithm. However, UPGMA is a heuristic algorithm, and it can not guarantee the constructed tree is minimum size. To construct minimum ultrametric tree (MUT) has been shown to be an NP-hard problem. In this paper, we propose an efficient parallel branch-and-bound algorithm with 3-Point Relationship (3PR) to reduce the construction time dramatically. 3PR is a relationship between a distance matrix and the constructed phylogenetic tree. The main concept is for any two species closed to each other in a distance matrix should be also closed to each other in the constructed phylogenetic tree. We use this property to mark the branching path with lower priority or higher, then we move the lower ranked branching path to delay bound pool instead of remove it to ensure the optimal solution can be found. The experimental results show that our parallel algorithm can save the computing time and it also shows that parallel algorithm with 3PR can save about 25% of computing time in average.

KW - 3-point relationship

KW - 4-point relationship

KW - Minimum ultrametric tree

KW - Parallel branch-and-bound algorithm

KW - Phylogenetic tree

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

U2 - 10.1007/11942634_23

DO - 10.1007/11942634_23

M3 - 会议稿件

AN - SCOPUS:84883861242

SN - 3540498605

SN - 9783540498605

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 215

EP - 220

BT - Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings

T2 - Int. Workshops on FHPCN 2006, XHPC 2006, S-GRACE 2006, GridGIS 2006, HPC-GTP 2006, PDCE 2006, ParDMCom 2006, WOMP 2006, ISDF 2006, and UPWN 2006, Held in Conjunction with the 4th Int. Symp. on Parallel and Distributed Processing and Appl., SPA 2006

Y2 - 4 December 2006 through 7 December 2006

ER -

Yu KM, Zhou J, Lin CY, Tang CY. An efficient parallel algorithm for ultrametric tree construction based on 3PR. In Frontiers of High Performance Computing and Networking - ISPA 2006 International Workshops, FHPCN, XHPC, S-GRACE, GridGIS, HPC-GTP, PDCE, ParDMCom, WOMP, ISDF, and UPWN, Proceedings. 2006. p. 215-220. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11942634_23

An efficient parallel algorithm for ultrametric tree construction based on 3PR

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this