what is the benefit of the de bruijn algorithm for short read assembly?

Question

[seta]

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

[Benn]

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.

[Rohit]

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

[GenoMax]

This is a slightly older paper but in case you have not seen it, it would be useful.

[Sej Modha]

You might file following papers useful.

Comparison of De Novo Genome Assembly Software

Sequence assembly demystified

Answer 1

[Michael]

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.