Title :
Parallel branch-and-bound algorithm for constructing evolutionary trees from distance matrix
Author :
Yu, Kun-Ming ; Zhou, Jiayi ; Lin, Chun-Yuan ; Tang, Chuan Yi
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Chung Hua Univ., Hsinchu
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 :
computational complexity; evolutionary computation; matrix algebra; optimisation; parallel algorithms; tree searching; trees (mathematics); NP-hard problem; branch-and-bound algorithm; distance matrix; evolutionary tree; minimum ultrametric tree; parallel algorithm; parallel computing; tree construction; Biological system modeling; Biology; Cells (biology); Computer science; Contracts; Costs; Evolution (biology); NP-hard problem; Partitioning algorithms; Sequences; Parallel computing; branch-and-bound; distance matrices; evolutionary tree; minimum ultrametric trees.;
Conference_Titel :
High-Performance Computing in Asia-Pacific Region, 2005. Proceedings. Eighth International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7695-2486-9
DOI :
10.1109/HPCASIA.2005.65
