Format

Send to

Choose Destination
BMC Evol Biol. 2018 Feb 2;18(1):11. doi: 10.1186/s12862-018-1131-3.

MPBoot: fast phylogenetic maximum parsimony tree inference and bootstrap approximation.

Author information

1
University of Engineering and Technology, Vietnam National University, Hanoi, Vietnam.
2
Department of Genetics, Evolution and Environment, University College London, Gower Street, London, WC1E 6BT, UK.
3
Heidelberg Institute for Theoretical Studies, Heidelberg, Germany.
4
Karlsruhe Institute of Technology, Institute for Theoretical Informatics, Karlsruhe, Germany.
5
Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University Vienna, Campus Vienna Biocenter 5, A-1030, Vienna, Austria. arndt.von.haeseler@univie.ac.at.
6
Bioinformatics and Computational Biology, Faculty of Computer Science, University of Vienna, Vienna, Austria. arndt.von.haeseler@univie.ac.at.
7
Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University Vienna, Campus Vienna Biocenter 5, A-1030, Vienna, Austria. minh.bui@univie.ac.at.

Abstract

BACKGROUND:

The nonparametric bootstrap is widely used to measure the branch support of phylogenetic trees. However, bootstrapping is computationally expensive and remains a bottleneck in phylogenetic analyses. Recently, an ultrafast bootstrap approximation (UFBoot) approach was proposed for maximum likelihood analyses. However, such an approach is still missing for maximum parsimony.

RESULTS:

To close this gap we present MPBoot, an adaptation and extension of UFBoot to compute branch supports under the maximum parsimony principle. MPBoot works for both uniform and non-uniform cost matrices. Our analyses on biological DNA and protein showed that under uniform cost matrices, MPBoot runs on average 4.7 (DNA) to 7 times (protein data) (range: 1.2-20.7) faster than the standard parsimony bootstrap implemented in PAUP*; but 1.6 (DNA) to 4.1 times (protein data) slower than the standard bootstrap with a fast search routine in TNT (fast-TNT). However, for non-uniform cost matrices MPBoot is 5 (DNA) to 13 times (protein data) (range:0.3-63.9) faster than fast-TNT. We note that MPBoot achieves better scores more frequently than PAUP* and fast-TNT. However, this effect is less pronounced if an intensive but slower search in TNT is invoked. Moreover, experiments on large-scale simulated data show that while both PAUP* and TNT bootstrap estimates are too conservative, MPBoot bootstrap estimates appear more unbiased.

CONCLUSIONS:

MPBoot provides an efficient alternative to the standard maximum parsimony bootstrap procedure. It shows favorable performance in terms of run time, the capability of finding a maximum parsimony tree, and high bootstrap accuracy on simulated as well as empirical data sets. MPBoot is easy-to-use, open-source and available at http://www.cibiv.at/software/mpboot .

KEYWORDS:

Maximum parsimony; Nonparametric bootstrap; Phylogenetic inference

PMID:
29390973
PMCID:
PMC5796505
DOI:
10.1186/s12862-018-1131-3
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for BioMed Central Icon for PubMed Central
Loading ...
Support Center