NECSTFridayTalk - Fast Genome Analysis Leveraging Exact String Matching
NECSTFridayTalk
Beatrice Branchini
Biomedical Engineering Master Student
Politecnico di Milano
Event will be online from Facebook
April 22nd, 2022
1.00 pm
Contacts:
Marco Santambrogio
Research Line:
System architectures
Beatrice Branchini
Biomedical Engineering Master Student
Politecnico di Milano
Event will be online from Facebook
April 22nd, 2022
1.00 pm
Contacts:
Marco Santambrogio
Research Line:
System architectures
Abstract
On April 22nd, 2022 at 1.00 pm "Fast Genome Analysis Leveraging Exact String Matching" a new appointment of NECSTFridayTalk, will be held online via Facebook by Beatrice Branchini, Biomedical Engineering Master Student at Politecnico di Milano.
Genome assembly is one of the most challenging tasks in bioinformatics, as it is the key to many applications. One of the fundamental tasks in genome assembly is exact sequence alignment. This process enables the identification of recurrent patterns and mutations inside the DNA, which can substantially support clinicians in providing a quicker diagnosis and producing individual-specific drugs. However, this procedure represents a bottleneck in genome analysis as it is computationally intensive and time-consuming. In this scenario, the efficiency of the chosen algorithm to perform this operation also plays a crucial role to speed up the analysis process. In this paper, we present a high-performance, energy-efficient FPGA implementation of the Knuth Morris Pratt (KMP) algorithm. Our multi-core architecture can parallelize the alignment procedure of the sequences, significantly reducing the execution time while still maintaining high flexibility. Experimental results show that our implementation on a Xilinx Alveo U280 achieves up to 2.68× speedup and up to 7.46× improvement in energy efficiency against Bowtie2, a State-of-the-Art application for sequence alignment run on a 40-thread Intel Xeon processor. Finally, our design also outperforms hardware-accelerated applications of the KMP present the State of the Art by up to 19.38× and 15.63× in terms of throughput and energy efficiency respectively.
Genome assembly is one of the most challenging tasks in bioinformatics, as it is the key to many applications. One of the fundamental tasks in genome assembly is exact sequence alignment. This process enables the identification of recurrent patterns and mutations inside the DNA, which can substantially support clinicians in providing a quicker diagnosis and producing individual-specific drugs. However, this procedure represents a bottleneck in genome analysis as it is computationally intensive and time-consuming. In this scenario, the efficiency of the chosen algorithm to perform this operation also plays a crucial role to speed up the analysis process. In this paper, we present a high-performance, energy-efficient FPGA implementation of the Knuth Morris Pratt (KMP) algorithm. Our multi-core architecture can parallelize the alignment procedure of the sequences, significantly reducing the execution time while still maintaining high flexibility. Experimental results show that our implementation on a Xilinx Alveo U280 achieves up to 2.68× speedup and up to 7.46× improvement in energy efficiency against Bowtie2, a State-of-the-Art application for sequence alignment run on a 40-thread Intel Xeon processor. Finally, our design also outperforms hardware-accelerated applications of the KMP present the State of the Art by up to 19.38× and 15.63× in terms of throughput and energy efficiency respectively.
The NECSTLab is a DEIB laboratory, with different research lines on advanced topics in computing systems: from architectural characteristics, to hardware-software codesign methodologies, to security and dependability issues of complex system architectures.
Every week, the “NECSTFridayTalk” invites researchers, professionals or entrepreneurs to share their work experiences and projects they are implementing in the “Computing Systems”.
Streaming via Facebook will be available at the following link
