{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:33:56Z","timestamp":1772138036608,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"22-23","license":[{"start":{"date-parts":[[2020,12,8]],"date-time":"2020-12-08T00:00:00Z","timestamp":1607385600000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2017-04030"],"award-info":[{"award-number":["2017-04030"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001729","name":"Swedish Foundation for Strategic Research","doi-asserted-by":"publisher","award":["BD15-0043"],"award-info":[{"award-number":["BD15-0043"]}],"id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NVIDIA Corporation"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>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\u00efve 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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Parallelization of the Green algorithm was found possible by non-trivial rearrangement of the structure of the algorithm. A speed-up\u2014by orders of magnitude\u2014is 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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availabilityand implementation<\/jats:title>\n                    <jats:p>In Python 3 code from the GitHub repository https:\/\/github.com\/statisticalbiotechnology\/parallelPermutationTest under an Apache 2.0 license.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa1007","type":"journal-article","created":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T16:36:22Z","timestamp":1605803782000},"page":"5392-5397","source":"Crossref","is-referenced-by-count":4,"title":["Parallelized calculation of permutation tests"],"prefix":"10.1093","volume":"36","author":[{"given":"Markus","family":"Ekvall","sequence":"first","affiliation":[{"name":"Science for Life Laboratory, School of Engineering Sciences in Chemistry, Biotechnology and Health, KTH \u2013 Royal Institute of Technology , 171 21 Solna, Sweden"}]},{"given":"Michael","family":"H\u00f6hle","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stockholm University , 106 91 Stockholm, Sweden"}]},{"given":"Lukas","family":"K\u00e4ll","sequence":"additional","affiliation":[{"name":"Science for Life Laboratory, School of Engineering Sciences in Chemistry, Biotechnology and Health, KTH \u2013 Royal Institute of Technology , 171 21 Solna, Sweden"}]}],"member":"286","published-online":{"date-parts":[[2020,12,8]]},"reference":[{"key":"2023062707102863000_btaa1007-B1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1186\/1471-2105-9-309","article-title":"Presto: rapid calculation of order statistic distributions and multiple-testing adjusted p-values via permutation for one and two-stage genetic association studies","volume":"9","author":"Browning","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023062707102863000_btaa1007-B2","doi-asserted-by":"crossref","first-page":"1910","DOI":"10.1016\/j.procs.2012.04.209","article-title":"Cuda: compiling and optimizing for a GPU platform","volume":"9","author":"Chakrabarti","year":"2012","journal-title":"Procedia Comput. Sci"},{"key":"2023062707102863000_btaa1007-B3","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1093\/genetics\/142.1.285","article-title":"Permutation tests for multiple loci affecting a quantitative character","volume":"142","author":"Doerge","year":"1996","journal-title":"Genetics"},{"key":"2023062707102863000_btaa1007-B4","first-page":"227","article-title":"Estimation of significance thresholds for genomewide association scans","volume":"32","author":"Dudbridge","year":"2008","journal-title":"Genet. Epidemiol. Off. Public. Int. Genet. Epidemiol. Soc"},{"key":"2023062707102863000_btaa1007-B5","volume-title":"Large-Scale Inference: Empirical Bayes Methods for Estimation, Testing, and Prediction","author":"Efron","year":"2012"},{"key":"2023062707102863000_btaa1007-B6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/09-SS051","article-title":"Wilcoxon-Mann-Whitney or t-test? On assumptions for hypothesis tests and multiple interpretations of decision rules","volume":"4","author":"Fay","year":"2010","journal-title":"Stat. Surv"},{"key":"2023062707102863000_btaa1007-B7","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF02925373","article-title":"Permutation tests \u2013 a revival?","volume":"39","author":"Gebhard","year":"1998","journal-title":"Stat. Papers"},{"key":"2023062707102863000_btaa1007-B8","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1080\/00031305.1977.10479192","article-title":"A practical interactive program for randomization tests of location","volume":"31","author":"Green","year":"1977","journal-title":"Am. Stat"},{"key":"2023062707102863000_btaa1007-B9","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1198\/000313006X118430","article-title":"A Lego system for conditional inference","volume":"60","author":"Hothorn","year":"2006","journal-title":"Am. Stat"},{"key":"2023062707102863000_btaa1007-B10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v028.i08","article-title":"Implementing a class of permutation tests: the coin package","volume":"28","author":"Hothorn","year":"2008","journal-title":"J. Stat. Softw"},{"key":"2023062707102863000_btaa1007-B11","doi-asserted-by":"crossref","first-page":"2244","DOI":"10.1093\/bioinformatics\/btl383","article-title":"To permute or not to permute","volume":"22","author":"Huang","year":"2006","journal-title":"Bioinformatics"},{"key":"2023062707102863000_btaa1007-B12","doi-asserted-by":"crossref","first-page":"e0206864","DOI":"10.1371\/journal.pone.0206864","article-title":"A simple null model for inferences from network enrichment analysis","volume":"13","author":"Jeuken","year":"2018","journal-title":"PLoS One"},{"key":"2023062707102863000_btaa1007-B13","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1038\/nature18003","article-title":"Proteogenomics connects somatic mutations to signalling in breast cancer","volume":"534","author":"Mertins","year":"2016","journal-title":"Nature"},{"key":"2023062707102863000_btaa1007-B14","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1198\/000313008X332421","article-title":"P-values are random variables","volume":"62","author":"Murdoch","year":"2008","journal-title":"Am. Stat"},{"key":"2023062707102863000_btaa1007-B15","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1080\/01621459.1983.10477990","article-title":"On obtaining permutation distributions in polynomial time","volume":"78","author":"Pagano","year":"1983","journal-title":"J. Am. Stat. Assoc"},{"key":"2023062707102863000_btaa1007-B16","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1086\/519795","article-title":"PLINK: a tool set for whole-genome association and population-based linkage analyses","volume":"81","author":"Purcell","year":"2007","journal-title":"Am. J. Hum. Genet"},{"key":"2023062707102863000_btaa1007-B17","doi-asserted-by":"crossref","first-page":"103","DOI":"10.2307\/3315826","article-title":"Practicing safe statistics with the mid-p","volume":"22","author":"Routledge","year":"1994","journal-title":"Can. J. Stat"},{"key":"2023062707102863000_btaa1007-B18","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1111\/biom.12731","article-title":"Fast approximation of small p-values in permutation tests by partitioning the permutations","volume":"74","author":"Segal","year":"2018","journal-title":"Biometrics"},{"key":"2023062707102863000_btaa1007-B19","doi-asserted-by":"crossref","first-page":"9440","DOI":"10.1073\/pnas.1530509100","article-title":"Statistical significance for genomewide studies","volume":"100","author":"Storey","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023062707102863000_btaa1007-B20","doi-asserted-by":"crossref","first-page":"15545","DOI":"10.1073\/pnas.0506580102","article-title":"Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles","volume":"102","author":"Subramanian","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023062707102863000_btaa1007-B21","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1016\/j.ajhg.2015.04.012","article-title":"Accurate and fast multiple-testing correction in EQTL studies","volume":"96","author":"Sul","year":"2015","journal-title":"Am. J. Hum. Genet"},{"key":"2023062707102863000_btaa1007-B22","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1002\/bimj.4710270414","article-title":"Exact calculation of permutational distributions for two independent samples","volume":"4","author":"Zimmermann","year":"1985","journal-title":"Biometrical J"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa1007\/35434106\/btaa1007.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/22-23\/5392\/50716552\/btaa1007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/22-23\/5392\/50716552\/btaa1007.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T15:12:22Z","timestamp":1723907542000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/22-23\/5392\/6026959"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":22,"journal-issue":{"issue":"22-23","published-print":{"date-parts":[[2021,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa1007","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.10.01.321828","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12,1]]},"published":{"date-parts":[[2020,12,1]]}}}