Kingsford ( Motif Search)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(mn)$

Space Complexity

$O(m^{2}n^{2})$ words

(Creates an ILP with $O(m^2n^2)$ variables and $O(n^2m)$ constraints, each involving $O(m)$ variables)

Description

ILP formulation

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2006

Reference

https://link.springer.com/chapter/10.1007/11780441_22