  Permutation tests are widely used for statistical hypothesis testing when the
sampling distribution of the test statistic under the null hypothesis is
analytically intractable or unreliable due to finite sample sizes. One critical
challenge in the application of permutation tests in genomic studies is that an
enormous number of permutations are often needed to obtain reliable estimates
of very small $p$-values, leading to intensive computational effort. To address
this issue, we develop algorithms for the accurate and efficient estimation of
small $p$-values in permutation tests for paired and independent two-group
genomic data, and our approaches leverage a novel framework for parameterizing
the permutation sample spaces of those two types of data respectively using the
Bernoulli and conditional Bernoulli distributions, combined with the
cross-entropy method. The performance of our proposed algorithms is
demonstrated through the application to two simulated datasets and two
real-world gene expression datasets generated by microarray and RNA-Seq
technologies and comparisons to existing methods such as crude permutations and
SAMC, and the results show that our approaches can achieve orders of magnitude
of computational efficiency gains in estimating small $p$-values. Our
approaches offer promising solutions for the improvement of computational
efficiencies of existing permutation test procedures and the development of new
testing methods using permutations in genomic data analysis.
