BioQC Algorithm: Speeding up the Wilcoxon-Mann-Whitney Test

Algorithmic improvements

The Wilcoxon-Mann-Whitney (WMW) test is a non-parametric statistical test to test if median values of two population are equal or not. Unlike the t-test, it does not require the assumption of normal distributions, which makes it more robust against noise.

We improved the computational efficiency of the Wilcoxon-Mann-Whitney test in comparison to the native R implementation based on three modifications:

1. The approximative WMW-statistic (Zar, J. H. (1999). Biostatistical analysis. Pearson Education India. pp. 174-177) is used. The differences to the exact version are negligible for high-throughput gene expression data.
2. The core algorithm is implemented in C instead of R as programming language.
3. BioQC avoids futile expensive sorting operations.

While (1) and (2) are straightforward, we elaborate (3) in the following.

Let \(W_{a,b}\) be the approximative WMW test of two gene vectors \(a,b\), where \(a\) is the gene set of interest, typically containing less than a few hundreds of genes, and \(b\) is the set of all genes outside the gene set (background genes) typically containing \(>10000\) genes. In the context of BioQC, the gene sets are referred to as tissue signatures.

Given an \(m \times n\) input matrix of gene expression data with \(m\) genes and \(n\) samples \(s_1, \dots, s_n\), and \(k\) gene sets \(d_1, \dots, d_k\), the WMW-test needs to be applied for each sample \(s_i, i \in 1..n\) and each gene set \(d_j, j \in 1..k\). The runtime of the WMW-test is essentially determined by the sorting operation on the two input vectors. Using native R wilcox.test, the vectors \(a\) and \(b\) are sorted individually for each gene set. However, in the context of gene set analysis, this is futile, as the (large) background set changes insignificantly in relation to the (small) gene set, when testing different gene sets on the same sample.

Therefore, we approximate the WMW-test by extending \(b\) to all genes in the sample, keeping the background unchanged when testing multiple gene sets. Like this, \(b\) has to be sorted only once per sample. The individual gene sets still need to be sorted, which is not a major issue, as they are small in comparison to the set of background genes.

Figure 1: BioQC speeds up the Wilcoxon-Mann-Whitney test by avoiding futile sorting operations on the same sample.

Time benchmark

To demonstrate BioQC’s superior performance, we apply both BioQC and the native R wilcox.test to random expression matrices and measure the runtime.

We setup random expression matrices of 20502 human protein-coding genes of 1, 5, 10, 50, or 100 samples. Genes are \(i.i.d\) distributed following \(\mathcal{N}(0,1)\). The native R and the BioQC implementations of the Wilcoxon-Mann-Whitney test are applied to the matrices respectively.

The numeric results of both implementations, bioqcNumRes (from BioQC) and rNumRes (from R), are equivalent, as shown by the next command.

expect_equal(bioqcNumRes, rNumRes)

The BioQC implementation is more than 500 times faster: while it takes about one second for BioQC to calculate enrichment scores of all 155 signatures in 100 samples, the native R implementation takes about 20 minutes:

Figure 2: Time benchmark results of BioQC and R implementation of Wilcoxon-Mann-Whitney test. Left panel: elapsed time in seconds (logarithmic Y-axis). Right panel: ratio of elapsed time by two implementations. All results achieved by a single thread on in a RedHat Linux server.

Conclusion

We have shown that BioQC achieves identical results as the native implementation in two orders of magnitude less time. This renders BioQC a highly efficient tool for quality control of large-scale high-throughput gene expression data.

R Session Info

sessionInfo()

## R version 3.4.2 (2017-09-28)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.3 LTS
## 
## Matrix products: default
## BLAS: /home/biocbuild/bbs-3.6-bioc/R/lib/libRblas.so
## LAPACK: /home/biocbuild/bbs-3.6-bioc/R/lib/libRlapack.so
## 
## locale:
##  [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=en_US.UTF-8        LC_COLLATE=C              
##  [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
##  [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       
## 
## attached base packages:
## [1] stats4    parallel  stats     graphics  grDevices utils     datasets 
## [8] methods   base     
## 
## other attached packages:
##  [1] rbenchmark_1.0.0     gplots_3.0.1         gridExtra_2.3       
##  [4] latticeExtra_0.6-28  RColorBrewer_1.1-2   lattice_0.20-35     
##  [7] hgu133plus2.db_3.2.3 org.Hs.eg.db_3.4.2   AnnotationDbi_1.40.0
## [10] IRanges_2.12.0       S4Vectors_0.16.0     BioQC_1.6.0         
## [13] Biobase_2.38.0       BiocGenerics_0.24.0  Rcpp_0.12.13        
## [16] testthat_1.0.2       knitr_1.17          
## 
## loaded via a namespace (and not attached):
##  [1] highr_0.6          compiler_3.4.2     bitops_1.0-6      
##  [4] tools_3.4.2        digest_0.6.12      bit_1.1-12        
##  [7] gtable_0.2.0       RSQLite_2.0        evaluate_0.10.1   
## [10] memoise_1.1.0      tibble_1.3.4       pkgconfig_2.0.1   
## [13] rlang_0.1.2        DBI_0.7            yaml_2.1.14       
## [16] stringr_1.2.0      caTools_1.17.1     gtools_3.5.0      
## [19] rprojroot_1.2      bit64_0.9-7        grid_3.4.2        
## [22] R6_2.2.2           rmarkdown_1.6      gdata_2.18.0      
## [25] blob_1.1.0         magrittr_1.5       backports_1.1.1   
## [28] htmltools_0.3.6    KernSmooth_2.23-15 stringi_1.1.5     
## [31] crayon_1.3.4