String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly)
Jump to navigation
Jump to search
Time Complexity
$O(n)$
Space Complexity
$O(n)$? words
(Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2010
Reference
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881401/pdf/btq217.pdf