SEQanswers

Go Back   SEQanswers > Bioinformatics > Bioinformatics



Similar Threads
Thread Thread Starter Forum Replies Last Post
SPAdes contigs vpi Bioinformatics 3 12-02-2015 04:49 PM
SPAdes: with different read length bio_informatics Illumina/Solexa 6 06-10-2015 09:04 AM
SPAdes: erroneous kmer threshold bio_informatics Bioinformatics 9 05-17-2015 06:03 PM
SPAdes: does contig with node id has/refer coverage? bio_informatics Bioinformatics 4 03-27-2015 06:44 AM
SPAdes trusted contigs aimc Bioinformatics 0 01-12-2015 10:22 AM

Reply
 
Thread Tools
Old 01-29-2016, 03:17 PM   #1
mido1951
Senior Member
 
Location: Tunisia

Join Date: May 2014
Posts: 123
Default 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
mido1951 is offline   Reply With Quote
Old 01-29-2016, 09:24 PM   #2
Brian Bushnell
Super Moderator
 
Location: Walnut Creek, CA

Join Date: Jan 2014
Posts: 2,707
Default

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
Old 01-30-2016, 05:12 AM   #3
mido1951
Senior Member
 
Location: Tunisia

Join Date: May 2014
Posts: 123
Default

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
mido1951 is offline   Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off




All times are GMT -8. The time now is 09:04 AM.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.
Single Sign On provided by vBSSO