BLAST (Gene Sequence alignment) Has anyone done it on CUDA

Accelerated Computing CUDA CUDA Programming and Performance
1

Hey guys,

I am working on implementing BLAST using CUDA. Has somebody already implemented it? I do not want to reinvent the wheel.

Thanks
Sid.

2

I am not in the topic, but have you tried googling it?
“BLAST CUDA”

[url=“CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment | BMC Bioinformatics | Full Text”]CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment | BMC Bioinformatics | Full Text
[url=“http://www.google.com/url?sa=t&source=web&ct=res&cd=2&url=http%3A%2F%2Fwww.biomedcentral.com%2Fcontent%2Fpdf%2F1471-2105-9-s2-s10.pdf&ei=Hs4qSr-OJpC6sgbj6p2eDA&rct=j&q=BLAST+CUDA&usg=AFQjCNF6DyaRRkxVYUo1Lf10ParPgkkAkA”]Redirect Notice

3

Respected Sir,

I had already(and obviously) googled it before posting it here. And the paper that you have directed me to is a Smithwaterman implementation on CUDA and is not about BLAST on GPUs. But any way it was nice of you to reply.

Thanks

Sid.

4

Was trying to help :(

5

I didnt want to lash out at you or anything. Sorry… just felt strange when you advised me to google it because that is what we all first do. :) No hard feelings. :)

6

You would be surprised…

7

Hey Sid,

If you get any updates, let me know. I’ve been thinking of tackling this one myself as I’m still relatively new to sequencing. Currently we have a summer student working on CUDA and it’s application to alignment tools. Not sure how far along he’s gotten though.

Rich

8

I’ve recently looked into this and it isn’t as straightforward as one might think. BLAST isn’t really an algorithm as a series of rather independent steps. In the standard NCBI implementation, most time is spent on simple (non-gapped) string matching, and I’m not sure it’s not faster on the CPU than it would take to just ship the data to the GPU. Later Smith-Waterman is used to align the HSSPs and the paper cited above shows how that can be done efficiently in cuda, but it’s only about 10% of total processing time in BLAST.

9

There are algorithms for string matching for GPU as well [url=“http://www.google.com/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww.cbcb.umd.edu%2Fsoftware%2Fcmatch%2FCmatch.pdf&ei=3Tg2Srn6Eo-asgbNpp24CQ&rct=j&q=string+matching+CUDA&usg=AFQjCNG_9PnDh8IHR5r4VH7FCniLF_hijQ”]Redirect Notice

10

Hi,

Its true that overhead of just transfering the database onto GPU may be huge but seeing the improving bandwidth of PCI-e and the speed-up that one may expect after the data has reached GPU, it is not a bad idea to port it onto the GPU. Or maybe some other algorithm which is better in terms of sensitivity than BLAST but not as fast may also be tried. Still looking into the possibilities.

Will surely update if there is any success.

Thanks

Sid.

11

I took a class in Bioinformatics a few years back. It’s not anywhere near my specialty (it was just an elective class), but I’m interested to read if you guys find (or write) any good string-matching code with CUDA.

12

I am curious as to how far you have gotten with your implementation with BLAST on CUDA? I have completed a variant of BLAST on the CUDA architecture and was curious as to how you attempted the same feat?

I look forward to your reply.

KK

13

btw, SSE 4.2 (i7) has superior string matching instructions… directly useful for string matching, xml parsing etc…
Check out the Intel guide. One can use that to optimize this code heavily.

14

CUDA-BLASTP uses BLAST-like heuristics for protein alignments. I’m working on BASALT, which will seed alignments for large nucleotide sequences. What kind of alignments are you interested in?