一句话：提出硬件加速系统 Harp，利用基因组图的准序列特性降低序列到图映射开销，显著加速长读比对。
长读序列到图映射（S2G）正逐渐取代序列到序列映射，但其图处理开销高且性能热点发生转移，给现有软件实现与硬件加速器带来挑战。本文提出 Harp，一种面向 S2G 的加速系统。它利用基因组图与序列之间的结构相似性，挖掘图的准序列特性，从而简化图处理算法。Harp 与两个算法组件协同设计：HarpTree 紧凑数据结构显式暴露准序列特性，HarpExt 多阶段种子扩展算法在保持映射视野的同时降低图操作开销。评估显示，Harp 在长读 S2G 映射中平均比最新软件快 140 倍，比最先进 S2G 加速器快 23.6 倍，并减少 72% 芯片面积。
Read mapping is a crucial task in computational genomics. Recently, there has been a significant paradigm shift from sequence-to-sequence mapping (S2S) to sequence-to-graph mapping (S2G). The S2G mapping incurs high graph processing overheads and leads to an unnoticed shift of performance hotspots. This presents a substantial challenge to current software implementations and hardware accelerators. This paper introduces Harp, a novel S2G mapping acceleration system. Harp leverages the structural similarities between genome graphs and sequences, significantly reducing graph processing overhead by exploiting their quasi-sequential characteristic. The Harp accelerator is co-designed with two main algorithmic components: (1) HarpTree, a compact data structure that explicitly reveals the quasi-sequential characteristic, enabling simplifications of graph processing algorithms in S2G mapping, and (2) HarpExt, a multi-stage seed-extension algorithm that mitigates graph operation overhead while maintaining the sight of S2G mapping. Harp achieves an average 140× speedup over the latest S2G mapping software and outperforms the state-of-the-art S2G accelerator by 23.6× while reducing the chip area by 72% in S2G mapping of long reads.
@inproceedings{ZhangCZ0LCWL24,
title = {Harp: Leveraging Quasi-Sequential Characteristics to Accelerate Sequence-to-Graph Mapping of Long Reads},
author = {Yichi Zhang and Dibei Chen and Gang Zeng and Jianfeng Zhu and Zhaoshi Li and Longlong Chen and Shaojun Wei and Leibo Liu},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3620666.3651331}
}