P. Achlioptas, B. Schoelkopf, K. Borgwardt, Two-Locus Association Mapping in Subquadratic Time, ACM SIGKDD, 2011.

Abstract:

Genome-wide association studies (GWAS) have not been able to discover strong associations between many complex human diseases and single genetic loci. Mapping these phenotypes to pairs of genetic loci is hindered by the huge number of candidates leading to enormous computational and statistical problems. In GWAS on single nucleotide poly- morphisms (SNPs), one has to consider in the order of 10^10 to 10^14 pairs, which is infeasible in practice. In this article, we give the first algorithm for 2-locus genome-wide association studies that is subquadratic in the number of SNPs.

Bibtex: 

@article{asb-tamst-11,
author = {Achlioptas,  Panos and Schoelkopf, Bernhard and Borgwardt, Karsten},
year = {2011},
title = {Two-Locus Association Mapping in Subquadratic Time},
journal = {SIGKDD},
}