A High-Performance Genomic Accelerator for Accurate Sequence-to-Graph Alignment Using Dynamic Programming Algorithm

doi:10.1109/TPDS.2023.3325137

2024-02-01

PRE

DOI：10.1109/TPDS.2023.3325137

原文链接

原文求助

摘要

En 中文

The rapid mutation of viruses, such as SARS-CoV-2, highlights the urgent need for fast and precise genomic sequencing. The traditional sequencing technique maps the DNA fragments collected from an individual to a known linear reference genome sequence. The linear reference cannot express the genetic diversity of the population, which leads to mapping bias. Therefore, researchers proposed to use a graph reference together with long reads for sequence mapping so that the mapping bias can be avoided to the greatest extent. However, the graph reference introduces irregular edges making memory access of alignment a bottleneck and meanwhile the long read quadratically increases the storage pressure in the alignment process. Therefore, there is a pressing need for a high-performance hardware accelerator for accurate sequence-to-graph alignment. To our best knowledge, this paper presents ASGDP, the first hardware accelerator designed for aligning sequences of arbitrary length reads to a graph. It is based on the traditional dynamic programming algorithm and supports flexible penalty scoring strategies. ASGDP has proposed an efficient memory access pattern in hardware and a hierarchical prediction pruning strategy in algorithm. This combined software-hardware strategy effectively alleviates the storage bottleneck of multi-edge access and improves the accuracy of pruning strategies. We demonstrate that ASGDP provides significant improvements for long reads of the sequence-to-graph alignment. For a typical 10 K long read, a single ASGDP accelerator outperforms state-of-the-art S2G mapping tools by 70.8x, 168.1x.

Keyword:

Graph-based

hardware accelerator

long read

read alignment

traditional dynamic programming

accuracy

期刊

IEEE Transactions on Parallel and Distributed Systems

IF:

论文数:

5.2K

被引数:

1.1W

机构

tsinghua university

学者数:

11.9W

论文数: 10.0W

被引数: 137

引用论文

Stress reappraisal improves the autonomic nervous system response of test anxious individuals: Evidence from heart rate variability

Neuroscience Letters

IF0

2023-08-01

PREAI

Qiong Huang; Huan Zhang; Renlai Zhou

Administration of Neomycin Resistance Gene Marked EBV Specific Cytotoxic T Lymphocytes to Recipients of Mismatched-Related or Phenotypically Similar Unrelated Donor Marrow Grafts. St. Jude Children's Research Hospital, Memphis, Tennesse

Human Gene Therapy

IF0

1994-03-01

PREAI

Helen E. Heslop; Malcolm K. Brenner; Cliona Rooney; Robert A. Krance; W. Mark Roberts; Richard Rochester; Colton A. Smith; Victoria Turner; John Sixbey; Robert Moen; James M. Boyett

A Decoder-free Transformer-like Architecture for High-efficiency Single Image Deraining

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

IF0

2022-07-01