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 motifs within a set of nucleic acid or peptide sequences.
PMS is known to be NP-complete. The 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.
The problem of identifying meaningful patterns (e.g., motifs) from biological data has been studied extensively since they play a vital role in understanding gene function, human disease, and may serve as therapeutic drug targets.
Description The search problem may be summarized as follows:
Input are n strings (s1, s2, ... , sn) 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 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 = {s1, s2, s3, ..., sn} 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 dH(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 dH(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 dH(a, S) stand for maxsєSdH(a, s). Let u be any l-mer. Then, the d-neighborhood of u, (denoted as Bd(u)), is nothing but the set of all the l-mers v such that dH(u, v) ≤ d. In other words, Bd(u)={v: dH(u, v)≤d}. Refer to any such l-mer v as a d-neighbor of u. Bd(x, y) is used to denote the common d-neighborhood of x and y, where x and y are two l-mers. Bd(x, y) is nothing but the set of all l-mers that are within a distance of d from both x and y. Similarly, Bd(x, y, 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 (or heuristic) algorithms include Random Projection, PatternBranching, MULTIPROFILER, CONSENSUS, and ProfileBranching. These algorithms have been experimentally demonstrated to perform well.
Random projection The algorithm 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.
Pattern branching This algorithm is a local searching algorithm. If u is any l-mer, then there are 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), (Brazma, et al. 1998), (Galas, et al. 1985), (Sinha, et al. 2000), (Staden 1989), (Tompa 1999), (Helden, et al. 1998) (Rajasekaran, et al.), (Davila and Rajasekaran 2006), (Davila, Balla, and Rajasekaran 2006), Voting and RISOTTO.
WINNOWER and SP-STAR The WINNOWER algorithm 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 . 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 M1, M2, ..., and Mn 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 . This algorithm runs in a reasonable amount of time in practice especially for small values of d. Another algorithm called SP-STAR, 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) employs expectation maximization algorithms while Gibbs sampling is used by (Lawrence et al., 1993). MULTIPROFILER MEME, 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 Rajasekaran. Some of these algorithms are described below.
PMS0 PMSo works as follows. Let s1, s2, ..., sn be a given set of input strings each of length m. Let C be the collection of l-mers in s1. Let C′ = ∪u∈CBd(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 .
PMS1 This algorithm is based on radix sorting and has the following steps.
Generate the set of all l-mers in each input string. Let Ci correspond to the l-mers of si, for 1≤i≤n. For each l-mer u in Ci (1 < i < n), generate Bd(u). Let Li be a collection of all of these neighbors (corresponding to all the l-mers of si). Sort Li (using radix sort) and eliminate any duplicates. Compute :. This can be done by merging the lists L1, L2, ..., Ln. 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 si, there will be at least one position ij such that a k-mer of Q occurs starting from ij. Another k-mer of Q occurs starting from ij +1 and so on, with the last k-mer occurring at ij + l – k. An l-mer can be obtained by combining these k-mers that occur starting from each such ij.
PMS2 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 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 M1 refer to the first half of M and M2 be the next half. Let s= a1a2...am 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′=aiai+1...ai+l'-1 and s′′ =ai+l'...ai+l-1.
It is clear that either the Hamming distance between M1 and s′ is at most d′ or the Hamming distance between M2 and s′′ is at most d′. Either M1 or M2 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 M1 or M2 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 structure for the motif candidates and uses a branch-and-bound algorithm to reduce the search space. Let S = {s1, s2, ..., sn} be a given set of input strings. PMSprune follows the same strategy as PMS0: For every l-mer y in s1, 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 s1 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 dH(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. If each node in the tree is visited for each l-mer y in s1, 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 dH(x, S) and h to prune the descendants of x. PMSPrune calculates the value of dH(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