9500

GPU Multiple Sequence Alignment Fourier-Space Cross-Correlation Alignment

Matthias Alexander Lee
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}

}

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

Package:

989

views

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-2017 hgpu.org

All rights belong to the respective authors

Contact us: