Cargando…

Parallelized calculation of permutation tests

MOTIVATION: 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 e...

Descripción completa

Detalles Bibliográficos
Autores principales: Ekvall, Markus, Höhle, Michael, Käll, Lukas
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Oxford University Press 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8016463/
https://www.ncbi.nlm.nih.gov/pubmed/33289531
http://dx.doi.org/10.1093/bioinformatics/btaa1007
_version_ 1783673865312927744
author Ekvall, Markus
Höhle, Michael
Käll, Lukas
author_facet Ekvall, Markus
Höhle, Michael
Käll, Lukas
author_sort Ekvall, Markus
collection PubMed
description MOTIVATION: 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. RESULTS: 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. AVAILABILITYAND IMPLEMENTATION: In Python 3 code from the GitHub repository https://github.com/statisticalbiotechnology/parallelPermutationTest under an Apache 2.0 license. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
format Online
Article
Text
id pubmed-8016463
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher Oxford University Press
record_format MEDLINE/PubMed
spelling pubmed-80164632021-04-07 Parallelized calculation of permutation tests Ekvall, Markus Höhle, Michael Käll, Lukas Bioinformatics Original Papers MOTIVATION: 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. RESULTS: 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. AVAILABILITYAND IMPLEMENTATION: In Python 3 code from the GitHub repository https://github.com/statisticalbiotechnology/parallelPermutationTest under an Apache 2.0 license. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. Oxford University Press 2020-12-08 /pmc/articles/PMC8016463/ /pubmed/33289531 http://dx.doi.org/10.1093/bioinformatics/btaa1007 Text en © The Author(s) 2020. Published by Oxford University Press. http://creativecommons.org/licenses/by/4.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Original Papers
Ekvall, Markus
Höhle, Michael
Käll, Lukas
Parallelized calculation of permutation tests
title Parallelized calculation of permutation tests
title_full Parallelized calculation of permutation tests
title_fullStr Parallelized calculation of permutation tests
title_full_unstemmed Parallelized calculation of permutation tests
title_short Parallelized calculation of permutation tests
title_sort parallelized calculation of permutation tests
topic Original Papers
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8016463/
https://www.ncbi.nlm.nih.gov/pubmed/33289531
http://dx.doi.org/10.1093/bioinformatics/btaa1007
work_keys_str_mv AT ekvallmarkus parallelizedcalculationofpermutationtests
AT hohlemichael parallelizedcalculationofpermutationtests
AT kalllukas parallelizedcalculationofpermutationtests