Motif Search: Difference between revisions

Revision as of 14:47, 15 February 2023

Motif search is the problem of identifying motifs, recurring or conserved patterns, in the strings (typically biological sequence data sets).

$n$: size of set of input strings

$m$: size of input strings

$k$: length of substrings

$\sigma$: function $V(k, m)$ defined as the number of $k$-mers that are at most $m$ Hamming distance from the motif space

Name	Year	Time	Space	Approximation Factor	Model	Reference
Lawrence, Reilly	1990	$O(nm)$	$O(nm)$		Deterministic	Time & Space
Lawrence Gibbs Sampling	1993	$O(nm)$	$O(n + m)$		Deterministic	Time
MotifSampler	2001	$O(nm)$	$O(n + m)$		Deterministic	Time
Speller	1998	$O(mn^{2} \sigma)$	$O(mn^{2}/w)$	Exact	Deterministic	Time & Space
Mitra	2002	$O(k nm \sigma)$	$O(mnk)$	Exact	Deterministic	Time & Space
Census	2003	$O(k nm \sigma)$	$O(mnk)$	Exact	Deterministic	Time & Space
Risotto	2006	$O(mn^{2} \sigma)$	$O(mn^{2})$	Exact	Deterministic	Time & Space
PMS	2007	$O(nm^{2} \sigma)$	$O(m^{2} n)$	Exact	Deterministic	Time & Space
Roth AlignACE	1998	$O(nm)$	$O(n + m)$		Deterministic	Time
Helden Oligo-Analysis	1998	$O(nm)$	$O(m)$	Exact	Deterministic	Time
van Helden J; Rios AF; Collado-Vides J	2000	$O(nm)$	$O(m)$	Exact	Deterministic	Time
Tompa M	1999	$O(nm)$	$O(m^{2})$	Exact	Deterministic	Time
Sinha S; Tompa M YMF (Yeast Motif Finder)	2000	$O(n^{0.{6}6} m)$	$O(m)$	Exact	Deterministic	Time
Bailey TL; Elkan C MEME	1995	$O(n^{2}m^{2})$	$O(nm)$	Exact	Deterministic	Time
Sagot M	1988	$O(n log(n)$ m^{1.{4}5})	$O(mn^{2}/w)$	Exact	Deterministic	Time & Space
Liang Cwinnower	2003	$O(nm^{0.5})$	$O(m^{2})$	Exact	Deterministic	Time
Kingsford	2006	$O(mn)$	$O(m^{2}n^{2})$	Exact	Deterministic	Time

@@ Line 50: / Line 50: @@
 | [[Bailey TL; Elkan C MEME ( Motif Search)|Bailey TL; Elkan C MEME]] || 1995 || $O(n^{2}m^{2})$ || $O(nm)$ || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF00993379 Time]
 |-
-| [[Sagot M ( Motif Search)|Sagot M]] || 1988 || $O(n logn m^{1.{4}5})$ || $O(mn^{2}/w)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/BFb0054337 Time & Space]
+| [[Sagot M ( Motif Search)|Sagot M]] || 1988 || $O(n log(n)$ m^{1.{4}5}) || $O(mn^{2}/w)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/BFb0054337 Time & Space]
 |-
 | [[Liang Cwinnower ( Motif Search)|Liang Cwinnower]] || 2003 || $O(nm^{0.5})$ || $O(m^{2})$ || Exact || Deterministic || [https://www.worldscientific.com/doi/10.1142/S0219720004000466 Time]
@@ Line 66: / Line 66: @@
 [[File:Motif Search - Space.png|1000px]]
-== Pareto Frontier Improvements Graph ==
+== Time-Space Tradeoff ==
 [[File:Motif Search - Pareto Frontier.png|1000px]]