TY - GEN
T1 - PRec-I-DCM3
T2 - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
AU - Coarfa, Cristian
AU - Dotsenko, Yuri
AU - Mellor-Crummey, John
AU - Nakhleh, Luay
AU - Roshan, Usman
PY - 2005
Y1 - 2005
N2 - Accurate reconstruction of phylogenetic trees very often involves solving hard optimization problems, particularly the maximum parsimony (MP) and maximum likelihood (ML) problems. Various heuristics have been devised for solving these two problems; however, they obtain good results within reasonable time only on small datasets. This has been a major impediment for large-scale phytogeny reconstruction, particularly for the effort to assemble the Tree of Life - the evolutionary relationship of all organisms on earth. Roshan et al. recently introduced Rec- I -DCM3, an efficient and accurate meta-method for solving the MP problem on large datasets of up to 14,000 taxa. Nonetheless, a drastic improvement in Rec- I Rec-I-DCM3's-DCM3's performance is still needed in order to achieve similar (or better) accuracy on datasets at the scale of the Tree of Life. In this paper, we improve the performance of Rec- I -DCM3 via parallelization. Experimental results demonstrate that our parallel method, PRec-I-DCM3, achieves significant improvements, both in speed and accuracy, over its sequential counterpart.
AB - Accurate reconstruction of phylogenetic trees very often involves solving hard optimization problems, particularly the maximum parsimony (MP) and maximum likelihood (ML) problems. Various heuristics have been devised for solving these two problems; however, they obtain good results within reasonable time only on small datasets. This has been a major impediment for large-scale phytogeny reconstruction, particularly for the effort to assemble the Tree of Life - the evolutionary relationship of all organisms on earth. Roshan et al. recently introduced Rec- I -DCM3, an efficient and accurate meta-method for solving the MP problem on large datasets of up to 14,000 taxa. Nonetheless, a drastic improvement in Rec- I Rec-I-DCM3's-DCM3's performance is still needed in order to achieve similar (or better) accuracy on datasets at the scale of the Tree of Life. In this paper, we improve the performance of Rec- I -DCM3 via parallelization. Experimental results demonstrate that our parallel method, PRec-I-DCM3, achieves significant improvements, both in speed and accuracy, over its sequential counterpart.
UR - http://www.scopus.com/inward/record.url?scp=23944443960&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=23944443960&partnerID=8YFLogxK
U2 - 10.1109/ICPADS.2005.240
DO - 10.1109/ICPADS.2005.240
M3 - Conference contribution
AN - SCOPUS:23944443960
SN - 0769522815
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
SP - 346
EP - 350
BT - Proceedings - 11th International Conference on Parallel and Distributed Systems Workshops, ICPADS 2005
A2 - Ma, J.
A2 - Yang, L.T.
Y2 - 20 July 2005 through 22 July 2005
ER -