LAVA

massachusetts institute of technology (mit)
computer science and artificial intelligence laboratory (csail)
theory of computation group (toc)
computation and biology group (compbio)

email queries bab@mit.edu

LAVA (Lightweight Assignment of Variant Alleles) is an NGS-based genotyping algorithm for a given set of SNP loci, which takes advantage of the fact that inexact 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, while performing 4-9 times faster than a standard NGS genotyping pipeline and optionally using as little as 5.2 GB 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.

Source code is available on GitHub.

Ariya Shajii, Deniz Yorukoglu, Yun William Yu, Bonnie Berger; Fast genotyping of known SNPs through approximate k-mer matching. Bioinformatics 2016; 32(17): i538-i544. doi: 10.1093/bioinformatics/btw460

Supplement Materials

• Reference:
• GRCh37/hg19: hg19.fa.gz
• Reads (NA12878 from 1000 Genomes Project):
  • SRR622461_1.filt.fastq.gz
  • SRR622461_2.filt.fastq.gz
  • SRR622461.filt.fastq.gz
• SNP list (in UCSC's txt-based format):
• dbSNP-142-Common (filtered): SNPs142_hg19_Common.filt.txt
• Affymetrix Genome-Wide Human SNP Array 6.0: Affymetrix_6_SNPs.txt