Complexity Time SPADES assembler

[mido1951]

hello,
I want to know the time Complexity of Spades Assmbeler?
I did not find on the net. Can you help me?
and is this the complexity of blastn is O (mn) with m and n the lenght of the two sequnces? if i have many sequences from two files so what's the time complexity?
Thanks

[Brian Bushnell]

Spades does not have an easy-to-express bounded time complexity; it's too complicated. You can only do that for fairly simple algorithms. A basic kmer-based assembler has a time complexity of O(n+m) where n is the amount of input data and m is the number of unique kmers. But, Spades has a lot of different phases, each with different characteristics, and it's hard to know which one will be the slowest. Graph-traversing algorithms especially can have worst-case bounds that are very different from what happens in a normal genome.

I'm not really sure about blastn, but full Smith-Waterman is O(mn) for two sequences of length m and n, and banded is O(b(m+n)) where b is the bandwidth. Blast uses some heuristics to reduce those so it may scale somewhat differently.

[mido1951]

if i do an assembly of Short reads with Spades. So the time coplexity is O(n) where n is the number of short reads.(n>>>>m) "m is the number of K-mer".
can i consider this?
Thanks