GPU Multiple Sequence Alignment Fourier-Space Cross-Correlation Alignment
Johns Hopkins University
Johns Hopkins University, 2013
@article{lee2013gpumultiple,
title={GPU Multiple Sequence Alignment Fourier-Space Cross-Correlation Alignment},
author={Lee, Matthias Alexander},
year={2013}
}
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.
May 31, 2013 by hgpu
