Fast genotyping of known SNPs through approximate k -mer matching

Ariya Shajii, Deniz Yörükoğlu, Yun William Yu, Bonnie BergerbioRxiv 2016 · DOI

TL;DR

This paper introduces LAVA, a novel algorithm that significantly speeds up the process of genotyping known Single Nucleotide Polymorphisms (SNPs) from next-generation sequencing (NGS) data. By leveraging approximate k-mer matching, LAVA bypasses the computationally expensive read mapping step, achieving up to an order of magnitude faster genotyping with comparable or even improved accuracy, while using substantially less memory.

What Problem Does This Paper Address?

Genotyping, the process of identifying genetic variations within an individual's genome, is a cornerstone of many genomic studies, from understanding genetic traits to population-level analyses like Genome-Wide Association Studies (GWAS). Traditionally, genotyping known SNPs relied on physical SNP arrays. However, with the explosion of NGS data, researchers are increasingly turning to sequencing for its comprehensive coverage. Existing NGS genotyping pipelines typically involve a multi-step process: first, mapping each short sequencing read to a reference genome, and then calling variants based on these alignments. This read mapping step is a major computational bottleneck, consuming significant time and resources. While alignment-free methods exist, they often sacrifice accuracy or are not optimized for the specific task of genotyping known variants. This paper addresses the need for a faster, more efficient, and scalable method for genotyping a predefined set of SNPs from NGS data, without the overhead of full read alignment.

Methods

LAVA (Lightweight Assignment of Variant Alleles) introduces a novel approach that replaces the traditional read mapping and variant calling stages with a unified k-mer based strategy. The core idea is to use "mid-size" k-mers (specifically, k=32) to uniquely identify genomic locations associated with SNPs.

Here's a breakdown of the LAVA method:

  • Preprocessing:
    • Reference Dictionary: LAVA first creates a dictionary of all unique 32-mers found in the reference genome, mapping each k-mer to its genomic position(s).
  • SNP Dictionary: It then constructs a second dictionary containing k-mers that specifically represent the alternate allele of the known SNPs of interest. This dictionary also stores SNP-specific information like allele frequencies.
  • These dictionaries are optimized for fast querying using a static hash table implementation.
  • Online Processing (Genotyping):
    • K-mer Extraction: Each sequencing read is broken down into overlapping 32-mers.
  • Approximate Matching: Instead of aligning the read, LAVA queries its k-mers (and their "Hamming neighbors" – k-mers with up to one base difference) against the reference and SNP dictionaries. This approximate matching allows for tolerance of sequencing errors.
  • Pileup Table: Based on the k-mer matches, LAVA determines which SNP(s) a read likely overlaps and updates a "pileup table" by incrementing counts for either the reference or alternate allele for that SNP.
  • Variant Calling: Finally, a probabilistic model (based on Hardy-Weinberg equilibrium and observed allele counts) is used to call the genotype (homozygous reference, heterozygous, or homozygous alternate) for each SNP.

This approach bypasses the need for full read alignment, treating k-mers as computational analogues of SNP probes on microarrays.

Datasets

The authors evaluated LAVA using the following datasets:

  • Reference Genome: GRCh37/hg19.
  • Sequencing Reads: NA12878 reads from Phase 1 of the 1000 Genomes Project.
  • Gold Standard: A high-quality trio-validated genotype annotation.
  • SNP Lists:
    • A subset of common SNPs from dbSNP.
  • SNPs from the Affymetrix Genome-Wide Human SNP Array 6.0.

The paper does not introduce new benchmark datasets but rather uses established ones for comparison with existing pipelines.

Key Insights and Ideas

  • K-mer Power for Genotyping: The central insight is that mid-size k-mers (k=32) are sufficiently unique in the human genome to act as reliable identifiers for specific SNP loci, even with approximate matching to account for sequencing errors. This allows for a significant departure from traditional alignment-based methods.
  • Alignment-Free Genotyping is Feasible and Efficient: LAVA demonstrates that it's possible to achieve high accuracy in genotyping known SNPs without the computationally intensive step of full read alignment. This "alignment-free" approach is key to its speedup.
  • Trade-off Between Memory and Speed: LAVA offers flexibility, allowing users to tune memory usage. A "LAVA Lite" version significantly reduces RAM requirements by optimizing dictionary storage, albeit with a slight increase in runtime.
  • Computational SNP Arrays: LAVA effectively simulates the functionality of physical SNP arrays but in a purely computational manner, offering greater flexibility in terms of the number of SNPs that can be analyzed and the ease of updating SNP lists.

