PaperlayerView exact revision on arXiv

Source-linked AI summary

GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies

Jeremie S. Kim, Damla Senol Cali, Hongyi Xin, Donghyuk Lee, Saugata Ghose, Mohammed Alser, Hasan Hassan, Oguz Ergin, Can Alkan, Onur Mutlu

arXiv:1711.01177v1q-bio.GNcs.CE

TL;DR

DNA read mapping spends substantial effort filtering candidate locations before expensive sequence alignment. GRIM-Filter combines token-presence metadata with highly parallel processing in 3D-stacked memory to accelerate this step. Compared with prior filtering and mapping approaches, it reports lower false negative rates and faster end-to-end mapping at error tolerance 0.05.

  • Problem

    Seed location filtering is a read-mapping bottleneck because candidate locations must be screened before computationally expensive sequence alignment.

  • Method

    GRIM-Filter represents reference-genome bins with token-existence bitvectors and exploits parallel processing-in-memory in 3D-stacked memory to filter candidate locations.

  • Results

    5.59x–6.41x lower false negative rate and 1.81x–3.65x end-to-end read-mapper speedup are reported at sequence alignment error tolerance 0.05.

  • Takeaways & Limitations

    GRIM-Filter is presented as a general seed location filter that can accelerate hash-table-based read mappers while maintaining high sensitivity and comprehensiveness.

  • Takeaways & Limitations

    Bitvector-generation time is excluded from final runtime results because generation occurs once per reference genome; for the human genome, it takes approximately five minutes under the reported configuration.

Abstract

from arXiv · show

Motivation: Seed location filtering is critical in DNA read mapping, a process where billions of DNA fragments (reads) sampled from a donor are mapped onto a reference genome to identify genomic variants of the donor. State-of-the-art read mappers 1) quickly generate possible mapping locations for seeds (i.e., smaller segments) within each read, 2) extract reference sequences at each of the mapping locations, and 3) check similarity between each read and its associated reference sequences with a computationally-expensive algorithm (i.e., sequence alignment) to determine the origin of the read. A seed location filter comes into play before alignment, discarding seed locations that alignment would deem a poor match. The ideal seed location filter would discard all poor match locations prior to alignment such that there is no wasted computation on unnecessary alignments. Results: We propose a novel seed location filtering algorithm, GRIM-Filter, optimized to exploit 3D-stacked memory systems that integrate computation within a logic layer stacked under memory layers, to perform processing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1) introducing a new representation of coarse-grained segments of the reference genome, and 2) using massively-parallel in-memory operations to identify read presence within each coarse-grained segment. Our evaluations show that for a sequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the false negative rate of filtering by 5.59x--6.41x, and 2) provides an end-to-end read mapper speedup of 1.81x--3.65x, compared to a state-of-the-art read mapper employing the best previous seed location filtering algorithm. Availability: The code is available online at: https://github.com/CMU-SAFARI/GRIM

1 Introduction

Read mapping is a major computational bottleneck in genome analysis, and seed location filtering targets expensive alignments by rapidly discarding poor candidate locations. GRIM-Filter addresses the filtering bottleneck with a PIM-oriented algorithm designed for 3D-stacked memory.

  • Motivation: Read mapping maps identified short DNA reads to a reference genome to analyze genomic variation and forms the pipeline’s third stage.The genome-analysis pipeline also cuts genomes into reads and identifies their sequences before mapping.
  • Read Mapping: Seed-and-extend mappers use seeds to find candidate reference locations, retrieve corresponding sequences, and verify matches using expensive sequence alignment.The mapper performs these operations in five stages, with alignment determining read-to-reference similarity.
  • Filtering Bottleneck: Seed location filters discard candidate locations likely to produce incorrect mappings before sequence alignment, accelerating mapping when filtering costs less than alignment.Their adoption has shifted the performance bottleneck from sequence alignment to seed location filtering.
  • GRIM-Filter: GRIM-Filter uses high parallelism and 3D-stacked memory’s logic layer to reduce filtering time and overcome the seed-filter memory bottleneck.The design exploits processing-in-memory capabilities and high internal bandwidth.
  • Contribution: GRIM-Filter is presented as the first seed location filter using PIM with 3D-stacked memory to accelerate read mapping while maintaining mapper sensitivity and comprehensiveness.The paper demonstrates it with mrFAST and FastHASH, while stating that the filter can be used with any read mapper.
  • Results: 5.59x–6.41x lower false negative rate and 1.81x–3.65x end-to-end speedup are reported at a sequence alignment error tolerance of 0.05.The comparison is against the best previous filter and against mrFAST with FastHASH, respectively, with zero false positives reported for the filtering comparison.

