title: Inferring missing genotypes in large SNP panels using fast nearest-neighbor searches over sliding windows.
abstract: 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.
authors.affiliation: Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599, USA.
authors.forename: Adam
authors.initials: A
authors.lastname: Roberts
authors.forename: Leonard
authors.initials: L
authors.lastname: McMillan
authors.forename: Wei
authors.initials: W
authors.lastname: Wang
authors.forename: Joel
authors.initials: J
authors.lastname: Parker
authors.forename: Ivan
authors.initials: I
authors.lastname: Rusyn
authors.forename: David
authors.initials: D
authors.lastname: Threadgill
mesh_terms: 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*