View source for Polykay

In the field of [[computational biology]], a '''planted motif search''' (PMS) also known as a '''(''l, d'')-motif search''' (LDMS) is a method for identifying conserved [[sequence motif|motifs]] within a set of [[nucleic acid sequence|nucleic acid]] or [[peptide sequence]]s.

PMS is known to be [[NP-complete]]. The [[Time complexity|time complexities]] of most of the planted motif search algorithms depend exponentially on the alphabet size and ''l''. The PMS problem was first introduced by Keich and Pevzner.<ref name="Keich_2002">{{cite journal | author = Keich U, Pevzner PA | title = Finding motifs in the twilight zone | journal = Bioinformatics | volume = 18 | issue = 10 | pages = 1374–1381 |date=October 2002 | pmid = 12376382 | doi = 10.1093/bioinformatics/18.10.1374 }}</ref>

The problem of identifying meaningful patterns (e.g., motifs) from [[biological data]] has been studied extensively since they play a vital role in understanding [[functional genomics|gene function]], [[disease|human disease]], and may serve as [[drug discovery|therapeutic drug targets]].

== Description ==
The search problem may be summarized as follows:

''Input are n strings (s<sub>1</sub>, s<sub>2</sub>, … , s<sub>n</sub>) of length m each from an alphabet Σ and two integers l and d. Find all strings x such that |x| = l and every input string contains at least one variant of x at a [[Hamming distance]] of at most d. Each such x is referred to as an (l, d) motif.''

For example, if the input strings are GCGCGAT, CACGTGA, and CGGTGCC; ''l'' = 3 and ''d'' = 1, then GGT is a motif of interest. Note that the first input string has GAT as a [[substring]], the second input string has CGT as a substring, and the third input string has GGT as a substring. GAT is a variant of GGT that is within a Hamming distance of 1 from GGT, etc. Call the variants of a motif that occur in the input strings as instances of the motif. For example, GAT is an instance of the motif GGT that occurs in the first input string.

Zero or more (''l'', ''d'') motifs are contained in any given set of input strings. Many of the known algorithms for PMS consider [[DNA sequence|DNA strings]] for which Σ ={G, C, T, A}. There exist [[algorithms]] that deal with protein strings as well. The PMS problem is also known as the (''l'', ''d'')-motif search (LDMS) problem.

== Notation ==
The following [[mathematical notation]] is often used to describe PMS algorithms.

Assume that S = {''s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, …, s<sub>n</sub>''} is the given set of input strings from an alphabet Σ. An ''l''-mer of any string is nothing but a substring of the string of length ''l''. Let ''d<sub>H</sub>(a, b)'' stand for the [[Hamming distance]] between any two ''l''-mers ''a'' and ''b''. Let ''a'' be an ''l''-mer and ''s'' be an input string. Then, let ''d<sub>H</sub>(a, s)'' stand for the minimum Hamming distance between ''a'' and any ''l''-mer ''b'' of ''s''. If ''a'' is any ''l''-mer and ''S'' is a set of input strings then let ''d<sub>H</sub>(a, S)'' stand for max<sub>sєS</sub>''d<sub>H</sub>(a, s)''. Let ''u'' be any ''l''-mer. Then, the ''d''-neighborhood of ''u'', (denoted as ''B<sub>d</sub>(u)''), is nothing but the set of all the ''l''-mers ''v'' such that ''d<sub>H</sub>(u, v)'' ≤ ''d''. In other words, ''B<sub>d</sub>(u)={v: d<sub>H</sub>(u, v)≤d}''. Refer to any such ''l''-mer ''v'' as a ''d''-neighbor of ''u''. ''B<sub>d</sub>(x, y)'' is used to denote the common ''d''-neighborhood of ''x'' and ''y'', where ''x'' and ''y'' are two ''l''-mers. ''B<sub>d</sub>(x, y)'' is nothing but the set of all ''l''-mers that are within a distance of ''d'' from both ''x'' and ''y''. Similarly, ''B<sub>d</sub>(x,&nbsp;y,&nbsp;z)'', etc. can be defined.

== Algorithms ==
The scientific literature describes numerous algorithms for solving the PMS problem. These algorithms can be classified into two major types. Those algorithms that may not return the optimal answer(s) are referred to as [[approximation algorithms]] (or [[heuristic]] algorithms) and those that always return the optimal answer(s) are called exact algorithms.

