Skip to main content

1 SeGraM

0. Notes of downside​

  • BitAlign cannot handle long-term dependencies.

The authors analyze two state-of-the-art sequence-to-graph mapping tools and reveal four key issues. We find that there is a pressing need to have a ① specialized, ② high-performance, ③ scalable, and ④ low-cost algorithm/hardware co-design that alleviates bottlenecks in both the seeding and alignment steps of sequence-to-graph mapping.

Since sequence-to-sequence mapping can be treated as a special case of sequence-to-graph mapping, we aim to design an accelerator that is efficient for both linear and graph-based read mapping, for both short and long reads. Fuse, Universal

1. Innovation​

SeGraM is the first algorithm/hardware co-design for accelerating sequence-to-graph mapping.

SeGraM consists of two main components: (1) MinSeed, the first minimizer-based seeding accelerator, which finds the candidate locations in a given genome graph; and (2) BitAlign, the first bitvector-based sequence-to-graph alignment accelerator, which performs alignment between a given read and the subgraph identified by MinSeed.

2. motivation​

  • Due to the nascent nature of sequence-to-graph mapping, a much smaller number of software tools (and no hardware accelerators) exist for sequence-to-graph mapping compared to the traditional sequence-to-sequence mapping.
  • In order to identify and quantify the performance bottlenecks of existing tools, The authors analyze GraphAligner and vg, two state-of-the-art software tools for sequence-to-graph mapping.
    • These observations expose a pressing need to have a specialized, high-performance, scalable, and low-cost algorithm/hardware co-design that alleviates bottlenecks in both the seeding and alignment steps of sequence-to-graph mapping.

3. proposal​

SeGraM consists of two main components:

1). MinSeed, the first minimizer-based seeding accelerator, which finds the candidate mapping locations (i.e., subgraphs) in a given genome graph;

  • memory-efficient minimizer-based seeding algorithm
    • decreases the memory footprint of the index and provides speedup during seed queries.
    • couple MinSeed with High-Bandwidth Memory (HBM) to enable low-latency and highly-parallel memory access
  • requires only basic operations (e.g., comparisons, simple arithmetic operations, scratchpad read-write operations) that are implemented with simple logic.

2). BitAlign, the first bitvector-based sequence-to-graph alignment accelerator, which performs alignment between a given read and the subgraph identified by MinSeed.

  • novel bitvector-based, highly-parallel S2G alignment algorithm
    • employs a systolic-array-based design to circulate the internal data (i.e., bitvectors) generated by different processing elements, which provides scalability and reduces both memory bandwidth and memory footprint.
    • In order to handle hops (i.e., non-neighbor nodes in the graph-based reference), BitAlign provides a simple design that contains queue structures between each processing element, which store the most recently generated bitvectors.