Simple Bioinformatics Algorithms Using Parallel Computing (Cuda)?

Question

[Newvin]

Hi,

I am a bioinformatics graduate student looking to do a short project using CUDA. I would like compare the performance of simple bioinformatics algorithms executing on either the CPU or GPU. Thus, for each selected algorithm, I would code one version in C and another using CUDA. Execution times would then be compared and analyzed.

I am wondering if anyone can suggest some simple algorithms or program ideas that might lend themselves to parallel computation. I am thinking about very simple problems...an example might be sequence alignment...

I do have a good amount of programming experience and have used CUDA for about a month now.

Any help would be appreciated and Thank You!

[Newvin]

Thanks to all for your great ideas. I decided to go with the ORF finder, but if I have extra time I may try to implement some of the algorithms others have suggested as well.

Answer 1

[Prateek]

1. You could write an ORF (open reading frames) finder for 6 frames of reference given a multi-fasta file.

[Eric Normandeau]

Nice and simple!

Answer 2

[Jarretinha]

You can use this as an example:

Parallelized pairwise sequence alignment using CUDA on multiple GPUs

Other very important examples of algorithms that might benefit from CUDA are:

• Maximum likelihood calculations (linear models, phylogenetics);
• Transforms and their kernels (Radon, Burrows-Wheeler);
• CYK/Backward/Viterbi algorithms;
• Combinatorial optimization fo GWAS;

I would stick to MSA algorithms. They're better explored and are easier to bechmark. The most wanted by now are CO for GWAS, used to assess high order interactions between SNPs. Most approaches use pure brute-force. Hence, a parallel algorithm would provide a huge improvement.

Answer 3

[Pierre Lindenbaum]

I would try to map each pair of primers from UniSTS on the human Genome.