Key Results

  • Speed: LAVA achieved significant speedups compared to standard genotyping pipelines:
  • 3.4-6.0x faster for the dbSNP-common SNP list.
  • 2.2-9.2x faster for the Affymetrix SNP Array 6.0 list.
  • Even when compared to variant calling from pre-aligned BAM files, LAVA provided substantial speed improvements.
  • Accuracy:
    • LAVA correctly called 93.1% of dbSNP-common SNPs and 96.4% of Affymetrix SNPs.
  • For the Affymetrix SNP list, LAVA achieved the highest SNP calling accuracy among the tested pipelines.
  • Memory Usage: LAVA demonstrated impressive memory efficiency, particularly in its "Lite" mode, using as little as ~5GB of RAM for the Affymetrix SNP list, compared to other pipelines that could use significantly more.
  • Parallelization: LAVA is straightforward to parallelize, achieving a 3.3x speedup with 4 threads, comparable to the speedup achieved by parallelized traditional pipelines.

Limitations and Future Work

  • Limitations:
    • LAVA, in its current implementation, discards reads containing 'N' bases.
  • It also discards segments at the end of reads that are not fully covered by k-mers, which can be up to 5 bases for their read length of 101 bp.
  • A small subset of SNPs cannot be uniquely identified by any of their overlapping 32-mers, leading LAVA to attempt genotyping on slightly fewer SNPs than are present in the list (e.g., 94.5% of dbSNP-common and 98.5% of Affymetrix SNPs).
  • Future Work:
    • Paired-End Reads: Incorporating a specific mode for paired-end reads to further improve accuracy.
  • Other Variant Types: Extending LAVA to genotype other variant types like insertions, deletions (indels), and copy number variations (CNVs), which are analogous to SNPs in the k-mer framework.
  • RNA-Seq Integration: Augmenting LAVA for RNA-seq data to identify SNP/indel variants and estimate differential allelic expression.
  • Advanced Probabilistic Models: Exploring more complex probabilistic models (similar to GATK HaplotypeCaller) and incorporating linkage disequilibrium information for potentially higher accuracy, while acknowledging the trade-off with speed.

Summary updated

Abstract

Abstract Motivation As the volume of next-generation sequencing (NGS) data increases, faster algorithms become necessary. Although speeding up individual components of a sequence analysis pipeline (e.g. read mapping) can reduce the computational cost of analysis, such approaches do not take full advantage of the particulars of a given problem. One problem of great interest, genotyping a known set of variants (e.g. dbSNP or Affymetrix SNPs), is important for characterization of known genetic traits and causative disease variants within an individual, as well as the initial stage of many ancestral and population genomic pipelines (e.g. GWAS). Results We introduce LAVA (Lightweight Assignment of Variant Alleles), an NGS-based genotyping algorithm for a given set of SNP loci, which takes advantage of the fact that approximate matching of mid-size k -mers (with k = 32) can typically uniquely identify loci in the human genome without full read alignment. LAVA accurately calls the vast majority of SNPs in dbSNP and Affymetrix’s Genome-Wide Human SNP Array 6.0 up to about an order of magnitude faster than standard NGS genotyping pipelines. For Affymetrix SNPs, LAVA has significantly higher SNP calling accuracy than existing pipelines while using as low as ~5GB of RAM. As such, LAVA represents a scalable computational method for population-level genotyping studies as well as a flexible NGS-based replacement for SNP arrays. Availability LAVA software is available at http://lava.csail.mit.edu . Contact [email protected] Supplementary information Supplementary data are available at Bioinformatics online.
BibTeX
@misc{shajii2016fast,
  author = {Ariya Shajii and Deniz Yörükoğlu and Yun William Yu and Bonnie Berger},
  title = {{Fast genotyping of known SNPs through approximate <i>k</i> -mer matching}},
  year = {2016},
  doi = {10.1101/063446},
  howpublished = {bioRxiv},
}
Figure