3-points relationship based parallel algorithm for minimum ultrametric tree construction

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

To construct an evolutionary tree is an important topic in computational biology. An evolutionary tree can symbolize the relationship and histories for a set of species. There are many models had been proposed to resolve these problems. However, most of them are NP-hard problem. Ultrametric tree is one of the most popular models, it is used by a well-accepted tree construction method-Unweighted Pair Group Method with Arithmetic Mean, which is widely used by biologists to observe the relationship among species. However, it is a heuristic algorithm. In this paper, we proposed a 3-Points relationship (3PR) based parallel algorithm to solve this problem. 3PR is a relationship between distance matrix and constructed evolutionary trees. The main concept is for any triplet species, two species closer to each other in distance matrix should be closer to each other in evolutionary tree. Then we combined this property and branch-and-bound strategy to reduce the computation time to obtain the optimal solution. Moreover, we put the lower ranked path which is determined by 3PR to delay bound pool (DBP) to accelerate the algorithm execution. DBP is a mechanism which can store the lower ranked path and can be helping algorithm to find a better bounding values speedily. The experimental results show that our proposed algorithm can reduce the computation time compared with algorithm without 3PR. Moreover, it also shows 3PR can reduce the computation time when number of computing nodes increasing.

Original languageEnglish
Title of host publicationParallel Computing Technologies - 9th International Conference, PaCT 2007, Proceedings
PublisherSpringer Verlag
Pages615-622
Number of pages8
ISBN (Print)9783540739395
DOIs
StatePublished - 2007
Externally publishedYes
Event9th International Conference on Parallel Computing Technologies, PaCT 2007 - Pereslavl-Zalessky, Russian Federation
Duration: 03 09 200707 09 2007

Publication series

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

Conference

Conference9th International Conference on Parallel Computing Technologies, PaCT 2007
Country/TerritoryRussian Federation
CityPereslavl-Zalessky
Period03/09/0707/09/07

Fingerprint

Dive into the research topics of '3-points relationship based parallel algorithm for minimum ultrametric tree construction'. Together they form a unique fingerprint.

Cite this