2011 TwoLocusAssociationMappinginSub

• (Achlioptas et al., 2011) ⇒ Panagiotis Achlioptas, Bernhard Schölkopf, and Karsten Borgwardt. (2011). “Two-locus Association Mapping in Subquadratic Time.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020521

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Two-locus+Association+Mapping+in+Subquadratic+Time
• http://dl.acm.org/citation.cfm?id=2020408.2020521&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; data mining; epistasis detection; experimentation; lightbulb algorithm; measurement; two-locus association mapping

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 polymorphisms (SNPs), one has to consider in the order of 10¹⁰ to 10¹⁴ 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, n, of SNPs. The running time of our algorithm is data-dependent, but large experiments over real genomic data suggest that it scales empirically as n^3/2. As a result, our algorithm can easily cope with n ~ 10⁷, i.e., it can efficiently search all pairs of SNPs in the human genome.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 TwoLocusAssociationMappinginSub	Bernhard Schölkopf Panagiotis Achlioptas Karsten Borgwardt			Two-locus Association Mapping in Subquadratic Time				10.1145/2020408.2020521		2011