eCite Digital Repository

Faster exact maximum parsimony search with XMP


White, WTJ and Holland, BR, Faster exact maximum parsimony search with XMP, Bioinformatics, 27, (10) pp. 1359-1367. ISSN 1367-4803 (2011) [Refereed Article]

Restricted - Request a copy

Copyright Statement

The definitive publisher-authenticated version is available online at:

Official URL:

DOI: doi:10.1093/bioinformatics/btr147


Motivation: Despite trends towards maximum likelihood and Bayesian criteria, maximum parsimony (MP) remains an important criterion for evaluating phylogenetic trees. Because exact MP search is NP-complete, the computational effort needed to find provably optimal trees skyrockets with increasing numbers of taxa, limiting analyses to around 2530 taxa. This is, in part, because currently available programs fail to take advantage of parallelism. Results: We present XMP, a new program for finding exact MP trees that comes in both serial and parallel versions. The serial version is faster in nearly all tests than existing software. The parallel version uses a work-stealing algorithm to scale to hundreds of CPUs on a distributed-memory multiprocessor with high efficiency. An optimized SSE2 inner loop provides additional speedup for Pentium 4 and later CPUs. Availability: C source code and several binary versions are freely available from The parallel version requires an MPI implementation, such as the freely available MPICH2.

Item Details

Item Type:Refereed Article
Research Division:Biological Sciences
Research Group:Bioinformatics and computational biology
Research Field:Bioinformatic methods development
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the biological sciences
UTAS Author:Holland, BR (Professor Barbara Holland)
ID Code:69836
Year Published:2011
Web of Science® Times Cited:7
Deposited By:Mathematics and Physics
Deposited On:2011-05-23
Last Modified:2018-03-18

Repository Staff Only: item control page