2 Motivation and Aim

The paper identifies wasted alignment work as a major opportunity for improving read-mapper performance. It motivates a filter that rejects false locations quickly without increasing total mapping time.

  • Motivation: Read mapping enables genome-variation analysis, while higher throughput could support larger-scale and more personalized genome analyses.The paper uses this broader potential to motivate improving read-mapper performance.
  • Bottleneck Analysis: 59% of mrFAST with FastHASH execution time is spent aligning locations later discarded as nonmatches, compared with 15% spent aligning locations found to match.These averages are reported across the paper’s read dataset.
  • Aim: An ideal filter would identify all false locations without increasing read-mapping time, yielding an estimated 3.2x average mrFAST with FastHASH speedup.The estimated gain primarily comes from eliminating false-location alignments.

3 GRIM-Filter

GRIM-Filter represents reference-genome segments with token-presence metadata and uses that representation to test candidate locations before alignment. Its bins and bitvectors support efficient filtering operations.

  • Overview: GRIM-Filter stores metadata for genome segments several hundred base pairs long to determine quickly whether a read can match a segment.These segments are the algorithm’s coarse-grained operating units.
  • Genome Metadata Representation: The reference genome is divided into overlapping contiguous bins, each associated with a bitvector recording whether short tokens are present.Bins are several hundred base pairs long, while tokens are approximately 5 base pairs long.
  • Genome Metadata Representation: For tokens of length n, each bin’s bitvector contains 4^n bits, with one existence bit for each possible token instance.A set bit indicates that the token occurs in the bin; an unset bit indicates that it does not.
  • Metadata Construction: The reference bitvectors are generated once per reference genome and can then support mapping any number of reads from individuals of the same species.Generation scans the genome for every possible token of the selected length and sets corresponding bin bits.

bin2

GRIM-Filter represents reference-genome bins with token-presence metadata and filters candidate seed locations before expensive sequence alignment. It uses accumulation sums and error-aware thresholds to retain likely matches while discarding unlikely ones.

  • Genome Metadata Representation: GRIM-Filter divides the reference genome into overlapping bins and stores token presence for each bin in bitvector metadata.Bins are short contiguous segments, typically several hundred base pairs, and tokens are short DNA sequences of about five base pairs.
  • Genome Metadata Representation: GRIM-Filter uses overlapping bins because the entire read must be contained within a bin for the token-presence test.Some base pairs therefore appear in multiple bins.
  • GRIM-Filter Operation: For each candidate location, GRIM-Filter loads its bin bitvector, checks read-token existence bits, and sums them into an accumulation sum.The accumulation sum counts how many read tokens occur somewhere in the candidate’s bin.
  • GRIM-Filter Operation: GRIM-Filter compares each accumulation sum with a threshold to decide whether a location proceeds to alignment or is discarded.Locations that pass are sent to the read mapper, while discarded locations avoid sequence alignment.
  • GRIM-Filter Operation: GRIM-Filter’s implementation reports zero false positives and does not affect read-mapper correctness while reducing unnecessary alignments.The filter passes locations whose bins contain enough matching tokens, including under supported error tolerance.
  • Determining the Accumulation Sum Threshold: The threshold accounts for sequence-alignment error tolerance by allowing tokens affected by insertions, deletions, or substitutions to remain unmatched.For each tolerated error, the method assumes the worst case in which up to n tokens are affected.

4 Mapping GRIM-Filter to 3D-Stacked Memory

