View Single Post
Old 01-29-2016, 09:24 PM   #2
Brian Bushnell
Super Moderator
Location: Walnut Creek, CA

Join Date: Jan 2014
Posts: 2,707

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.

Last edited by Brian Bushnell; 01-29-2016 at 09:28 PM.
Brian Bushnell is offline   Reply With Quote