high performance computing on graphics processing units: hgpu.org

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.