GRIM-Filter maps naturally onto 3D-stacked memory because it is memory-intensive, uses simple operations, and can process bins in parallel near the stored bitvectors. The implementation places custom filter logic in each vault’s logic layer.

  • 3D-Stacked Memory: 3D-stacked DRAM combines stacked memory layers with a tightly integrated logic layer connected by high-bandwidth TSVs.This organization enables bulk data transfer from memory layers to logic that performs simple parallel operations.
  • Processing-in-Memory: PIM places computation near data in memory, reducing data movement between processor cores and memory while improving bandwidth and latency.The paper uses this capability to address the memory bottleneck in seed location filtering.
  • Mapping GRIM-Filter to 3D-Stacked Memory: GRIM-Filter is a strong PIM candidate because it is memory-intensive, uses simple additions and comparisons, and supports parallel bin processing.Its filter bitmask generator requires simple operations and is highly memory-bound.
  • Mapping GRIM-Filter to 3D-Stacked Memory: Bitvectors are stored column-major so a DRAM row fetches the same-token existence bits across many bin bitvectors.The fetched data is copied from the DRAM row buffer into logic-layer registers for processing.
  • Mapping GRIM-Filter to 3D-Stacked Memory: Each vault contains GRIM-Filter logic modules that process bin existence bits in parallel.The custom module uses an incrementer, accumulator, and comparator, with accumulator width based on read length.
  • Hardware Overhead: The implementation uses the available HBM2 bandwidth with 4096 GRIM-Filter logic modules distributed across vaults.A 512 KB DRAM bitmask buffer is sufficient to prevent stalls between filtering and read mapping.
  • Hardware Overhead: The bitvectors require a 3.8 GB memory footprint for the effective parameter set evaluated by the paper.The footprint is determined by the number of bins multiplied by the size of one bin.
  • Hardware Overhead: The authors conclude that GRIM-Filter requires a modest, simple logic layer compared with other seed location filtering algorithms.This is presented as an implementation advantage for the logic layer.

5 Experimental Methodology

The evaluation integrates GRIM-Filter with mrFAST and FastHASH, compares filtered and unfiltered mapper variants, and measures filtering accuracy and end-to-end performance. Experiments use ten real 1000 Genomes datasets and a modeled 3D-stacked-memory implementation.

  • Evaluated Read Mappers: The study evaluates GRIM-Filter as an extension to the state-of-the-art hash-table mapper mrFAST with FastHASH.The mapper was selected for its accuracy with relatively many errors.
  • Evaluated Read Mappers: The two evaluated systems are baseline mrFAST with FastHASH and GRIM-3D, which combines mrFAST with GRIM-Filter’s 3D-stacked-memory implementation.GRIM-3D retains the non-filtering portions of FastHASH.
  • Major Evaluation Metrics: The evaluation reports false negative rate and end-to-end read-mapper performance improvement as its major metrics.False negative rate is defined from locations passing the filter that do not produce a mapping.
  • Performance Evaluation: GRIM-3D execution time is estimated from read mapping, coordination, and filtering components.The first two components come from GRIM-Software measurements, while filtering time uses a validated 3D-stacked-memory simulator.
  • Evaluation System: Software mapper experiments run on an Intel Core i7-2600 CPU at 3.40 GHz with 16 GB of DRAM.The software versions evaluated are mrFAST with FastHASH and GRIM-Software.
  • Data Sets: The study uses ten real datasets from the 1000 Genomes Project, matching Xin et al.’s datasets for comparison with the baseline.Table 1 lists the read length and size of each dataset.
  • Code Availability: The GRIM-Filter, GRIM-Software, and 3D-stacked-memory simulator implementations are freely available online.The repository is hosted at github.com/CMU-SAFARI/GRIM.

6 Evaluation Results