=== Approximate ===
Examples of [[Approximation algorithms|approximation (or heuristic) algorithms]] include Random Projection,<ref name="Buhler_2001">{{cite journal | author = Buhler J, Tompa M | title = Finding motifs using random projections | journal = J. Comput. Biol. | volume = 9 | issue = 2 | pages = 225–42 | year = 2002 | pmid = 12015879 | doi = 10.1089/10665270252935430 }}</ref> PatternBranching,<ref name="Price_2003">{{cite journal | author = Price A, Ramabhadran S, Pevzner PA | title = Finding subtle motifs by branching from sample strings | journal = Bioinformatics | volume = 19 Suppl 2 | issue = | pages = ii149–55 |date=October 2003 | pmid = 14534184 | doi = 10.1093/bioinformatics/btg1072 }}</ref> MULTIPROFILER,<ref name="Keich_2002" /> CONSENSUS,<ref name="Hertz1999">{{cite journal | author = Hertz GZ, Stormo GD | title = Identifying DNA and protein patterns with statistically significant alignments of multiple sequences | journal = Bioinformatics | volume = 15 | issue = 7–8 | pages = 563–77 | year = 1999 | pmid = 10487864 | doi = 10.1093/bioinformatics/15.7.563 }}</ref> and ProfileBranching.<ref name="Price_2003" /> These algorithms have been experimentally demonstrated to perform well.

==== Random projection ====
The algorithm<ref name="Buhler_2001" /> is based on random projections. Let the motif ''M'' of interest be an ''l''-mer and ''C'' be the collection of all the ''l''-mers from all the ''n'' input strings. The algorithm projects these ''l''-mers along ''k'' randomly chosen positions (for some appropriate value of ''k''). The projection of each ''l''-mer may be thought of as an integer. The projected values (which are ''k''-mers) are grouped according to their integer values. In other words, hash all the ''l''-mers using the ''k''-mer of any ''l''-mer as its hash value. All the ''l''-mers that have the same hash value fall into the same hash bucket. Since the instances of any (''l'', ''d'') motif are similar to each other,  many of these instances will fall into the same bucket. Note that the [[Hamming distance]] between any two instances of an (''l'', ''d'') motif is no more than 2''d''. The key idea of this algorithm is to examine those buckets that have a large number of ''l''-mers in them. For each such bucket, an [[Expectation maximization|expectation maximization (EM) algorithm]] is used to check if an (''l'', ''d'') motif can be found using the ''l''-mers in the bucket.

==== Pattern branching ====
This algorithm<ref name="Price_2003" /> is a [[Local search (optimization)|local searching algorithm]]. If ''u'' is any ''l''-mer, then there are <math>\tbinom ld 3^d</math> ''l''-mers that are ''d''-neighbors of ''u'', for DNA strings. This algorithm starts from each ''l''-mer ''u'' in the input, searches the neighbors of ''u'', scores them appropriately and outputs the best scoring neighbor.

