TY - GEN
T1 - ExactMP
T2 - ICPP 2006: 2006 International Conference on Parallel Processing
AU - Bader, David A.
AU - Chandu, Vaddadi P.
AU - Yan, Mi
PY - 2006
Y1 - 2006
N2 - Constructing phylogenetic trees in the study of the evolutionary history of a group organisms is an extremely challenging problem in computational biology. The problem becomes intractable with growing number of organisms. In this paper, we design and implement an efficient parallel solver (ExactMP) using a parsimony based approach for solving this problem. We create a testbed consisting of eighteen datasets of varying size (up to 27 taxa) and difficulty level (easy to hard), containing real (Eukaryotes, Metazoan, and rbcL) and randomly-generated synthetic genome sequences. We demonstrate our ExactMP Solver against this testbed and achieve a parallel speedup of up to 7.26 with 8 processors using an 8-way symmetric multiprocessor. The main contributions of this work are: (1) an efficient parallel solver ExactMP for the problem of phylogenetic tree reconstruction using maximum parsimony, (2) a new upper bounding methodology for this problem using heuristic and randomization techniques, and (3) a highly optimized branch and bound algorithm for this problem.
AB - Constructing phylogenetic trees in the study of the evolutionary history of a group organisms is an extremely challenging problem in computational biology. The problem becomes intractable with growing number of organisms. In this paper, we design and implement an efficient parallel solver (ExactMP) using a parsimony based approach for solving this problem. We create a testbed consisting of eighteen datasets of varying size (up to 27 taxa) and difficulty level (easy to hard), containing real (Eukaryotes, Metazoan, and rbcL) and randomly-generated synthetic genome sequences. We demonstrate our ExactMP Solver against this testbed and achieve a parallel speedup of up to 7.26 with 8 processors using an 8-way symmetric multiprocessor. The main contributions of this work are: (1) an efficient parallel solver ExactMP for the problem of phylogenetic tree reconstruction using maximum parsimony, (2) a new upper bounding methodology for this problem using heuristic and randomization techniques, and (3) a highly optimized branch and bound algorithm for this problem.
UR - http://www.scopus.com/inward/record.url?scp=34547414434&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547414434&partnerID=8YFLogxK
U2 - 10.1109/ICPP.2006.40
DO - 10.1109/ICPP.2006.40
M3 - Conference contribution
AN - SCOPUS:34547414434
SN - 0769526365
SN - 9780769526362
T3 - Proceedings of the International Conference on Parallel Processing
SP - 65
EP - 73
BT - ICPP 2006
Y2 - 14 August 2006 through 18 August 2006
ER -