SEQanswers (
-   Bioinformatics (
-   -   Complexity Time SPADES assembler (

mido1951 01-29-2016 03:17 PM

Complexity Time SPADES assembler
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?

Brian Bushnell 01-29-2016 09:24 PM

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 01-30-2016 05:12 AM

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?

All times are GMT -8. The time now is 01:04 PM.

Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.