=== Exact ===
Many exact algorithms are known for solving the PMS problem as well. Examples include the ones in (Martinez 1983),<ref name="Martinez_1983">{{cite journal | author = Martinez HM | title = An efficient method for finding repeats in molecular sequences | journal = Nucleic Acids Res. | volume = 11 | issue = 13 | pages = 4629–34 |date=July 1983 | pmid = 6866775 | pmc = 326069 | doi = 10.1093/nar/11.13.4629 }}</ref> (Brazma, et al. 1998),<ref name="Brazma1998">{{cite journal | author = Brazma A, Jonassen I, Vilo J, Ukkonen E | title = Predicting gene regulatory elements in silico on a genomic scale | journal = Genome Res. | volume = 8 | issue = 11 | pages = 1202–1215 |date=November 1998 | pmid = 9847082 | pmc = 310790 | doi = 10.1101/gr.8.11.1202 }}</ref> (Galas, et al. 1985),<ref name="Galas_1985">{{cite journal | author = Galas DJ, Eggert M, Waterman MS | title = Rigorous pattern-recognition methods for DNA sequences. Analysis of promoter sequences from Escherichia coli | journal = J. Mol. Biol. | volume = 186 | issue = 1 | pages = 117–28 |date=November 1985 | pmid = 3908689 | doi = 10.1016/0022-2836(85)90262-1 }}</ref> (Sinha, et al. 2000),<ref name="Sinha_2000">{{cite journal | author = Sinha S, Tompa M | title = A statistical method for finding transcription factor binding sites | journal = Proc Int Conf Intell Syst Mol Biol | volume = 8 | issue = | pages = 344–54 | year = 2000 | pmid = 10977095 | doi =  }}</ref> (Staden 1989),<ref name="Staden_1989">{{cite journal | author = Staden R | title = Methods for discovering novel motifs in nucleic acid sequences | journal = Comput. Appl. Biosci. | volume = 5 | issue = 4 | pages = 293–8 |date=October 1989 | pmid = 2684350 | doi = 10.1093/bioinformatics/5.4.293 }}</ref> (Tompa 1999),<ref name="Tompa_1999">{{cite journal | author = Tompa M | title = An exact method for finding short motifs in sequences, with application to the ribosome binding site problem | journal = Proc Int Conf Intell Syst Mol Biol | volume = | issue = | pages = 262–71 | year = 1999 | pmid = 10786309 | doi =  }}</ref> (Helden, et al. 1998)<ref name="Helden_1998">{{cite journal | author = van Helden J, André B, Collado-Vides J | title = Extracting regulatory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies | journal = J. Mol. Biol. | volume = 281 | issue = 5 | pages = 827–42 |date=September 1998 | pmid = 9719638 | doi = 10.1006/jmbi.1998.1947 }}</ref> (Rajasekaran, et al.),<ref name="RajBallaHuang2005">{{cite journal | author = Rajasekaran S, Balla S, Huang CH | title = Exact algorithms for planted motif problems | journal = J. Comput. Biol. | volume = 12 | issue = 8 | pages = 1117–1128 |date=October 2005 | pmid = 16241901 | doi = 10.1089/cmb.2005.12.1117 }}</ref> (Davila and Rajasekaran 2006),<ref name=Davila>{{cite journal| author = Davila J, Rajasekaran S | title = Extending Pattern Branching to Handle Challenging Instances | journal = BioInformatics and BioEngineering | year = 2006 | pages = 65–69 | doi = 10.1109/BIBE.2006.253317| isbn = 0-7695-2727-2 }}</ref>  (Davila, Balla, and Rajasekaran 2006),<ref name=RajBallaDavila2006>{{cite journal | author = Davila J, Balla S, Rajasekaran S | title = Space and time efficient algorithms for planted motif search | journal = Proc. 6th International Conference on Computational Science (ICCS 2006)/ 2nd International Workshop on Bioinformatics Research and Applications (IWBRA 2006) LNCS 3992 | year = 2006 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.4572&rep=rep1&type=pdf }}</ref>  Voting<ref name="Chin_2005">{{cite journal| author = [[Y. L. Chin|Chin FYL]], Leung HCM | title = Voting algorithms for discovering long motifs | journal = Proceedings of the Third Asia-Pacific Bioinformatics Conference (APBC) | year = 2005 | pages = 261–271| doi = 10.1142/9781860947322_0026| isbn = 978-1-86094-477-2 }}</ref> and RISOTTO.<ref name="Pisanti2006">{{cite journal | author = Pisanti N, Carvalho A, Marsan L, Sagot MF | title = Risotto: Fast extraction of motifs with mismatches | journal = Proceedings of the 7th Latin American Theoretical Informatics Symposium | pages = 757–768 | year = 2006 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.1028&rep=rep1&type=pdf }}</ref>

==== WINNOWER and SP-STAR ====
The WINNOWER algorithm<ref name="Pevzner_2000">{{cite journal | author = Pevzner PA, Sze SH | title = Combinatorial approaches to finding subtle signals in DNA sequences | journal = Proc Int Conf Intell Syst Mol Biol | volume = 8 | issue = | pages = 269–78 | year = 2000 | pmid = 10977088 | doi = }}</ref> is a [[heuristic algorithm]] and it works as follows. If ''A'' and ''B'' are two instances of the same motif in two different input strings, then the Hamming distance between ''A'' and ''B'' is at most 2''d''. It can be shown that the expected Hamming distance between ''A'' and ''B'' is <math>2d-\tfrac{4d^2}{3l}</math>. WINNOWER constructs a collection ''C'' of all possible ''l''-mers in the input. A graph ''G(V,E)'' is constructed in which each ''l''-mer of ''C'' will be a node. Two nodes ''u'' and ''v'' in ''G'' are connected by an edge if and only if the Hamming distance between ''u'' and ''v'' is at most 2''d'' and they come from two different input strings.

