Motif Search

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

Parameters

$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

Related Problems

Edit-distance-based Motif Search

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 12 of 12 algorithms

				See more
PMS	2007	$O(nm^2 \sigma)$	$O(m^2 n)$
Risotto	2006	$O(mn^2 \sigma)$	$O(mn^2)$
Kingsford	2006	$O(mn)$	$O(m^2n^2)$
Census	2003	$O(k nm \sigma)$	$O(mnk)$
Mitra	2002	$O(k nm \sigma)$	$O(mnk)$
MotifSampler	2001	$O(nm)$	$O(n + m)$
Tompa M	1999	$O(mn)$	$O(m^2)$
Speller (Sagot)	1998	$O(mn^2 \sigma)$	$O(mn^2/w)$
Roth AlignACE	1998	$O(nm)$	$O(n + m)$
Bailey TL; Elkan C MEME	1995	$O(n^2m^2)$	$O(mn)$
Lawrence Gibbs Sampling	1993	$O(nm)$	$O(n + m)$
Lawrence, Reilly	1990	$O(nm)$	$O(nm)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table