This is a test version of Biostars. For the public version, visit https://www.biostars.org.
what is the benefit of the de bruijn algorithm for short read assembly?

Hi all,

First of sorry if the question is a basic for you. Could you please explain to me why the short reads are broken into shorter fragments (K-mer) and then found the overlap k-mer by the de Bruijn algorithm-based assembler software for transcriptome assembly, instead of using the entire read for finding the overlap segments? Please let me kindly know what is the benefit of such algorithms in relative to overlap algorithm used by CAP3?

Thanks

assembly de bruijn algorithm k-mer
• 3,449 views • link
updated by Michael Dondrup Michael Dondrup • written by seta seta

Time... It takes a lot more time to do it the old fashion way (with overlap), every read has to be checked with every other read.

• 0 views • link
written by Benn Benn

If you like tutorials in-addition to papers Homolog-blog covers really cool things about denovo assembly in general. Take a look :)

• 0 views • link
written by Rohit Rohit

1 answer

The advantages are time- and space complexity. Time complexity for building the graph is O(n * k) with n: number of bases sequenced and k: -kmer length. Space complexity for storing the graph is O(g * k) with g: genome-or transcriptome size which is often g << n (with sufficiently high coverage).

Of course, this needs to be compared to another algorithm which would be any Overlap-Layout-Consensus algorithm design. Such an algorithm would essentially have quadratic complexity (both storage and time) over the number of reads for generating and storing the overlap graph.

• 0 views • link
written by Michael Dondrup Michael Dondrup

Log in to answer this question.

More posts like this