Dynamic Programming on CUDA: Finding the Most Similar DNA Sequence
GrzegorzPuchawski 2700050UAH Visits (1167)
Recently, two my colleagues (Grzegorz Kokosinski and Krzysztof Zarzycki) were at GTC 2012 (GPU Technology Conference) in San Jose, California.
They gave a talk about a couple of techniques to speed up compute-heavy Dynamic Programming algorithms on the GPU (Graphics Processing Unit), especially in area of DNA sequences.
Problem definition: given a reference sequence, how to find the one most similar to it among a large database? The sequences are millions characters long, and their similarity is calculated with a (quadratic) DP algorithm, which makes the problem very tough even for the GPUs.
We speed up both the theoretical and practical side by using programming techniques that enable Dynamic Programming to be performed at the hardware speed and improvements to the algorithm itself that drastically lower the execution time.
You can find some more info (both video and presentation) at GTC conference web site: http
There are also other interesting presentations about application of GPU to tackle enormous computational challenges.