Hoang Diep Thi, Vinh Le Sy, Flouri Tomáš, Stamatakis Alexandros, von Haeseler Arndt, Minh Bui Quang
University of Engineering and Technology, Vietnam National University, Hanoi, Vietnam.
Department of Genetics, Evolution and Environment, University College London, Gower Street, London, WC1E 6BT, UK.
BMC Evol Biol. 2018 Feb 2;18(1):11. doi: 10.1186/s12862-018-1131-3.
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.
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.
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 .
非参数自展法被广泛用于衡量系统发育树的分支支持度。然而，自展法计算成本高昂，仍然是系统发育分析的瓶颈。最近，一种超快速自展近似（UFBoot）方法被提出用于最大似然分析。然而，最大简约法仍缺少这样一种方法。
为了填补这一空白，我们提出了MPBoot，它是UFBoot的一种改编和扩展，用于在最大简约原则下计算分支支持度。MPBoot适用于均匀和非均匀成本矩阵。我们对生物DNA和蛋白质的分析表明，在均匀成本矩阵下，MPBoot的运行速度平均比PAUP中实现的标准简约自展法快4.7倍（DNA）至7倍（蛋白质数据）（范围：1.2 - 20.7）；但比TNT中具有快速搜索程序的标准自展法慢1.6倍（DNA）至4.1倍（蛋白质数据）。然而，对于非均匀成本矩阵，MPBoot比快速TNT快5倍（DNA）至13倍（蛋白质数据）（范围：0.3 - 63.9）。我们注意到，MPBoot比PAUP和快速TNT更频繁地获得更好的分数。然而，如果在TNT中调用密集但较慢的搜索，这种效果就不那么明显了。此外,对大规模模拟数据的实验表明，虽然PAUP*和TNT自展估计都过于保守，但MPBoot自展估计似乎更无偏差。
MPBoot为标准最大简约自展程序提供了一种有效的替代方法。它在运行时间、找到最大简约树的能力以及对模拟和实证数据集的高自展准确性方面表现出良好的性能。MPBoot易于使用、开源，可在http://www.cibiv.at/software/mpboot获取。
