Whole genome SNP genotype piecemeal imputation

Yining Wang, Tim Wylie, Paul Stothard, Guohui LinBMC Bioinformatics 2015 · DOI

TL;DR

This paper introduces "piecemeal imputation," a novel two-step approach to accurately impute missing single nucleotide polymorphism (SNP) genotypes in whole genomes. By constructing intermediate "pseudo-arrays" of informative SNPs, this method significantly improves imputation accuracy compared to traditional one-step methods, making whole-genome association studies more feasible and cost-effective.

What Problem Does This Paper Address?

Genome-wide association studies (GWAS) are crucial for identifying genetic variants linked to traits. These studies rely on abundant and well-distributed genetic markers, primarily single nucleotide polymorphisms (SNPs). While sequencing entire genomes is becoming cheaper, it remains prohibitively expensive for large cohorts. Consequently, researchers often use commercial SNP genotyping arrays, which capture only a fraction of the millions of SNPs present in the genome. This leaves a large number of SNPs "untyped."

SNP imputation aims to computationally infer these missing genotypes. While existing methods are effective for filling small gaps within genotyped arrays, this paper tackles a more ambitious goal: imputing the vast majority of untyped SNPs across the entire genome, using a lower-density genotyped set and a high-density reference panel (often whole-genome sequence data). The challenge lies in achieving high accuracy for this massive imputation task, as traditional one-step imputation methods struggle with the sheer scale and density differences. The paper builds on prior work suggesting that two-step imputation (low-density to medium-density, then to high-density) can improve accuracy, but proposes a more sophisticated, "piecemeal" approach to construct optimal intermediate steps.

Methods

The core innovation is the piecemeal imputation framework. This is a two-step process:

  1. Training Phase (5-fold Cross-Validation):
    • Add-one Two-Step Imputation: For each untyped SNP (from the higher density set, denoted as $U$) and a lower density set ($T$), the method evaluates the potential of each SNP in $U$ to improve imputation accuracy. This is done by temporarily adding one SNP from $U$ to $T$ to form an intermediate set ($T \cup \{m_i\}$) and then imputing the rest of $U$ to $T \cup \{m_i\}$. The accuracy of this two-step process is compared to a direct one-step imputation from $T$ to $U$.
  2. Feature Vector Creation: For each SNP $m_i \in U$, a "feature vector" is created, capturing its performance across all untyped SNPs in the add-one imputation.
  3. Marker Clustering: These feature vectors are then clustered using k-means. The idea is that SNPs with similar feature vectors have similar imputation potentials, allowing for redundancy reduction.
  4. Target Marker Cluster Identification: Within each cluster, a "target marker cluster" ($TC_i$) is identified, containing SNPs that can be well imputed by the SNPs in that cluster.
  5. Pseudo-Array Construction: From each cluster, a representative SNP ($m_i^*$) is selected to form a "pseudo intermediate array" ($T \cup \{m_i^*\}$). This pseudo-array is not a physical chip but a computationally derived set of markers.
  6. Imputation Phase (Independent Testing):
    • The study samples (genotyped on the lower density chip $T$) are first imputed using the constructed pseudo-array ($T \cup \{m_i^*\}$).
  7. This imputed data is then used to impute the remaining untyped SNPs in $U$.
  8. The final imputed genotypes are compared to the true genotypes to calculate accuracy.

This "piecemeal" aspect refers to breaking down the imputation of the entire set $U$ into smaller, manageable "pieces" (target marker clusters), each imputed using a selected representative marker.

Datasets

The study utilizes two main types of datasets:

  • Sequenced Animals (Reference Panels):
    • Holstein sequence collection: 114 animals.
  • Simmental sequence collection: 82 animals. These datasets provide the "ground truth" for whole-genome genotypes.

  • Genotyped Animals (Study Samples):

    • Affymetrix 660K genotypes: 390 Simmental animals.
  • Illumina 777K chip (BovineHD): Used for Holstein animals.
  • Lower density chips: Illumina 6K (BovineLD) and 50K (BovineSNP50) were also used.

The paper uses chromosome 14 (BTA 14) for Simmental data and chromosome 27 (BTA 27) for Holstein data. The study also leverages data from the 1000 Bull Genomes Project.

Key Insights and Ideas

  • The Power of Intermediate Steps: The fundamental insight is that a single, direct imputation from a very low-density chip to a whole genome is less accurate than a multi-step approach. The "piecemeal" strategy formalizes this by intelligently constructing intermediate "pseudo-arrays" that act as stepping stones.
  • Informative SNP Selection is Key: Not all SNPs are created equal for imputation. The "add-one" imputation evaluation and subsequent clustering effectively identify the most informative SNPs to include in these intermediate pseudo-arrays, maximizing their utility.
  • Clustering for Efficiency and Robustness: Clustering SNPs based on their imputation potential helps reduce redundancy and makes the process more robust. It ensures that even if one representative marker isn't perfect, the overall imputation for that "piece" remains strong.
  • "Piecemeal" as a Scalable Strategy: The piecemeal approach breaks down the massive imputation task into smaller, more manageable imputation problems, making it computationally feasible for whole-genome imputation.
  • Breed-Specific Imputation: The authors found that inter-breed imputation is less accurate, supporting the idea that imputation should ideally be performed within breeds.

Key Results

  • Consistent Accuracy Improvement: The piecemeal imputation method consistently achieved higher imputation accuracies compared to classic one-step imputation.
  • For Simmental data using Beagle, improvements ranged from 1.46% to 2.55% in 5-fold cross-validation and 0.71% to 1.76% in independent testing.
  • For Holstein data using Beagle, improvements were around 2.07% to 2.92% in 5-fold cross-validation and 1.94% to 1.97% in independent testing.
  • Beagle vs. FImpute: While both Beagle and FImpute were used as base imputation programs, Beagle generally showed more significant improvements with the piecemeal approach, especially in cross-validation. FImpute showed smaller, sometimes statistically insignificant, improvements.
  • Multi-Step Imputation Benefits: The paper demonstrated that even standard multi-step imputation (e.g., 6K -> 50K -> HD) benefits from the piecemeal strategy, showing accuracy improvements over classic multi-step methods.
  • Computational Cost: While the training phase can be computationally intensive and require significant disk storage (over 3TB for intermediate data), the imputation phase itself is efficient. The authors argue this is a worthwhile trade-off for the accuracy gains.

Limitations and Future Work

  • Computational Burden of Training: The primary limitation acknowledged is the computational cost and disk space required for the training phase, especially for whole-genome imputation.
  • Clustering Method Choice: While k-means was used for clustering, the authors suggest that other bi-clustering algorithms might be worth exploring for potentially better results.
  • LD-Based Approaches: The paper briefly mentions exploring LD-based marker selection (e.g., using Haploview) as a faster alternative to the add-one imputation training, but it did not yield conclusive accuracy increases. Future work could focus on better LD block estimation for faster imputation.
  • Relatedness: The current empirical experiments used population-based imputation, assuming unrelated individuals. The authors suggest that defining relatedness and using only closely related sequenced animals as references could lead to more accurate imputation.
  • Inter-Breed Imputation: While the study separated breeds, further investigation into optimizing inter-breed imputation could be valuable.

Summary updated

BibTeX
@article{wang2015whole,
  author = {Yining Wang and Tim Wylie and Paul Stothard and Guohui Lin},
  title = {{Whole genome SNP genotype piecemeal imputation}},
  journal = {BMC Bioinformatics},
  year = {2015},
  doi = {10.1186/s12859-015-0770-2},
}
Figure