The Exelixis Lab


Enabling Research in Evolutionary Biology

Parsimonator: A fast open-source parsimony program

Parsimonator v1.0.2 source code available here: https://github.com/stamatak/Parsimonator-1.0.2.

Parsimonator is a no-frills light-weight implementation for building starting trees under parsimony for RAxML-Light.

It deploys a randomized stepwise addition order algorithm to build trees and thereafter conducts a couple of SPR (Subtree Pruning Re-Grafting moves) to further improve the parsimony score.

Right now, parsimonator can only compute trees on DNA datasets. It uses SSE3 128-bit wide and 256-bit wide AVX (new as of v101) vector instructions to significantly accelerate parsimony computations.

Although it is significantly slower than TNT, I think that it is the fastest open-source parsimony function implementation, albeit the search algorithm itself is rather naïve.

It can also extend given trees that do not comprise all taxa of an input alignment by using a randomized stepwise addition order algorithm and for those taxa that are not contained in the starting tree. The source archive includes a manual.

The current version has been used to compute a parsimony tree on an alignment with 1481 taxa and 20,000,000 sites (a phylip file with a size of 27GB!).

Old version without OpenMP parallelization and bug fixes for very large datasets available here 1.0.1
Old Version without AVX instructions still available here 1.0.0