GRIM-Filter’s evaluation examines parameter sensitivity, memory and parallelization trade-offs, filtering accuracy, and end-to-end execution time against FastHASH. Across ten real data sets, it substantially lowers false negatives and improves mapper performance.

  • Parameter Sensitivity: Under 16 GB, the evaluation sweeps bin count, token size, and error tolerance to characterize GRIM-Filter’s performance and memory footprint.The parameter study targets the capacity of contemporary HBM2 devices.
  • Parameter Sensitivity: Increasing token size from 4 to 5 reduces average read existence by around 10x, while increasing it from 5 to 6 yields only around 2x improvement and quadruples memory footprint.Increasing bin count lowers average read existence, whereas increasing error tolerance raises it.
  • Parameter Sensitivity: Above 300×216 bins, false-negative reductions show diminishing returns across error tolerances; the evaluation selects 450×216 bins as a memory, filtering-efficiency, and runtime trade-off.More bins exponentially reduce false negatives, minimally affect runtime, and linearly increase memory footprint.
  • Evaluation Scope: Bitvector-generation time is excluded from final runtime results because generation occurs once per reference genome; with 450×216 bins, human-genome generation takes approximately five minutes.The reported generation time is (9.03e −08) × L seconds for genome length L.
  • Parallelization: A bin window of w = 4096 uses HBM2’s full memory bandwidth and enables up to 4096 independent logic modules to process bins in parallel.Lockstep operation means modules assigned to empty bins may wait for other modules.
  • Filtering Accuracy: At e = 0.05, GRIM-Filter’s false negative rate is 5.97x lower than FastHASH’s average across ten data sets.GRIM-Filter has a lower false negative rate than FastHASH for every evaluated data set and error tolerance.
  • Execution Time: At e = 0.05, GRIM-3D improves average mapper performance by 2.08x, reaches a maximum 3.65x improvement, and reduces false-negative computation time by 83.7% versus FastHASH.The execution-time comparison covers ten real data sets and all evaluated error tolerances.

7 Related Work

Related work addresses acceleration of pre-alignment filtering and sequence alignment using FPGA and 3D-stacked-memory hardware. GRIM-Filter is presented as the first 3D-stacked-DRAM PIM algorithm targeting seed location filtering.

  • Pre-Alignment Acceleration: GRIM-Filter is described as the first algorithm to use 3D-stacked DRAM and PIM to accelerate seed location filtering, a read-mapping pre-alignment bottleneck.The paper distinguishes this focus from prior work accelerating sequence alignment.
  • Pre-Alignment Acceleration: Prior FPGA-based seed location filtering achieves speedup but remains limited by memory bandwidth; GRIM-Filter is described as overcoming this bottleneck on FPGA as well.The comparison concerns acceleration of pre-alignment filtering.
  • Sequence-Alignment Acceleration: Other work uses 3D-stacked memory’s bandwidth and reconfigurable logic layer to accelerate sequence alignment and other genome-sequence-analysis algorithms.Additional FPGA studies also accelerate sequence alignment with customized implementations.

8 Future Work

The paper concludes that GRIM-Filter reduces read-mapper execution time by avoiding unnecessary alignments and exploiting 3D-stacked DRAM PIM. It identifies broader integration and scalability studies as future directions.

  • Conclusion: GRIM-Filter reduces read-mapper execution time by reducing unnecessary sequence alignments and using processing-in-memory with 3D-stacked DRAM.The filter can be combined with other read mappers and genome-analysis acceleration mechanisms.
  • Future Work: Future work includes combining GRIM-Filter with other read mappers, evaluating varying reference-genome sizes, and scaling to more concurrently processed reads.These are identified as three promising research directions.

9 Conclusion

GRIM-Filter addresses the seed location filtering bottleneck in genome read mapping with a bin-and-token representation and processing-in-memory on 3D-stacked memory. It reduces filtering false negative rates and improves read-mapper performance, while motivating further use of emerging memory technologies and processing paradigms.

  • GRIM-Filter introduces a novel algorithm for seed location filtering, a critical performance bottleneck in genome read mapping.
  • GRIM-Filter represents large genome subsequences as bins and records whether smaller subsequences, or tokens, occur in each bin.
  • GRIM-Filter uses metadata operations and processing-in-memory in the logic layer of 3D-stacked memory to discard locations before expensive alignment.
  • At an alignment error tolerance of 0.05, GRIM-Filter achieves 5.59x–6.41x lower false negative rates than FastHASH and 1.81x–3.65x higher performance for mrFAST with FastHASH.
  • The results suggest designing DNA read mapping and other bioinformatics algorithms for technologies such as 3D-stacked DRAM and processing-in-memory.
Loading 1711.01177v1…