Parallelized calculation of permutation tests.
Parallelized calculation of permutation tests.
复制标题
DOI：
10.1093/bioinformatics/btaa1007
复制
发表时间：
2021-04-01
期刊：
影响因子：
--
通讯作者：
Käll L
中科院分区：
文献类型：
--
作者：
Ekvall M;Höhle M;Käll L
排列检验提供了一个简单的框架来评估样本统计差异的显著性。置换检验的一个显著优点是相对较少的假设需要测试统计量的分布，因为它们依赖于组标签的互换性假设。它们有很大的价值，因为它们允许进行敏感性分析，以确定检验统计量的假设广泛样本分布的适用程度。然而，在这种情况下，置换测试很少被应用，因为简单实现的运行时间太慢，并且随着样本大小呈指数增长。然而，在20世纪80年代的持续发展引入了动态规划算法，可以在多项式时间内计算精确的排列测试。尽管运行时间显著缩短，但精确检验尚未成为中等样本量的主要统计检验之一。在这里，我们提出了一个这样的动态规划为基础的置换测试，绿色算法，这使得置换测试更有吸引力的计算并行化。绿色算法的并行化被发现是可能的，通过非平凡的重排的算法的结构。通过在GPU上执行并行化算法，可以实现数量级的加速。我们证明，执行时间基本上成为一个非问题的样本大小，甚至高达数百个样本。这种改进使我们的方法成为一种有吸引力的替代方法，例如广泛使用的渐近Mann-Whitney U检验。在Apache 2.0许可下，来自GitHub存储库https://github.com/statisticalbiotechnology/parallelPermutationTest的Python 3代码。 补充数据可在Bioinformatics在线获得。
Permutation tests offer a straightforward framework to assess the significance of differences in sample statistics. A significant advantage of permutation tests are the relatively few assumptions about the distribution of the test statistic are needed, as they rely on the assumption of exchangeability of the group labels. They have great value, as they allow a sensitivity analysis to determine the extent to which the assumed broad sample distribution of the test statistic applies. However, in this situation, permutation tests are rarely applied because the running time of naïve implementations is too slow and grows exponentially with the sample size. Nevertheless, continued development in the 1980s introduced dynamic programming algorithms that compute exact permutation tests in polynomial time. Albeit this significant running time reduction, the exact test has not yet become one of the predominant statistical tests for medium sample size. Here, we propose a computational parallelization of one such dynamic programming-based permutation test, the Green algorithm, which makes the permutation test more attractive. Parallelization of the Green algorithm was found possible by non-trivial rearrangement of the structure of the algorithm. A speed-up—by orders of magnitude—is achievable by executing the parallelized algorithm on a GPU. We demonstrate that the execution time essentially becomes a non-issue for sample sizes, even as high as hundreds of samples. This improvement makes our method an attractive alternative to, e.g. the widely used asymptotic Mann-Whitney U-test. In Python 3 code from the GitHub repository https://github.com/statisticalbiotechnology/parallelPermutationTest under an Apache 2.0 license. Supplementary data are available at Bioinformatics online.
登录
查看更多内容
影响因子：
3.3
作者：
Fay MP;Proschan MA
通讯作者：
Proschan MA
影响因子：
1.9
作者：
Segal, Brian D.;Braun, Thomas;Jiang, Hui
通讯作者：
Jiang, Hui
影响因子：
5.8
作者：
Huang, Yifan;Xu, Haiyan;Hsu, Jason C.
通讯作者：
Hsu, Jason C.
影响因子：
1.8
作者：
GREEN, BF
通讯作者：
GREEN, BF
DOI：
10.1073/pnas.1530509100
发表时间：
2003-08-05
影响因子：
11.1
作者：
Storey, JD;Tibshirani, R
通讯作者：
Tibshirani, R