GPU Multiple Sequence Alignment Fourier-Space Cross-Correlation Alignment

Matthias Alexander Lee
Johns Hopkins University
Johns Hopkins University, 2013


   title={GPU Multiple Sequence Alignment Fourier-Space Cross-Correlation Alignment},

   author={Lee, Matthias Alexander},



Download Download (PDF)   View View   Source Source   Source codes Source codes




The aim of this project is to explore the possible application of Graphics Processors (GPUs) to accelerate and speed up sequence alignment by Fourier-space cross-correlation. Aligning signals using cross-correlations is a well studied approach in the world of signal processing, but has found relatively little reception in the realm of computational genomics. As long as we can treat DNA as a signal by encoding it numerically, we can utilize these cross-correlations to align and compare 2 or more strands of DNA or RNA. Fourier-space cross-correlations have a favorable computational complexity of O(n log_2(n)), where n is the length of the longer input strand. A single cross-correlation consists of three FFTs and a sliding dot-product, both of these types of operations are inherently parallel. Due to the extraordinary length of DNA sequences and the independence between operations, we can extort parallelism to a high degree. Therefore this problem maps very well to the highly parallel architecture of the modern GPU. This project explores the method, execution and performance of GPU-based DNA/RNA alignment using cross-correlations.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: