Accelerating Sequence-to-Graph Genome Mapping and Alignment on FPGAs using High Level Synthesi

Abstract

A crucial part of genome sequence analysis involves aligning DNA fragments (known as reads) obtained from an individual to a standard linear reference genome sequence, a process called sequence-to-sequence alignment. Recently, this linear reference has been replaced by a graph-based representation of the genome, which better reflects genetic variations and diversity found across different individuals within a population. Aligning reads to this graph-based reference (referred to as sequence-to-graph mapping) significantly enhances the accuracy of genome analysis. However, while sequence-to-sequence mapping is well-established with numerous tools and hardware accelerators available, sequence-to-graph mapping presents a more complex computational challenge and currently has far fewer practical software solutions and even fewer proposed hardware accelerators which could have important contribution in speeding up the genome analysis pipeline. In this work, we propose a sequence-to-graph read mapping and alignment by designing, evaluating and comparing two hardware architectures, one deducing the problem to sequence-to-sequence alignment and the other following a sequence-to-graph approach. Additionally, we build our own seeding workflow introducing hardware friendly seeding algorithms, which we evaluate in terms of both accuracy and performance. Our accelerator is implemented using High-Level Synthesis (HLS) on an AMD Alveo U200 FPGA, leveraging the reconfigurability of FPGAs to offer a flexible and adaptable solution. Both proposed accelerators, implementing the integrated workflow, achieve maximum 8.16x higher performance than the software implementation on a high-end server CPU. Our work is the first to building a sequence-to-graph aligner that deduces the problem to sequence-to-sequence alignment and to compare these different solutions, while proposing a standalone seeding workflow and architecture. Our contributions pave the way to finding novel algorithms and architectures to accelerate genome mapping and alignment while using reference genome representation with a greater amount of genomic information, such as genome graphs.