Planted motif search

Examples of approximation (or heuristic) algorithms include Random Projection,[2] PatternBranching,[3] MULTIPROFILER,[1] CONSENSUS,[4] and ProfileBranching.[3] These algorithms have been experimentally demonstrated to perform well.

The algorithm[2] 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 2d. 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 (EM) algorithm is used to check if an (l, d) motif can be found using the l-mers in the bucket.

This algorithm[3] is a local searching algorithm. If u is any l-mer, then there are ${\displaystyle {\tbinom {l}{d}}3^{d}}$ 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.

Many exact algorithms are known for solving the PMS problem as well. Examples include the ones in (Martinez 1983),[5] (Brazma, et al. 1998),[6] (Galas, et al. 1985),[7] (Sinha, et al. 2000),[8] (Staden 1989),[9] (Tompa 1999),[10] (Helden, et al. 1998)[11] (Rajasekaran, et al.),[12] (Davila and Rajasekaran 2006),[13] (Davila, Balla, and Rajasekaran 2006),[14] Voting[15] and RISOTTO.[16]

The WINNOWER algorithm[17] 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 2d. It can be shown that the expected Hamming distance between A and B is ${\displaystyle 2d-{\tfrac {4d^{2}}{3l}}}$. 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 2d and they come from two different input strings.

If M is an (l, d) motif and if M₁, M₂, ..., and M_n are instances of M in the input strings, then, clearly, these instances will form a 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 problem is 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 ${\displaystyle O(N^{2d+1})}$. This algorithm runs in a reasonable amount of time in practice especially for small values of d. Another algorithm called SP-STAR,[17] 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)[18] employs expectation maximization algorithms while Gibbs sampling is used by (Lawrence et al., 1993).[19] MULTIPROFILER[1] MEME,[20] are also known PMS algorithms.

In the last decade a series of algorithms with PMS as a prefix has been developed in the lab of Rajasekaran. Some of these algorithms are described below.

PMSo[12] works as follows. Let s₁, s₂, ..., s_n be a given set of input strings each of length m. Let C be the collection of l-mers in s₁. Let C′ = ∪_u∈CB_d(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 ${\displaystyle O(m^{2}nl{\tbinom {l}{d}}3^{d})}$.

This algorithm[12] is based on radix sorting and has the following steps.

1. Generate the set of all l-mers in each input string. Let C_i correspond to the l-mers of s_i, for 1≤i≤n.
2. For each l-mer u in C_i (1 < i < n), generate B_d(u). Let L_i be a collection of all of these neighbors (corresponding to all the l-mers of s_i).
3. Sort L_i (using radix sort) and eliminate any duplicates.
4. Compute :${\displaystyle \bigcap _{i=1}^{n}L_{i}.}$. This can be done by merging the lists L₁, L₂, ..., L_n. All the l-mers in this intersection are valid (l, d) motifs.

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_i, there will be at least one position i_j such that a k-mer of Q occurs starting from i_j. Another k-mer of Q occurs starting from i_j +1 and so on, with the last k-mer occurring at i_j + l – k. An l-mer can be obtained by combining these k-mers that occur starting from each such i_j.

PMS2[12] 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.

This algorithm[12] enables one to handle large values of d. Let d′=d/2. Let M be the motif to be found with |M|=l=2l′ for some integer l′. Let M₁ refer to the first half of M and M₂ be the next half. Let s= a₁a₂...a_m 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_ia_i+1...a_i+l'-1 and s′′ =a_i+l'...a_i+l-1.

It is clear that either the Hamming distance between M₁ and s′ is at most d′ or the Hamming distance between M₂ and s′′ is at most d′. Either M₁ or M₂ 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₁ or M₂ 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.

This algorithm introduces a tree structure for the motif candidates and uses a branch-and-bound algorithm to reduce the search space.[21] Let S = {s₁, s₂, ..., s_n} be a given set of input strings. PMSprune follows the same strategy as PMS0: For every l-mer y in s₁, 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:

1. It generates the d-neighborhood of every l-mer y in s₁ 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_H(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 manner.
2. If each node in the tree is visited for each l-mer y in s₁, 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.
3. For an l-mer x, which corresponds to a node in a subtree of height h, the algorithm uses the value of d_H(x, S) and h to prune the descendants of x.
4. PMSPrune calculates the value of d_H(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[22] 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.

1. 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.
2. for each l-mer v in C do

Check if v is a valid motif in O(mnl) time. If so, output v.

PMS5[23] is an extension of PMS0. If S = {s₁, s₂, ..., s_n} is a set of strings (not necessarily of the same length), let ${\displaystyle M_{l}^{d}(S)}$ denote the (l, d)-motifs present in S. Let S′ = {s₂, s₃, ..., s_n}. PMS5 computes the (l, d)-motifs of S as ${\displaystyle \bigcup _{L\in s_{1}}M_{l}^{d}(L,S^{'})}$. 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_d(x, y, z), PMS5 represents B_d(x) as a tree T_d(x). Each node in this tree represents an l-mer in B_d(x). The root of T_d(x) stands for the l-mer x. T_d(x) has a depth of _d. Nodes of T_d(x) are traversed in a depth-first manner. The node and the l-mer it represents may be used interchangeably. While the tree is traversed, any node t will be output if t is in ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$. When any node t is visited, check if there is a descendent t′ of t such that t′ is in ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$. 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 ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$ is formulated as an 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[24] is an extension of PMS5 that improves the preprocessing step and also it uses efficient 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

Given a set S={s₁, s₂, ..., s_n} 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.[21] qPMSPrune exploits the following fact: If M is any (l, d, q)-motif of the input strings s₁, s₂, ..., s_n, then there exists an i (with 1 ≤ i ≤ n – q + 1) and an l-mer ${\displaystyle {x\in s_{i}}}$ such that M is in B_d(x) and M is an (l, d, q-1)-motif of the input strings excluding s_i. The algorithm processes every s_i, 1≤ i ≤ n. While processing s_i, it considers every l-mer x of s_i. When considering x, it constructs B_d(x) and identifies elements of B_d(x) that are (l, d, q-1) motifs (with respect to input strings other than s_i). B_d(x) is represented as a tree with x as the root. This tree will be traversed in a 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[25] 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₁, s₂, ..., s_n, then there exist 1 ≤ i ≠ j ≤ n and l-mer ${\displaystyle x\in s_{i}}$ and l-mer ${\displaystyle y\in s_{j}}$ such that M is in ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$ and M is an (l, d, q-2)-motif of the input strings excluding s_i and s_j. 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_i and y is from s_j). While considering any x and y, the algorithm identifies all the elements of ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$ that are (l, d, q-2) motifs (with respect to input strings other than s_i and s_j). An acyclic graph is used to represent and explore ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$. Call this graph G_d(x, y). G_d(x, y) is traversed in a depth first manner. Like in qPMSPrune, qPMS7 also employs some pruning conditions to prune subgraphs of G_d(x, y).

RISOTTO[16] employs a suffix tree to identify the (l, d)-motifs. It is somewhat similar to PMS0. For every l-mer in s₁, 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[15] is similar to PMS1. Instead of using radix sorting, it uses hashing to compute L_i's and their intersections.

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.[25] In this table several algorithms have been compared: qPMSPrune,[21] qPMSPruneI,[25] Pampa,[26] Voting,[15] RISOTTO,[16] PMS5,[23] PMS6,[24] qPMS7.[25]

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