SEQanswers

Go Back   SEQanswers > Bioinformatics > Bioinformatics



Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU/bioinformatics programmer adaptivegenome Industry Jobs! 0 02-06-2013 08:59 AM
GPU CUDA BLAST Efficiency jjk Bioinformatics 2 01-31-2013 04:22 AM
Running BarraCUDA on Amazon AWS GPU ajminich Bioinformatics 4 03-13-2012 08:35 AM
GPU sequence aligner brianlamx Bioinformatics 8 12-22-2011 04:12 AM
gpu/cuda molbio software sbberes Bioinformatics 2 11-24-2010 02:34 PM

Reply
 
Thread Tools
Old 05-20-2013, 07:15 AM   #1
davispeter
Junior Member
 
Location: London

Join Date: May 2013
Posts: 2
Default DNA assembly on GPU

I was looking for DNA assemblers that work on GPU. I found only this paper http://www.cs.gmu.edu/~tr-admin/pape...-TR-2011-1.pdf - GPU Euler. But I was not satisfied with the concept and results provided in the paper. It works by finding the whole Euler tour without any graph transformation and error correction, still it is getting results comparable to well established assemblers like Euler SR. Like max-length of 40,000 , N-50 value 8000, etc. No other assembler works by finding the whole Euler tour then how this paper is mentioning such good results. Does anyone have read or worked with this paper?
davispeter is offline   Reply With Quote
Old 05-20-2013, 12:17 PM   #2
samanta
Senior Member
 
Location: Seattle

Join Date: Feb 2010
Posts: 109
Default

I would say GPU is a no-go for genome assembly. We looked at various options for doing genome assembly in GPUs last year, and could not make the algorithms scale well. Genome assembly programs need very large memory bandwidth, and it is not possible to scale the programs well in the GPUs, whose greatest benefit is access to many 'parallel' processors. Late last year, I attended BGI's booth at HPC conference (Salt Lake City) and saw a number of GPU solutions being presented for various bioinformatics problems, but the genome assembly program did not seem to give any performance boost. At present our group is working on implementing a genome assembler in FPGA, where we can get the performance boost.

I will forward your question to BGI's Ruibang, who can probably shed more light on the current status.
__________________
http://homolog.us
samanta is offline   Reply With Quote
Old 05-21-2013, 06:05 AM   #3
davispeter
Junior Member
 
Location: London

Join Date: May 2013
Posts: 2
Default

hmmmm. Thanks for reply. But what about the Euler approach. In the paper (that I mentioned) the Euler approach is implemented parallely. Does that mean Euler approach is not good?
davispeter is offline   Reply With Quote
Old 05-21-2013, 08:02 AM   #4
lh3
Senior Member
 
Location: Boston

Join Date: Feb 2008
Posts: 693
Default

According to the tech report, 90% of total time goes to "I/O". If I understand correctly, this "I/O" phase, unusually, includes k-mer counting and is done purely with CPU. K-mer counting is one of the slowest and most memory hungry steps in the construction of de Bruijn graph. If we cannot parallelize this step with GPU, we will not get much speed up.

In addition, the reported assembly speed is slower than what I would expect with velvet. I think velvet can usually get the results in a minute or so given 20X error-free data for a ~2Mbp genome. That is in par with GPU-Euler.

In all, I think the tech report does not prove that a GPU-based de Bruijn assembler is much better than CPU-based ones.
lh3 is offline   Reply With Quote
Old 05-21-2013, 07:40 PM   #5
Aqua
Junior Member
 
Location: Hong Kong

Join Date: Jan 2013
Posts: 2
Default

Thanks Samanta and lh3. I'm not closing the possibility of implementing an ultra-fast assembler on GPU, but the reduction nature of genome assembly problem constrained it from scaling well on GPU. For the latest GPU model nVidia GTX Titan, which has 2600+ cores but only ~300G memory bandwidth, every core will only get ~100MB/s memory bandwidth, not mentioning the optimal can only be achieve by coalesced memory access, which is almost impossible to be fulfilled no matter using DBG, String Graph or Greedy. Another problem is that GPU has only limited amount of on-board memory (3G-12G), swapping between host memory and GPU memory is possible but ultimately slow.

Differently, the problem of alignment is mainly "mapping" problem in MapReduce scheme, which makes it suitable for GPU or other HPC accelerator like FPGA and MIC. Plenty investigations have been done: "SOAP3-dp" (http://arxiv.org/abs/1302.5507) and "CUSHAW2-GPU" (http://cushaw2.sourceforge.net/homepage.htm#latest) has achieved more than 10x acceleration to CPU aligners, the most important, much higher sensitivity and accuracy in opening large gaps provide much more computational power.

BTW, frankly speaking, CPU assemblers, say SOAPdenovo2 and ALLPATH-LG, still have a large space to be improved. Samanta has a very good discussion on the hash function used in assemblers (http://homolog.us/blogs). A question is that, why we have to use standard, general hash functions in assembler? The only feature assemblers require the hash functions to have is the evenness, why shall we care that much about avalanche test.
Aqua is offline   Reply With Quote
Old 05-21-2013, 09:34 PM   #6
samanta
Senior Member
 
Location: Seattle

Join Date: Feb 2010
Posts: 109
Default

Here are the links.

http://www.homolog.us/blogs/blog/201...s-do-they-use/

http://www.homolog.us/blogs/blog/201...ash-functions/
__________________
http://homolog.us
samanta is offline   Reply With Quote
Old 05-22-2013, 07:44 AM   #7
lh3
Senior Member
 
Location: Boston

Join Date: Feb 2008
Posts: 693
Default

I should clarify that I am not closing the possibility of a good GPU assembler, either. I am just saying that we have not reached there yet. I also agree GPU based aligners are impressive works.
lh3 is offline   Reply With Quote
Old 05-25-2013, 11:58 AM   #8
mchaisso
Member
 
Location: Seattle, WA

Join Date: Apr 2008
Posts: 84
Default

Quote:
Originally Posted by davispeter View Post
hmmmm. Thanks for reply. But what about the Euler approach. In the paper (that I mentioned) the Euler approach is implemented parallely. Does that mean Euler approach is not good?
Unfortunately, under wrote definition of an Eulerian tour, finding a full Eulerian tour is meaningless when there are errors in sequences, and repeats longer than k. The de Bruijn based assemblers output contigs that represent unambiguous (and sequencing error-free) paths taken on the traversal of the de Bruijn graph. The original power of the de Bruijn approach was an efficient encoding of overlaps of very short (30nt) reads.

-mark
mchaisso is offline   Reply With Quote
Old 12-06-2018, 06:55 AM   #9
ctseto
Member
 
Location: SE MN

Join Date: Oct 2013
Posts: 44
Default

Haven't seen any as of late 2018, and I've been looking after getting back into de novo assembly...
Always possible that as someone getting back in that I've missed something.

Edit: I see megahit can use a GPU for graph construction

Last edited by ctseto; 12-06-2018 at 07:14 AM.
ctseto is offline   Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off




All times are GMT -8. The time now is 06:12 AM.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Single Sign On provided by vBSSO