
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SPAdes contigs  vpi  Bioinformatics  3  12022015 04:49 PM 
SPAdes: with different read length  bio_informatics  Illumina/Solexa  6  06102015 09:04 AM 
SPAdes: erroneous kmer threshold  bio_informatics  Bioinformatics  9  05172015 06:03 PM 
SPAdes: does contig with node id has/refer coverage?  bio_informatics  Bioinformatics  4  03272015 06:44 AM 
SPAdes trusted contigs  aimc  Bioinformatics  0  01122015 10:22 AM 

Thread Tools 
01292016, 03:17 PM  #1 
Senior Member
Location: Tunisia Join Date: May 2014
Posts: 123

Complexity Time SPADES assembler
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 
01292016, 09:24 PM  #2 
Super Moderator
Location: Walnut Creek, CA Join Date: Jan 2014
Posts: 2,707

Spades does not have an easytoexpress bounded time complexity; it's too complicated. You can only do that for fairly simple algorithms. A basic kmerbased 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. Graphtraversing algorithms especially can have worstcase bounds that are very different from what happens in a normal genome.
I'm not really sure about blastn, but full SmithWaterman 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. Last edited by Brian Bushnell; 01292016 at 09:28 PM. 
01302016, 05:12 AM  #3 
Senior Member
Location: Tunisia Join Date: May 2014
Posts: 123

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 Kmer".
can i consider this? Thanks 
Thread Tools  

