Read Mapping Near Non-Volatile Memory
Preprint
Abstract
DNA sequencing is the physical/biochemical process of identifying the location of the four bases (Adenine, Guanine, Cytosine, Thymine) in a DNA strand. As semiconductor technology revolutionized computing, modern DNA sequencing technology (termed Next Generation Sequencing, NGS)revolutionized genomic research. As a result, modern NGS platforms can sequence hundreds of millions of short DNA fragments in parallel. The sequenced DNA fragments, representing the output of NGS platforms, are termed reads. Besides genomic variations, NGS imperfections induce noise in reads. Mapping each read to (the most similar portion of) a reference genome of the same species, i.e., read mapping, is a common critical first step in a diverse set of emerging bioinformatics applications. Mapping represents a search-heavy memory-intensive similarity matching problem, therefore, can greatly benefit from near-memory processing. Intuition suggests using fast associative search enabled by Ternary Content Addressable Memory (TCAM) by construction. However, the excessive energy consumption and lack of support for similarity matching (under NGS and genomic variation induced noise) renders direct application of TCAM infeasible, irrespective of volatility, where only non-volatile TCAM can accommodate the large memory footprint in an area-efficient way. This paper introduces GeNVoM, a scalable, energy-efficient and high-throughput solution. Instead of optimizing an algorithm developed for general-purpose computers or GPUs, GeNVoM rethinks the algorithm and non-volatile TCAM-based accelerator design together from the ground up. Thereby GeNVoM can improve the throughput by up to 113.5 times (3.6); the energy consumption, by up to 210.9 times (1.36), when compared to a GPU (accelerator) baseline, which represents one of the highest-throughput implementations known.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- BreaKmer: detection of structural variation in targeted massively parallel sequencing data using kmersNucleic Acids Research, 2014
- Fast gapped-read alignment with Bowtie 2Nature Methods, 2012
- Small insertions and deletions (INDELs) in human genomesHuman Molecular Genetics, 2010
- Fast and accurate long-read alignment with Burrows–Wheeler transformBioinformatics, 2010
- SOAP2: an improved ultrafast tool for short read alignmentBioinformatics, 2009
- Fast and accurate short read alignment with Burrows–Wheeler transformBioinformatics, 2009
- The diploid genome sequence of an Asian individualNature, 2008
- Mapping short DNA sequencing reads and calling variants using mapping quality scoresGenome Research, 2008
- SOAP: short oligonucleotide alignment programBioinformatics, 2008
- Genomic mapping by fingerprinting random clones: A mathematical analysisGenomics, 1988