Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment)
Jump to navigation
Jump to search
Time Complexity
$O(V + mE)$
Space Complexity
$O(mV)$ words
(Derived: algorithm uses a V-sized array of bitvectors each of which is of length m, and also uses a priority queue which has at most V elements. The precomputed pattern bitvectors also takes up O(V * m) space.)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2019