Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents



ID: 595922.0, MPI für biologische Kybernetik / Biologische Kybernetik
Two-locus association mapping in subquadratic time
Authors:Achlioptas, P; Schölkopf, B; Borgwardt, K
Place of Publication:San Diego, CA, USA
Date of Publication (YYYY-MM-DD):2011-08-01
Title of Proceedings:17th ACM SIGKKD Conference on Knowledge Discovery and Data Mining (KDD 2011)
Start Page:726
End Page:734
Physical Description:8
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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 1010 to 1014 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 n3/2. As a result, our algorithm can easily cope with n ~ 107, i.e., it can efficiently search all pairs of SNPs in the human genome.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/NWG Borgwardt
MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
Identifiers:LOCALID:Borgwardt2011
URL:http://www.kyb.tuebingen.mpg.de/
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.