Source-linked AI summary
Matrix eQTL: Ultra fast eQTL analysis via large matrix operations
Andrey A. Shabalin
TL;DR
Large eQTL datasets require enormous numbers of transcript-SNP tests, creating a computational bottleneck. Matrix eQTL uses fast matrix-based linear-model testing with covariates and extended error models, and the authors report analyses that previously took days or weeks can run in minutes.
Problem
Modern eQTL datasets make exhaustive transcript-SNP association testing computationally demanding, with complete analyses potentially involving over ten billion tests.
Method
Matrix eQTL uses matrix operations to test transcript-SNP associations with linear regression or ANOVA models, including covariates and extended error structures.
Results
Matrix eQTL was hundreds to thousands of times faster than five existing eQTL methods in the authors’ comparison.
Takeaways & Limitations
The method enables large-dataset eQTL analysis and comparison of multiple models, preprocessing procedures, and permutation-based significance thresholds on a desktop machine.
Takeaways & Limitations
The current method does not yet cover planned extensions such as multi-SNP and generalized linear models, while future GPU support is proposed.
Abstract
from arXiv · showhide
Expression quantitative trait loci (eQTL) mapping aims to determine genomic regions that regulate gene transcription. Expression QTL is used to study the regulatory structure of normal tissues and to search for genetic factors in complex diseases such as cancer, diabetes, and cystic fibrosis. A modern eQTL dataset contains millions of SNPs and thousands of transcripts measured for hundreds of samples. This makes the analysis computationally complex as it involves independent testing for association for every transcript-SNP pair. The heavy computational burden makes eQTL analysis less popular, often forces analysts to restrict their attention to just a subset of transcripts and SNPs. As larger genotype and gene expression datasets become available, the demand for fast tools for eQTL analysis increases. We present a new method for fast eQTL analysis via linear models, called Matrix eQTL. Matrix eQTL can model and test for association using both linear regression and ANOVA models. The models can include covariates to account for such factors as population structure, gender, and clinical variables. It also supports testing of heteroscedastic models and models with correlated errors. In our experiment on large datasets Matrix eQTL was thousands of times faster than the existing popular software for QTL/eQTL analysis. Matrix eQTL is implemented as both Matlab and R packages and thus can easily be run on Windows, Mac OS, and Linux systems. The software is freely available at the following address: http://www.bios.unc.edu/research/genomic_software/Matrix_eQTL
Introduction.
eQTL analysis must test vast numbers of transcript-SNP associations, motivating Matrix eQTL’s fast linear-model approach for large datasets. It uses matrix operations and supports covariates and several extended error models.
- Motivation: Modern eQTL datasets can contain millions of SNPs, thousands of transcripts, and hundreds of samples, making exhaustive association testing computationally intensive.The paper focuses on independent testing of each transcript-SNP pair rather than jointly modeling multiple SNPs.
- Method: Matrix eQTL performs independent transcript-SNP testing with least squares regression or ANOVA models.Both model types can include additive covariates for population structure, gender, and clinical variables.
- Method: Matrix eQTL supports weighted least squares, correlated-error models, and mixed-effects models with known variance parameters.These extensions broaden the supported linear-model settings beyond the basic regression and ANOVA formulations.
- Method: A special algorithm and preprocessing avoid estimating all model parameters, expressing the intensive computation through large matrix operations.The implementations rely on efficient matrix multiplication in R and Matlab.
- Implementation: Matrix eQTL runs on Linux, Mac OS X, and Windows through independent Matlab and R implementations with equal functionality.Performance may differ according to the Matlab or R version used.
Results.
The evaluation compares Matrix eQTL with five existing QTL/eQTL programs on cystic-fibrosis genotype and expression data. Matrix eQTL completes analyses that previously took days or weeks in minutes and supports rapid comparison of alternative models and preprocessing choices.
- Data: 840 patients contributed genotype data for 573,337 markers and expression measurements for 22,011 transcripts in the cystic-fibrosis dataset.Missing values were imputed using the variable’s average across samples.
- Performance comparison: Five existing programs—Plink, Merlin, R/qtl, eMap, and FastMap—were used as performance comparators.The tools differ in design, including pedigree analysis, general association analysis, R-based QTL analysis, and permutation-focused testing.
- Performance comparison: The first four existing methods were projected from a random subset of 2,000 genes and 2,000 SNPs, while Matrix eQTL was timed on the complete dataset.The table caption specifies the projection basis for the first four methods.
- Results: Matrix eQTL can perform analyses that previously required days or weeks in just minutes.This result is reported for the large-data eQTL analyses discussed in the Results section.
- Results: Matrix eQTL lets analysts fit and compare varied covariate models in less than an hour and evaluate alternative preprocessing and quality-control procedures.It can also determine permutation-based significance thresholds faster than most packages generate nominal p-values.
Methods.
Matrix eQTL accelerates independent transcript–SNP testing by reducing linear-model calculations to large matrix operations, block processing, and threshold-based evaluation. The framework also extends to covariates, ANOVA, and non-i.i.d. error models.
- Models: Linear regression models genotype as a 0, 1, or 2 allele count, while ANOVA treats genotype categorically through two dummy variables and tests their joint significance.For ANOVA, orthogonalization enables an efficient R^2-based test statistic and corresponding F-test thresholds.
- Algorithm: Matrix eQTL targets significant transcript-SNP pairs while skipping unnecessary parameter estimation and initially calculating p-values only for associations exceeding a test-statistic threshold.This focuses computation on efficient test-statistic calculations and significant pairs.
- Algorithm: For simple linear regression, standardized genotype and expression matrices yield all gene-SNP correlations through one matrix multiplication, computed in blocks of up to 10,000 variables.Block processing limits memory requirements for correlation matrices involving tens of billions of tests.
- Algorithm: The simple-regression workflow splits and standardizes input matrices, computes each block’s correlations, filters by an absolute-correlation threshold, and then calculates statistics and p-values for retained pairs.The workflow is organized around blockwise matrix operations followed by selective statistical evaluation.
- Models: Covariates are handled by centering and orthogonalizing genotype and expression with respect to the covariate before applying simple regression with one fewer degree of freedom.The approach supports covariates such as population structure, gender, age, and clinical variables.
- Models: For heteroskedastic or correlated errors, Matrix eQTL assumes a known covariance matrix, transforms variables to obtain i.i.d. errors, and applies the covariate-model algorithm without centering.The transformed model is homoskedastic and has independent errors but omits a constant.
Grant Support
The work received support from multiple U.S. government agencies and the Gillings Innovation Laboratory in Statistical Genomics. The funders had no role in the study or publication process.
- Grant Support: Funding came from the National Institutes of Health, U.S. Environmental Protection Agency, National Cancer Institute, National Institute of Mental Health, and Gillings Innovation Laboratory in Statistical Genomics.The passage lists the specific grant identifiers for the government-funded support.
- Grant Support: The funders had no role in study design, data collection and analysis, publication decisions, or manuscript preparation.
Conclusion
Matrix eQTL provides fast transcript-SNP association testing across several linear-model extensions and was hundreds to thousands of times faster than five existing methods. Its speed supports large analyses on desktop computers, while future work targets GPU acceleration and more complex models.
- Conclusion: Matrix eQTL tests transcript-SNP associations with linear regression and ANOVA models, including covariates and heteroskedastic or correlated errors.
- Conclusion: Matrix eQTL was hundreds to thousands of times faster than five existing eQTL methods.
- Conclusion: Matrix eQTL enables large-dataset eQTL analysis on a single desktop machine in the time other methods would require on a computing cluster.The implementation is available in Matlab and R, with publicly available code.
- Future work: Future versions are planned to target GPU computation and faster estimation of complex models such as multi-SNP and generalized linear models.The authors estimate that a GPU version could provide at least a tenfold performance increase.
Appendix.
The appendix examines the computational basis of Matrix eQTL, focusing on large-matrix multiplication and its practical performance across software and hardware. It also situates direct multiplication among asymptotically faster methods and reports the test environment.
- Matrix Multiplication: Matrix eQTL expresses its most computationally intensive operations as large matrix multiplications, making linear-algebra performance central to runtime.The tested operation multiplies two 4,096x4,096 matrices with uniformly distributed random elements.
- Matrix Multiplication: 90 seconds and 80 seconds were required by standard 32-bit and 64-bit R installations, while R with C2D ATLAS completed the same multiplication in 15 seconds.The standard R installation used a generic, non-CPU-specific BLAS; ATLAS provided a faster BLAS implementation.
- Matrix Multiplication: The NVIDIA GTX 480 GPU offered ten times better performance than the best CPU algorithm tested.Single-precision calculations were not used in Matrix eQTL because of potential accuracy loss, and they are unavailable in R.
- Matrix Multiplication: Direct multiplication of square n × n matrices has complexity O(n^3), although more asymptotically efficient algorithms have also been developed.The cited alternatives include O(n^log2 7) ≈ O(n^2.81) and o(n^2.376).
- Matrix Multiplication: In practice, the newer asymptotically efficient methods do not outperform direct multiplication even for matrices around n ≈ 2000 and may be numerically unstable.This limits their practical advantage despite their lower asymptotic complexity.
- Test Environment: The performance tests used a four-core Intel Xeon X3430 system with 16 GB RAM running Windows 7, Matlab R2010b, and Revolution R Enterprise 4.0.The CPU was specified at 2.4 GHz and 38.4 gigaflops.