If ''M'' is an (''l'', ''d'') motif and if ''M<sub>1</sub>'', ''M<sub>2</sub>'', …, and ''M<sub>n</sub>'' are instances of ''M'' in the input strings, then, clearly, these instances will form a [[Clique (graph theory)|clique]] in ''G''. The WINNOWER algorithm has two phases. In the first phase, it identifies large cliques in ''G''. In the second phase each such clique is examined to see if a motif can be extracted from this clique.
Since the [[Clique (graph theory)|CLIQUE]] problem is [[Intractability (complexity)|intractable]], WINNOWER uses a heuristic to solve CLIQUE. It iteratively constructs cliques of larger and larger sizes. If ''N'' = ''mn'', then the run time of the algorithm is <math>O(N^{2d+1} )</math>.This algorithm runs in a reasonable amount of time in practice especially for small values of ''d''.
Another algorithm called SP-STAR,<ref name="Pevzner_2000" /> is faster than WINNOWER and uses less memory. WINNOWER algorithm treats all the edges of ''G'' equally without distinguishing between edges based on similarities. SP-STAR scores the ''l''-mers of ''C'' as well as the edges of ''G'' appropriately and hence eliminates more edges than WINNOWER per iteration.

(Bailey and Elkan, 1994)<ref name="Bailey_Elkan_1994">{{cite journal | author = Bailey TL, Elkan C | title = Fitting a mixture model by expectation maximization to discover motifs in biopolymers | journal = Proc Int Conf Intell Syst Mol Biol | volume = 2 | issue = | pages = 28–36 | year = 1994 | pmid = 7584402 | doi =  }}</ref> employs expectation maximization algorithms while Gibbs sampling is used by (Lawrence et al., 1993).<ref name="Lawrence_1993">{{cite journal | author = Lawrence CE, Altschul SF, Boguski MS, Liu JS, Neuwald AF, Wootton JC | title = Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment | journal = Science | volume = 262 | issue = 5131 | pages = 208–14 |date=October 1993 | pmid = 8211139 | doi = 10.1126/science.8211139 }}</ref> MULTIPROFILER<ref name="Keich_2002" /> MEME,<ref name=Bailey_Elkan_1995>{{cite journal | author=Bailey TL, Elkan C|coauthors=Elkan, Charles | title = Unsupervised learning of multiple motifs in biopolymers using expectation maximization | journal = Machine Learning |date=January 1995 | volume = 21 | issue = 1–2 |pages = 51–80 | doi = 10.1007/BF00993379 }}</ref> are also known PMS algorithms.

