Inferring missing genotypes in large SNP panels using fast nearest-neighbor searches over sliding windows.
BACKGROUND
Typical high-throughput genotyping techniques produce numerous missing calls that confound subsequent analyses, such as disease association studies. Common remedies for this problem include removing affected markers and/or samples or, otherwise, imputing the missing data. On small marker sets imputation is frequently based on a vote of the K-nearest-neighbor (KNN) haplotypes, but this technique is neither practical nor justifiable for large datasets.


RESULTS
We describe a data structure that supports efficient KNN queries over arbitrarily sized, sliding haplotype windows, and evaluate its use for genotype imputation. The performance of our method enables exhaustive exploration over all window sizes and known sites in large (150K, 8.3M) SNP panels. We also compare the accuracy and performance of our methods with competing imputation approaches.


BACKGROUND
A free open source software package, NPUTE, is available at http://compgen.unc.edu/software, for non-commercial uses.
Roberts
Adam
A
Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599, USA.
McMillan
Leonard
L
Wang
Wei
W
Parker
Joel
J
Rusyn
Ivan
I
Threadgill
David
D
D000465:Algorithms; D016477:Artifacts; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods*; D014644:Genetic Variation / Q000235:genetics; D010363:Pattern Recognition, Automated / Q000379:methods; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*