This work will be about the possibilty to use GPGPU methodes in Seqan (especially with NVidia CUDA) and the implementation and parallelization of Myers fast bitvector algorithm for approximate string matchings. It is stated that using massive multiprocessor programming can dramatically increases the speed and performance of algorithms, depending on the amount that could be parallized and the efficiency it is implemented. Using hundreds or thousands of parallel threads for read mapping/ localizing/matching to a genom with the fast GPU cores and Myers fast matching algorithm can give an great gain of speed for sequence analyse and string matchings.
Several issues have to be worked out:
This will require an efficient adopting of the problem and problem-size for partitioning the parallel work most effective on GPU with different hardware settings.
[1] Myers, G. (1999). A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, Journal of the ACM, 46(3): 495-415
[2] Hyyrö, H. (2001). A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances
[3] Gröpl, C., Klau, G. and Reinert, K. (2009). Bit-parallel string matching
[4] Bailey, M., Cunningham, S. (2009). Graphics Shaders - Theory and Practice
[5] Kirk, David B., Hwu, Wen.mei W. (2010). Programming Massively Parallel Processors - A Hands-on Approach