==== PMS series ====
In the last decade a series of algorithms with PMS as a prefix has been developed in the lab of [http://www.engr.uconn.edu/~rajasek/ Rajasekaran]. Some of these algorithms are described below.

===== PMS0 =====
PMSo<ref name="RajBallaHuang2005" /> works as follows. Let ''s<sub>1</sub>'', ''s<sub>2</sub>'', …, ''s<sub>n</sub>''  be a given set of  input strings  each of length ''m''. Let ''C'' be the collection of ''l''-mers in ''s<sub>1</sub>''. Let C' = ∪<sub>''u∈C''</sub>''B''<sub>''d''</sub>(''u''). For each element ''v'' of ''C''' check if it is a valid (''l'', ''d'')-motif or not. Given an ''l''-mer ''v'', a check if it is a valid (''l'', ''d'')-motif or not can be made in O(''mnl'') time. Thus the run time of PMS0, assuming an alphabet of size 4, is <math>O(m^2 nl\tbinom ld 3^d)</math>.

===== PMS1 =====
This algorithm<ref name="RajBallaHuang2005" /> is based on [[radix sorting]] and has the following steps.

# Generate the set of all ''l''-mers in each input string. Let ''C<sub>i</sub>'' correspond to the ''l''-mers of ''s<sub>i</sub>'', for 1≤''i''≤''n''.
# For each ''l''-mer u in ''C<sub>i</sub>'' (1 < ''i'' < ''n''), generate ''B<sub>d</sub>''(''u'').  Let ''L<sub>i</sub>'' be a collection of all of these neighbors (corresponding to all the ''l''-mers of ''s<sub>i</sub>'').
# Sort ''L<sub>i</sub>'' (using radix sort) and eliminate any duplicates.
# Compute :<math>\bigcap_{i=1}^{n} L_i.</math>. This can be done by merging the lists ''L<sub>1</sub>'', ''L<sub>2</sub>'', …, ''L<sub>n</sub>''. All the ''l''-mers in this intersection are valid (''l'', ''d'') motifs.

===== PMS2 =====
Let the motif ''M'' of interest be of length ''l''. If ''M'' occurs in every input string then any [[substring]] of ''M'' also occurs in every input string. Here occurrence means occurrence within a Hamming distance of ''d''. It follows that there are at least ''l''-''k''+1 strings each of length ''k'' (for ''k'' ≤ ''l'') such that each of these occurs in every input string.

Let ''Q'' be a collection of ''k''-mers in ''M''. Note that, in every input string ''s<sub>i</sub>'', there will be at least one position ''i<sub>j</sub>'' such that a ''k''-mer of ''Q'' occurs starting from ''i<sub>j</sub>''. Another ''k''-mer of ''Q'' occurs starting from ''i<sub>j</sub>''&nbsp;+1 and so on, with the last ''k''-mer occurring at ''i<sub>j</sub>'' + l – ''k''. An ''l''-mer can be obtained by combining these ''k''-mers that occur starting from each such ''i<sub>j</sub>''.

PMS2<ref name="RajBallaHuang2005" /> works as follows. In the first phase find all the (''k'', ''d'') motifs present in all the input strings (for some appropriate value of ''k''<''l''). In the second phase, look for (''l''-''k''+1) of these (''k'', ''d'') motifs that occur starting from successive positions in each of the input strings. From every such collection of (''l''-''k''+1) (''k'', ''d'')-motifs, ''l''-mer can be generated (if possible). Each such ''l''-mer is a candidate (''l'', ''d'')-motif. For each candidate motif, check if it is an (''l'', ''d'')-motif or not in O(''mnl'') time. This ''l''-mer is returned as output if this is an (''l'', ''d'')-motif.

===== PMS3 =====
This algorithm<ref name="RajBallaHuang2005" /> enables one to handle large values of ''d''. Let ''d''’=''d''/2. Let ''M'' be the motif to be found with |''M''|=''l''=2''l''’ for some integer ''l''’. Let ''M<sub>1</sub>'' refer to the first half of ''M'' and ''M<sub>2</sub>'' be the next half. Let ''s''= ''a<sub>1</sub>a<sub>2</sub>…a<sub>m</sub>'' be one of the input strings. ''M'' occurs in every input string. Let the occurrence of ''M'' (within a Hamming distance of ''d'') in ''s'' start at position ''i''. Let ''s''’=''a<sub>i</sub>a<sub>i+1</sub>…a<sub>i+l’-1</sub>''  and ''s''’’ =''a<sub>i+l</sub>’…a<sub>i+l-1</sub>''.
It is clear that either the Hamming distance between ''M<sub>1</sub>'' and ''s''’ is at most ''d''’ or the Hamming distance between ''M<sub>2</sub>'' and ''s''’’ is at most ''d''’. Either ''M''<sub>1</sub> or ''M''<sub>2</sub> occurs in every input string at a Hamming distance of at most ''d''’. As a result, in at least ''n''’ strings (where ''n''’ = ''n''/2) either ''M''<sub>1</sub> or ''M''<sub>2</sub>  occurs with a Hamming distance of at most ''d''.
The algorithm first obtains all the (''l''’, ''d''’)-motifs that occur in at least ''n''/2 of the input strings. It then uses these motifs and the above observations to identify all the (''l'', ''d'')-motifs present in the input strings.

===== PMSPrune =====
This algorithm introduces a [[Tree (data structure)|tree structure]] for the motif candidates and uses a [[branch-and-bound algorithm]] to reduce the search space.<ref name="Raj_Davila_Balla_2007">{{cite journal | author = Davila J, Balla S, Rajasekaran S | title = Fast and practical algorithms for planted (l, d) motif search | journal = IEEE/ACM Trans Comput Biol Bioinform | volume = 4 | issue = 4 | pages = 544–52 | year = 2007 | pmid = 17975266 | doi = 10.1109/TCBB.2007.70241 }}</ref> Let ''S'' = {''s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub>''} be a given set of input strings.
PMSprune follows the same strategy as PMS0: For every ''l''-mer ''y'' in ''s<sub>1</sub>'', it generates the set of neighbors of ''y'' and, for each of them, checks whether this is a motif or not. Some key steps in the algorithm are:
# It generates the ''d''-neighborhood of every ''l''-mer ''y'' in ''s<sub>1</sub>'' using a tree of height ''d''. The root of this tree will have ''y''. Every ''l''-mer that is at a distance of 1 from ''y'' will be a node in the tree that is at a distance of 1 from the root; every ''l''-mer that is at a distance of 2 from ''y'' will be a node in the tree that is at a distance of 2 from the root; and so on. When a node in this tree is visited, check if the corresponding ''l''-mer is an (''l'', ''d'')-motif. I.e., if the ''l''-mer is ''x'', check if ''d<sub>H</sub>(x, S)''≤''d''. If so, output this ''l''-mer. In any case move to the next node in the tree. This tree is explored in a [[Depth-first search|depth first]] manner.
# If each node in the tree is visited for each ''l''-mer ''y'' in ''s<sub>1</sub>'', then the run time of PMSPrune will be at least as much as that of PMS0. PMSPrune uses some pruning conditions to prune subtrees that cannot possibly have any motifs in them.
# For an ''l''-mer ''x'', which corresponds to a node in a subtree of height ''h'', the algorithm uses the value of ''d<sub>H</sub>(x, S)'' and ''h'' to prune the descendants of ''x''.
# PMSPrune calculates the value of ''d<sub>H</sub>(x, S)'' for the nodes (''x'') in the tree in an incremental way, taking into account the way in which the neighborhood is generated.

===== PMS4 =====
PMS4<ref name="Raj_Din_2011">{{cite journal | author = Rajasekaran S, Dinh H | title = A speedup technique for (l, d)-motif finding algorithms | journal = BMC Res Notes | volume = 4| pages = 54 | year = 2011 | pmid = 21385438 | pmc = 3063805 | doi = 10.1186/1756-0500-4-54 }}</ref> is a technique that can be used to speedup any algorithm for the PMS problem. In many of the above algorithms there are two phases. In the first phase we come up with a set of candidate motifs and in the second phase check, for each candidate motif, if it is a valid (''l'', ''d'')-motif. For each candidate motif it takes O(''mnl'') time to check if it is a valid motif or not. PMS4 employs a similar two phase strategy. These phases are explained below. Let A be any PMS algorithm.
# Run the algorithm A on ''k'' input strings (where ''k'' < ''n''). An optimal value of ''k'' can be determined empirically. The ''k'' strings may be picked in a number of ways. For example, they could be the first ''k'' strings, random ''k'' strings, and so on. Let ''C'' be the collection of (''l'', ''d'')-motifs found in these ''k'' strings. Clearly, ''C'' is a superset of the (''l'', ''d'')-motifs present in the ''n'' given input strings.
# for each ''l''-mer ''v'' in ''C'' do
:::Check if ''v'' is a valid motif in O(''mnl'') time. If so, output ''v''.

===== PMS5 and PMS6 =====
PMS5<ref name="Raj_Din_Kundeti_2012">{{cite journal | author = Dinh H, Rajasekaran S, Kundeti VK | title = PMS5: an efficient exact algorithm for the (ℓ, d)-motif finding problem | journal = BMC Bioinformatics | volume = 12| pages = 410 | year = 2011 | pmid = 22024209 | pmc = 3269969 | doi = 10.1186/1471-2105-12-410 }}</ref> is an extension of PMS0. If ''S'' = {''s<sub>1</sub>'', ''s<sub>2</sub>'', …, ''s<sub>n</sub>''}  is a set of strings (not necessarily of the same length), let <math>M_l^d (S)</math> denote the (''l'', ''d'')-motifs present in ''S''. Let ''S''’ = {''s<sub>2</sub>, s<sub>3</sub>, …, s<sub>n</sub>''}. PMS5 computes the (''l'', ''d'')-motifs of ''S'' as <math>\bigcup_{L\in s_1} M_l^d (L,S^')</math>. Here ''L'' refers to an ''l''-mer.

One of the key steps in the algorithm is a [[subroutine]] to compute the common ''d''-neighborhood of three ''l''-mers. Let ''x'', ''y'', ''z'' be any three ''l''-mers. To compute ''B<sub>d</sub>(x, y, z)'', PMS5 represents ''B<sub>d</sub>(x)'' as a tree ''T<sub>d</sub>(x)''. Each node in this tree represents an ''l''-mer in ''B<sub>d</sub>(x)''. The root of ''T<sub>d</sub>(x)'' stands for the ''l''-mer x. ''T<sub>d</sub>(x)'' has a depth of <sub>d</sub>. Nodes of ''T<sub>d</sub>(x)'' are traversed in a [[Depth-first search|depth-first]] manner. The node and the ''l''-mer it represents may be used interchangeably. While the tree is [[tree traversal|traversed]], any node ''t'' will be output if ''t'' is in <math>B_d (y)\bigcap B_d (z)</math>. When any node ''t'' is visited, check if there is a descendent ''t’'' of ''t'' such that ''t’'' is in <math>B_d (y)\bigcap B_d (z)</math>. Prune the [[subtree]] rooted at ''t'' if there is no such descendent. In PMS5, the problem of checking if ''t'' has any descendent that is in <math>B_d (y)\bigcap B_d (z)</math> is formulated as an [[Integer linear program|integer linear program (ILP)]] on ten variables. This ILP is solved in O(1) time. Solving the ILP instances is done as a preprocessing step and the results are stored in a lookup table.

Algorithm PMS6<ref name="Bandyo_Sahni_Raj_2012">{{cite journal | author = Bandyopadhyay S, Sahni S, Rajasekaran S | title = PMS6: A fast algorithm for motif discovery | journal = IEEE 2nd International Conference on Computational Advances in Bio and medical Sciences | volume = | issue = | pages = 1| year = 2012 | pmid = | pmc = | doi = 10.1109/ICCABS.2012.6182627 | isbn = 978-1-4673-1321-6 }}</ref> is an extension of PMS5 that improves the [[preprocessing]] step and also it uses efficient [[Hash table|hashing]] techniques to store the lookup tables. As a result, it is typically faster than PMS5.

Shibdas Bandyopadhyay, Sartaj Sahni, Sanguthevar Rajasekaran, "PMS6: A fast algorithm for motif discovery," iccabs, pp.1-6, 2012 IEEE 2nd International Conference on Computational Advances in Bio and medical Sciences, 2012

===== qPMSPrune and qPMS7 =====
Given a set ''S''={''s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub>''} of strings, and integers ''l'', ''d'', and ''q'', an (''l, d, q'')-motif is defined to be a string ''M'' of length ''l'' that occurs in at least ''q'' of the ''n'' input strings within a Hamming distance of ''d''. The qPMS (''Quorum Planted Motif Search'') problem is to find all the (''l, d, q'')-motifs present in the input strings. The qPMS problem captures the nature of motifs more precisely than the PMS problem does because, in practice, some motifs may not have motif instances in all of the input strings.
Any algorithm for solving the qPMS problem (when ''q'' ≠ ''n'') is typically named with a prefix of `''q'''. qPMSPrune is one of the first algorithms to address this version of the PMS problem.<ref name="Raj_Davila_Balla_2007" /> qPMSPrune exploits the following fact: If ''M'' is any (''l, d, q'')-motif of the input strings ''s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub>'', then there exists an ''i'' (with 1 ≤ ''i'' ≤ ''n'' – ''q'' + 1) and an ''l''-mer <math>{x\in s_i}</math> such that ''M'' is in ''B<sub>d</sub>(x)'' and ''M'' is an (''l, d, q''-1)-motif of the input strings excluding ''s<sub>i</sub>''. The algorithm processes every ''s<sub>i</sub>'', 1≤ ''i'' ≤ ''n''. While processing ''s<sub>i</sub>'', it considers every ''l''-mer ''x'' of ''s<sub>i</sub>''. When considering ''x'', it constructs ''B<sub>d</sub>(x)'' and identifies elements of ''B<sub>d</sub>(x)'' that are (''l, d, q''-1) motifs (with respect to input strings other than ''s<sub>i</sub>''). ''B<sub>d</sub>(x)'' is represented as a tree with ''x'' as the root. This tree will be traversed in a [[Depth-first search|depth first]] manner. The algorithm does not traverse the entire tree. Some of the subtrees are pruned using effective pruning conditions. In particular, a subtree is pruned if it can be inferred that none of the nodes in this subtree carries a motif of interest.

Algorithm qPMS7<ref name="Raj_Hieu_2012">{{cite journal | author = Dinh H, Rajasekaran S, Davila J | title = qPMS7: a fast algorithm for finding (ℓ, d)-motifs in DNA and protein sequences | journal = PLoS ONE | volume = 7 | issue = 7 | pages = e41425 | year = 2012 | pmid = 22848493 | pmc = 3404135 | doi = 10.1371/journal.pone.0041425 | editor1-last = Brusic | editor1-first = Vladimir }}</ref> is an extension of qPMSPrune. Specifically, it is based on the following observation: If ''M'' is any (''l, d, q'')-motif of the input strings ''s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub>'', then there exist 1 ≤ ''i'' ≠ ''j'' ≤ ''n'' and ''l''-mer <math>x\in s_i</math> and ''l''-mer <math>y\in s_j</math> such that ''M'' is in <math>B_d (x)\bigcap B_d (y)</math> and ''M'' is an (''l, d, q''-2)-motif of the input strings excluding ''s<sub>i</sub>'' and ''s<sub>j</sub>''. The algorithm considers every possible pair (''i, j''), 1≤ ''i, j'' ≤ ''n'' and ''i'' ≠ ''j''. For any pair (''i'', ''j''), every possible pair of ''l''-mers (''x, y'') is considered (where ''x'' is from ''s<sub>i</sub>'' and ''y'' is from ''s<sub>j</sub>''). While considering any ''x'' and ''y'', the algorithm identifies all the elements of <math>B_d (x)\bigcap B_d (y)</math> that are (''l, d, q''-2) motifs (with respect to input strings other than ''s<sub>i</sub>'' and ''s<sub>j</sub>''). An [[Directed acyclic graph|acyclic graph]] is used to represent and explore <math>B_d (x)\bigcap B_d (y)</math>. Call this graph ''G<sub>d</sub>(x, y)''.  ''G<sub>d</sub>(x, y)'' is traversed in a depth first manner. Like in qPMSPrune, qPMS7 also employs some pruning conditions to prune subgraphs of ''G<sub>d</sub>(x, y)''.

==== RISOTTO ====
RISOTTO<ref name="Pisanti2006" /> employs a [[suffix tree]] to identify the (''l, d'')-motifs. It is somewhat similar to PMS0. For every ''l''-mer in ''s<sub>1</sub>'', it generates the ''d''-neighborhood and for every ''l''-mer in this neighborhood it walks through a suffix tree to check if this ''l''-mer is an (''l, d'')-motif.
Voting<ref name="Chin_2005" /> is similar to PMS1. Instead of using radix sorting, it uses hashing to compute ''L<sub>i</sub>''’s and their [[Intersection (set theory)|intersections]].

=== Relative performance ===
PMS algorithms are typically tested on random benchmark data generated as follows: Twenty strings each of length 600 are generated randomly from the alphabet of interest. The motif ''M'' is also generated randomly and planted in each of the input strings within a Hamming distance of ''d''. The motif instances are also generated randomly. Certain instances of the (''l, d'')-motif problem have been identified to be ''challenging''. For a given value of ''l'', the instance (''l, d'') is called challenging if ''d'' is the smallest integer for which the expected number of (''l, d'')-motifs that occur by random chance (in addition to the planted one) is one or more. For example, the following instances are challenging: (9, 2), (11, 3), (13, 4), (15, 5), (17, 6), (19, 7), etc. The performance of PMS algorithms is customarily shown only for challenging instances. Following is a table of time comparison of different PMS algorithms on the challenging instances of DNA sequences for the special case. This table is taken from the paper qPMS7.<ref name="Raj_Hieu_2012" /> In this table several algorithms have been compared: qPMSPrune,<ref name="Raj_Davila_Balla_2007" /> qPMSPruneI,<ref name="Raj_Hieu_2012" /> Pampa,<ref name="Davila_Balla_Raj_techrpt">{{cite journal | author = Davila J, Balla S, Rajasekaran S | title = Pampa: An improved branch and bound algorithm for planted (l, d) motif search | journal = Technical Report | year = 2007 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6500&rep=rep1&type=pdf }}</ref> Voting,<ref name="Chin_2005" /> RISOTTO,<ref name="Pisanti2006" /> PMS5,<ref name="Raj_Din_Kundeti_2012" /> PMS6,<ref name="Bandyo_Sahni_Raj_2012" /> qPMS7.<ref name="Raj_Hieu_2012" />

In the following table, the alphabet ∑={''A'',''C'',''G'',''T''}, ''n''=20, ''m''=600, and ''q''=''n''=20.

{| class="wikitable" style="margin: 1em auto 1em auto;"

|+TIME COMPARISON OF DIFFERENT PMS ALGORITHMS
|-
! Algorithm !! (13,4) !! (15,5) !! (17,6) !! (19,7) !! (21,8) !! (23,9)
|-
! qPMS7
| 47 s || 2.6 m || 11&nbsp;m || 0.9 h || 4.3 h || 24 h
|-
! PMS6
| 67 s || 3.2 m || 14&nbsp;m || 1.16 h || 5.8 h || -
|-
!PMS5
| 117 s || 4.8 m || 21.7 m || 1.7 h || 9.7 h || 54
|-
! qPMSPruneI
| 17 s || 2.6 m || 22.6 m || 3.4 h || 29 h || -
|-
! Pampa
| 35 s || 6&nbsp;m || 40&nbsp;m || 4.8 h || - || -
|-
! qPMSPrune
| 45 s || 10.2 m || 78.7 m || 15.2 h || - || -
|-
! Voting
| 104 s || 21.6 m || - || - || - || -
|-
! RISOTTO
| 772 s || 106&nbsp;m || - || - || - || -
|}

== References ==
{{reflist|35em}}

== External links ==
* {{cite web | url = http://motifsearch.com | title = PMS Motif Search | author = Rajasekaran S, Dinh H | publisher = University of Connecticut }}
* {{cite web | url = http://pms.engr.uconn.edu | title = Panoptic Motif Search| author = Rajasekaran S, Dinh H | publisher = University of Connecticut }}

[[Category:Bioinformatics]]
[[Category:Computational biology]]