- **Bioinformatics**
(*http://seqanswers.com/forums/forumdisplay.php?f=18*)

- - **Complexity Time SPADES assembler**
(*http://seqanswers.com/forums/showthread.php?t=65943*)

Complexity Time SPADES assemblerhello,
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 |

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. |

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 |

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.