Figures
Abstract
Detection of rare events happening in a set of DNA/protein sequences could lead to new biological discoveries. One kind of such rare events is the presence of patterns called motifs in DNA/protein sequences. Finding motifs is a challenging problem since the general version of motif search has been proven to be intractable. Motifs discovery is an important problem in biology. For example, it is useful in the detection of transcription factor binding sites and transcriptional regulatory elements that are very crucial in understanding gene function, human disease, drug design, etc. Many versions of the motif search problem have been proposed in the literature. One such is the -motif search (or Planted Motif Search (PMS)). A generalized version of the PMS problem, namely, Quorum Planted Motif Search (qPMS), is shown to accurately model motifs in real data. However, solving the qPMS problem is an extremely difficult task because a special case of it, the PMS Problem, is already NP-hard, which means that any algorithm solving it can be expected to take exponential time in the worse case scenario. In this paper, we propose a novel algorithm named qPMS7 that tackles the qPMS problem on real data as well as challenging instances. Experimental results show that our Algorithm qPMS7 is on an average 5 times faster than the state-of-art algorithm. The executable program of Algorithm qPMS7 is freely available on the web at http://pms.engr.uconn.edu/downloads/qPMS7.zip. Our online motif discovery tools that use Algorithm qPMS7 are freely available at http://pms.engr.uconn.edu or http://motifsearch.com.
Citation: Dinh H, Rajasekaran S, Davila J (2012) qPMS7: A Fast Algorithm for Finding (ℓ, d)-Motifs in DNA and Protein Sequences. PLoS ONE 7(7): e41425. https://doi.org/10.1371/journal.pone.0041425
Editor: Vladimir Brusic, Dana-Farber Cancer Institute, United States of America
Received: March 12, 2012; Accepted: June 21, 2012; Published: July 24, 2012
Copyright: © 2012 Dinh et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Funding: This work has been supported in part by the following grants: NSF 0829916 and NIH R01-LM010101. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. No additional external funding was received for this study.
Competing interests: The authors have declared that no competing interests exist.
Introduction
Detection of rare events happening in a set of DNA/protein sequences often provides the main clue leading to new biological discoveries. One kind of such rare events is the presence of patterns called motifs. For example, regulatory regions in a genome such as promoters, enhancers, locus control regions, etc., contain motifs that control many biological processes such as gene expression (see [1]). Basically, proteins known as transcription factors regulate the expression of a gene by binding to locations of motifs in regulatory regions. For instance, transcription factors such as TFIID, TFIIA and TFIIB usually bind to sequence 5′-TATAAA-3′ in the promoter region of a gene in order to initiate its transcription. Such motifs and their locations in regulatory regions, i.e., binding sites, are important and helpful to decipher the regulatory mechanism of gene expression, which is very sophisticated. As a result, motif identification plays an important role in biological studies.
Motif prediction is usually the first stage in the process of identifying motifs. An extensive amount of research has been done on this topic over the past twenty years. In the literature, many approaches for motif prediction have been proposed. One of them is a combinatorial approach that has proven to be more accurate than the others. Even in this combinatorial approach, many variations can be found such as Planted Motif Search (PMS), Simple Motif Search (SMS), and Edit-distance-based Motif Search (EMS) (see e.g., [2]).
Among the combinatorial variations, the PMS Problem has been the most widely studied perhaps because it offers a higher level of accuracy in modeling the true motifs than the others. Motifs typically occur with mutations at binding sites. The binding sites are referred to as instances of a motif. A motif in this model is referred to as a -motif where
is its length and
is the maximum number of mutations allowed for its instances. Given a set of sequences, the objective of the PMS problem is to find all the
-motifs in them. The formal definition of the PMS Problem is given in Section 0.1. An algorithm that solves the PMS problem is called a PMS Algorithm.
Owing to its importance, the PMS problem has been extensively studied in the past twenty years. Many PMS algorithms have been proposed in the literature. There are two kinds of PMS algorithms, namely, exact and approximate. An exact algorithm always finds all the -motifs present in the input sequences. An approximate algorithm may not find all the motifs. In this paper we only consider exact algorithms. The (exact variant of the) PMS problem has been shown to be NP-hard which means that there is unlikely to be a PMS algorithm that takes only polynomial time. As a result, all the existing exact PMS Algorithms take time that is exponential time in some of the parameters in the worst case. In practice, all known PMS Algorithms (both exact and approximate) are only able to find
-motifs for up to certain values of
and
. The most recent exact algorithms that have been proposed in the literature are Algorithm PMS6 due to [3], Algorithm PMS5 due to [4], Algorithm Pampa due to [5], Algorithm PMSPrune due to [6], Algorithm PMS3 due to [7], Algorithm Voting due to [8], and Algorithm RISSOTO due to [9]. Some earlier PMS algorithms are due to [10], [11], [12], [13], [14], [15], [16], and [17]. Among these known algorithms, Algorithm PMS6 is considered the fastest one and has been developed closely following the ideas of Algorithm PMS5.
Approximate PMS algorithms usually tend to be faster than exact PMS algorithms. Typically, approximate PMS algorithms employ heuristics such as local search, Gibbs sampling, expectation optimization, etc. Examples of approximate algorithms are Algorithm MEME due to [18], Algorithm PROJECTION due to [19], Algorithm GibbsDNA due to [20], Algorithm WINNOWER due to [21], and Algorithm RandomProjection due to [22]. Some other approximate PMS algorithms are Algorithm MULTIPROFILER due to [23], Algorithm PatternBranching due to [24], Algorithm ProfileBranching due to [24], and Algorithm CONSENSUS due to [25].
A generalized version of the PMS Problem, namely Quorum Planted Motif Search (qPMS) Problem, was first considered in [6]. The qPMS problem is to find all the motifs that have motif instances present in q out of the n input sequences. 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 sequences. The qPMS problem is formally defined in Section 0.1. An algorithm that solves the qPMS problem is called a qPMS algorithm. qPMS algorithms can be used to find DNA motifs and protein motifs as well as transcription factor binding sites. The larger the values of and d that a qPMS algorithm can handle, the more accurate will be the motifs it finds. So it is important to solve the qPMS problem instances with large values of
and d. However, solving the qPMS problem is a difficult task since it is even harder than the PMS problem. To the best of our knowledge, the currently best exact qPMS algorithm is Algorithm qPMSPrune due to [6] that can only solve instances up to
and
for
, where n is the number of input sequences. In this paper, we propose a new algorithm named Algorithm qPMS7 that can solve larger instances. Also, qPMS7 is ten times as fast as qPMSPrune. In addition, when applied to the PMS problem, our algorithm is faster than the best PMS algorithm, i.e., Algorithm PMS6 due to [3].
Methods
0.1 Problems Definition and Notations
Definition 0.1 A string of length
is called an
-mer.
Definition 0.2 Given two and
with
, we use the notation
if x is a contiguous substring of s. In other words,
if there exists
such that
for every
. We also say that x is an
-mer in s.
Definition 0.3 Given two strings and
of equal length, the Hamming distance between
and
, denoted by
, is the number of mismatches between them. In other words,
, where
is the indicator at position
.
if
, and
otherwise.
Definition 0.4 Given two strings and
with
, the Hamming distance between
and
, denoted by
, is
.
Definition 0.5 Given a set of strings
of length
each, a string
of length
is called an
-motif of the strings if there are at least
out of the
strings such that the Hamming distance between each one of them and
is no more than
.
is called an
-motif for short if the set of strings is clear.
The definition of Quorum Planted Motif Search (qPMS) Problem is as follows. Given input strings
of length
each, three integer parameters
,
and
, find all the
-motifs of the input strings. The Planted Motif Search (PMS) problem is a special case of the qPMS problem when
. In this paper, we propose a fast algorithm for the qPMS problem.
0.2 The Existing Algorithm qPMSPrune
Algorithm qPMSPrune for the qPMS problem was proposed by [6]. For the sake of completeness, we will describe Algorithm qPMSPrune in this section briefly because our new algorithm is partially based on it. For more details on Algorithm qPMSPrune, the readers are referred to [6].
Algorithm qPMSPrune uses the -neighborhood concept defined as follows.
Definition 0.6 Given a string , we define the
-neighborhood of
,
, to be
.
It is easy to see that , where
is the alphabet of interest. Notice that
depends only on
,
and
. For this reason, we define
.
Algorithm qPMSPrune is based on the following observation. Any -motif of the input strings must be in
for some
-mer
in some input string
and also it must be a
-motif of the input strings excluding
. This observation can be rewritten formally as follows.
Observation 0.1 Let be any
-motif of the input strings
. Then there exists an
(with
) and a
-mer
such that
is in
and
is a
-motif of the input strings excluding
.
The above observation suggests the following algorithm. Compute for every
-mer
in each input string
for
. For each
-mer in the neighborhoods thus computed, check if it is a
-motif of the input strings excluding
. This simple algorithm can be improved further as shown in [6]. The key observation is that it is sufficient to consider each input string
for
:
Observation 0.2 Let be any
-motif of the input strings
. Then there exists an
(with
) and a
-mer
such that
is in
and
is a
-motif of the input strings excluding
.
Algorithm qPMSPrune is based on the above observation. For any -mer
, it represents
as a tree
using the following rules.
- Each node in
is a pair
where
is an
-mer and
is an integer between
and
such that
. A node
is referred to as a
-mer
if
is clear.
- Let
and
. A node
is the parent of a node
if and only if
- (a)
.
- (b)
(From Rule 1,
).
- (c)
for any
.
- (a)
- The root of
is
.
- The depth of
is
.
For example, the tree with alphabet
is illustrated in Figure 1.
with alphabet
. The value of
at each node is the location of its shaded letter. For example,
at node
,
at node
.
Clearly, the following properties of can be inferred directly from the rules.
- Each node in
is uniquely associated with an
-mer in
and vice versa.
- If a node
is a parent of a node
, then
. As a result, if a node
is at level
, then
.
The algorithm traverses the tree in a depth-first manner. At each node
, it computes
incrementally from its parent for
. This operation can be done in
time by the incremental computation shown in [6]. Let
be the number of input strings
such that
. Obviously if
then
is a
-motif of the input strings excluding
. If this condition is satisfied, it outputs
as a
-motif of the entire input strings.
Algorithm qPMSPrune prunes certain nodes (and their descendants) in that cannot possibly be
-motifs. Under what conditions can we prune the node
? Let
be the number of input strings
such that
. Observe that if
then none of the nodes in the subtree rooted at node
could be a
-motif. This is because if there is a node
in the subtree which is a
-motif, then there are at least
input strings
such that
. Consider such an input string
. By the triangle inequality,
. This inequality will infer that
. Therefore, if the condition
occurs, it can safely prune the subtree rooted at node
without missing any
-motif. The pseudo-code of Algorithm qPMSPrune is described as follows.
Algorithm qPMSPrune
For each do:
Traverse the tree in a depth-first manner. At each node
, do the following steps.
- Incrementally compute
from its parent for
.
- Let
be the number of input strings
such that
. If
, output
.
- Let
be the number of input strings
such that
. If
, then prune the subtree rooted at node
. Otherwise, explore its children.
It is easy to see that the time and space complexities of Algorithm qPMSPrune are and
, respectively.
0.3 A Computational Technique Improving upon Algorithm qPMSPrune
In this section, we propose a speedup technique to improve the runtime of Algorithm qPMSPrune. Specifically, the technique will reduce the time taken for computing Hamming distances in step (1) of Algorithm qPMSPrune. Recall that the operation takes at least
time in Algorithm qPMSPrune because it considers every
-mer in each input string
. We observe that some
-mers can be ignored without changing the result since we notice that we just need to count
and
. Any
-mer
in
can be ignored, as far as a node
in the tree
is concerned, if
. The reason for this will be given in the next paragraph. Based on this observation, the technique is implemented as follows. At each node
, we store a list of surviving
-mers for each input string
. It is sufficient to store the positions of the
-mers in the input strings. If the list of surviving
-mers of
is empty, then we set
. In terms of the incremental distance computation, only the surviving
-mers are considered. The runtime of the operation now depends on the sizes of the lists of surviving
-mers.
The reason for ignoring any -mer
in
, as far as a node
in the tree
is concerned, if
is as follows. If this condition occurs, then for any node
in the subtree rooted at node
we have:
. Therefore, ignoring
-mer
at any node
in the subtree rooted at node
will not change its
. The value of
at node node
may become smaller as a result of ignoring the
-mer
. However, the pruning condition based on
in step (3) in the pseudo-code still holds.
Another way to view the ignoring condition is as follows. Consider a node in the tree
and an
-mer
in the input string
. Let us separate each of
and
into two parts based on
, namely,
and
where
and
. Notice that
. Then the inequality
is equivalent to
. In other words,
and
are disjoint. Notice that this condition is independent of
. This view helps us in designing our best algorithm qPMS7 which is described in Section 0.4.
The speedup technique reduces the runtime of Algorithm qPMSPrune drastically because the deeper a node is, the smaller will be the size of its list of surviving -mers. Note that the number of nodes at a depth of
from the root will be exponential in
. In practice, the runtime of Algorithm qPMSPrune is improved by a factor of around 5 when this technique is used (see Table 1 and Table 2). However, it does not change the worst case time complexity of Algorithm qPMSPrune, theoretically.
0.4 Our Best Algorithm qPMS7
In this section, we propose a fast algorithm called qPMS7 for the qPMS problem. Algorithm qPMS7 is a generalized version of Algorithm qPMSPrune combined with the core idea of Algorithm PMS5 which was introduced in [4].
Recall that Algorithm qPMSPrune considers one -mer
in a specific input string
at a time. Algorithm qPMS7 extends Algorithm qPMSrune by considering two
-mers
and
in two different input strings
and
. An observation similar to that of Algorithm qPMSPrune can be obtained as follows.
Observation 0.3 Let be any
-motif of the input strings
. Then there exist
and
-mer
and
-mer
such that
is in
and
is a
-motif of the input strings excluding
and
.
Using an argument similar to the one in [6], we infer that it is enough to consider every pair of input strings and
with
. As a result, the above observation gets strengthened as follows.
Observation 0.4 Let be any
-motif of the input strings
. Then there exist
and
-mer
and
-mer
such that
is in
and
is a
-motif of the input strings excluding
and
.
Like Algorithm qPMSPrune, Algorithm qPMS7 uses a routine that finds all of the motifs such that
is in
and is a
-motif of the input strings excluding
and
. Recall that Algorithm qPMSPrune explores
by traversing the tree
. In Algorithm qPMS7, we also explore
by traversing an acyclic graph, denoted as
, with similar construction rules. The rules for constructing
are given below.
- Each node in
is a pair
where
is an
-mer and
is an integer between
and
. A node
is referred to as
-mer
if
is clear. Let
and
where
and
. Node
must satisfy the following constraints:
- (a)
if
, otherwise,
.
- (b)
and
.
- (a)
- Let
and
. There is an arc from a node
to a node
if and only if
- (a)
.
- (b)
.
- (c)
for any
.
- (a)
It is not hard to see that if we traverse the graph in a depth-first manner starting from node
, then all the
-mers in
will be visited. For example, Figure 2 illustrates the visited nodes in the graph
in a depth-first manner starting from node
where the alphabet
.
Visited nodes in in a depth-first manner when the starting node is
. In this example,
. The value of
at each node is the location of its shaded letter. For example,
at node
.
Algorithm qPMS7 traverses the graph in a depth-first manner with the starting node
. During the traversal, at each node
it computes
incrementally from its parent for
. With the same method as the one in Algorithm qPMSPrune, we can achieve this task in
time. Also, it is easy to see that if
then
is a
-motif of the input strings excluding
and
, where
is the number of input strings
such that
. If this is the case, it outputs
as a
-motif of the entire input strings.
Algorithm qPMS7 also uses a similar pruning strategy to that of Algorithm qPMSRune and the speedup technique discussed in Section 0.3. In this case, the speedup technique ignores some -mers in
when computing
at each node
during the traversal of the graph
. The ignoring condition of an
-mer
in
for this case resembles that in Section 0.3. Let
and
where
. It is not hard to see that
-mer
can be safely ignored if
is empty. Checking for this condition can be done in
time using the incremental computation shown in [4]. During the traversal of the graph, at each node
) we also store a list of surviving
-mers for each input string
. At node
, if the list of surviving
-mers of an input string is empty, then the input string will contribute nothing to any descendant node of
in order for that descendant to be a
-motif. Therefore, the pruning condition is
where
is the number of input strings whose lists of surviving
-mers are not empty. The following pseudo-code describes Algorithm qPMS7.
Algorithm qPMS7
1. For each do:
(a) Traverse the graph in a depth-first manner starting from node
. At each node
, do the following steps.
- Incrementally compute
from its parent for
.
- Let
be the number of input strings
such that
. If
, output
.
- Let
be the number of input strings whose lists of surviving
-mers are not empty. If
, then backtrack. Otherwise, explore its children.
Theoretically, the time and space complexities of Algorithm qPMS7 are and
, respectively. In the worst case scenario, the runtime of Algorithm qPMS7 is worse than that of Algorithm qPMSPrune by a factor of
. However, Algorithm qPMS7 is much faster than Algorithm qPMSPrune in practice, as shown in Section 0.5.
Algorithm qPMS7 also employs the following observation which has been used in many prior works such as [6] and [26]. Let be any
motif in inputs strings
. Let
be an instance of
in
(for
). Then the Hamming distance between
and
is
for any
and
(with
). In other words, if
is any
-mer in some
, then it could possibly be an instance of
only if there are at least
out of
sequences
‘s,
, that have an
-mer
such that the Hamming distance between
and
is
. This observation can be utilized to preprocess the input strings so that for any input string only those
-mers that satisfy the above condition are kept (and the other
-mers are ignored from further processing).
0.5 Transcription Factor Binding Sites Discovery
In this section we will discuss how to use a qPMS Algorithm, e.g., Algorithm qPMS7, to discover transcription factor-binding sites. Given a set of DNA strings that likely contains transcription factor-binding sites, we propose a general framework to find them. The framework consists of two phases. The first phase will select a set of motifs by repeatedly calling the qPMS Algorithm on different values of and
. The second phase will use a scoring function to eliminate some of the motifs returned in the first phase, and then identify the transcription factor-binding sites based on the surviving motifs.
In the first phase we employ different values, ranging between and
, for the length
of motifs, where
and
are user-specified parameters. For each value of
, we let
range from
to
, where
is another user-specified parameter, and call the best qPMS algorithm (let it be Algorithm
) to find
-motifs. In this process, if some
-motif(s) are found, we add them to the set of motifs. The pseudo-code of the first phase follows.
Phase I: selecting candidate motifs
Input: a set of strings
Parameters: and
Output: a set of -motifs
1:
2: for to
to do
3: for d = 0 to do
4: Run the fastest qPMS Algorithm to find
-motifs of the input strings
5: if algorithm takes too long then
6: Terminate algorithm
7: break the for loop of
8: end if
9: Let be the set of
-motifs returned by algorithm
10: if is NOT empty then
11:
12: break the for loop of
13: end if
14: end for
15: end for
In the second phase, we sort the -motifs according to their scores and pick the top
motifs, where
is a user-specified parameter. For each picked
-motif
and each input string
, transcription binding sites in
are identified as follows. We consider every
-mer
in
and output the location of
in
as a transcription binding site if
. The following pseudo-code describes the second phase.
Phase II: identifying transcription factor binding sites
Input: a set of strings and a set of -motifs
Parameters: a scoring function and
Output: a set of binding sites on the input strings
1: Sort -motifs in
according to the scoring function
2: Pick the top
-motifs in
after sorting
3: for each picked -motif
do
4: for each input string do
5: Identify all the -mers
in
such that
6: Output the location of each such -mer
in
as a transcription factor binding site
7: end for
8: end for
The accuracy of the framework in discovering transcription factor-binding sites heavily depends on two factors: the qPMS Algorithm and the scoring function. Of course, the faster the qPMS Algorithm is, the more accurate will be the results it provides. Designing fast qPMS algorithms is our main focus because it is a difficult task. On the other hand, the choice of the scoring function is also critical. In general, the scoring function should measure the biological significance of a candidate motif possibly via a probabilistic model. As a rule of thumb, the smaller the probability that a motif appears (by random chance) is, the more likely will it be to be biologically significant. In addition, the impact of the scoring function on the accuracy also depends on the size of the list of candidate motifs . The larger the size is, the more will be the scoring function’s impact. For example, the scoring function called “sequence specificity” is usually used. It is defined to be
where
is the expected number of times a motif appears in string
with up to
mismatches [6].
Results
In this section we evaluate the performance of Algorithm qPMS7 on simulated as well as real data. With simulated data, we compare its runtime with that of other existing algorithms. With real data, we measure the accuracy of qPMS7 in detecting real motifs. Of course, the larger the values of and
that an algorithm can solve, the more accurate will be the results it yields because it covers a larger search space of motifs.
0.6 Experiments on Simulated Data
We compared the runtime of Algorithm qPMS7 with other well-known algorithms such as Algorithm qPMSPrune of [6], Algorithm PMS6 of [3], Algorithm PMS5 of [4], Algorithm Pampa of [5], Algorithm Voting of [8], and Algorithm RISSOTO of [9]. Recall that among these algorithms, only Algorithm qPMSPrune deals with the qPMS problem. The rest of the algorithms deal with the simpler version, i.e., the PMS problem. The improved Algorithm qPMSPrune in Section 0.3 is named qPMSPruneI. To evaluate the performance of algorithms, we usually test them on challenging and hard instances of the problem. All of these algorithms have been run on the same machine running Windows XP Operating System with a Dual Core Pentium 2.4GHz CPU and 3GB RAM. The experimental results below show that Algorithm qPMS7 is better than any other algorithm.
0.6.1 DNA sequences.
Following [21] and [6], the set of input strings of a challenging instance is typically generated as follows. Each input string is a random DNA string drawn according to the i.i.d model. A random -mer
is chosen as a
-motif and mutations of this
-mer
are planted in
out of the
input strings at random positions. The Hamming distance between
and any of these mutations is at most
. The number of input strings
and the length of each of them
are chosen to be 20 and 600, respectively.
In the case of the PMS problem, . The pairs
corresponding to challenging instances are
,
,
,
,
,
,
, and so on. To the best of our knowledge, there has not been any algorithm that can solve the challenging instance
. Therefore, Table 1 reports the runtime of the algorithms on the challenging instances up to
. Algorithms qPMS7, PMS6 and PMS5 can solve any of these challenging instances. In Table 1, the letter ‘–’ indicates that the corresponding algorithm either takes too long or uses too much memory on the corresponding challenging instance.
Following [6] and [4], we have tested the qPMS algorithms on the most difficult case of . The challenging instances for this case are identified as
,
,
,
,
,
,
, and so on. Since among the existing algorithms, only Algorithm qPMSPrune deals with the qPMS problem, we compare Algorithm qPMS7 to it. Algorithm qPMS7 can solve any challenging instance up to
. Table 2 shows the results for these challenging instances.
0.6.2 Protein sequences.
We have also tested the algorithms on synthetic protein sequences. These sequences have been generated in a manner similar to the generation of DNA strings as explained in Section 0.6.1. The number of the protein strings in each testing dataset and the length of each protein string
are chosen to be the same:
and
. For the case of
, the
pairs that correspond to challenging instances are
,
,
,
,
, and so on. For the case of
, the challenging instances are
,
,
,
,
, and so on.
Since none of the exact algorithms reported in the literature deals with the qPMS problem for protein sequences, we restrict our comparison to the algorithms qPMSPrune, qPMSPruneI, and qPMS7. Table 3 and Table 4 show the runtimes of these algorithms for the two cases and
, respectively. As the results show, Algorithm qPMS7 outperforms Algorithms qPMSPruneI and qPMSPrune on all the cases.
0.7 Experiments on Real Data
0.7.1 Finding real DNA motifs.
We tested Algorithm qPMS7 on the real datasets discussed in [27] which is commonly used to measure the accuracy of the existing algorithms (see e.g., [27], [19], and [7]). Each of the datasets is a collection of DNA orthologous sequences from many organisms. These real datasets are substantially different from the simulated data because they contain known transcription regulatory elements, i.e, known motifs. Algorithm qPMS7 was able to identify these known motifs for appropriate values of the parameters and
. We report these motifs in Table 5. However, we should mention that our results are similar to those published in [7], [6] as well as other papers.
0.7.2 Detecting transcription factor-binding sites.
We have also tested our algorithms on the biological datasets described in [28]. In this collection there are several datasets. Some strings of each of these datasets contain known transcription factor-binding sites of different lengths and the others do not. Therefore, in order to test these real datasets we rely on the framework for transcription factor-binding sites discovery described in Section 0.5. Recall that this framework needs a qPMS algorithm and a scoring function. Since Algorithm qPMS7 is currently the fastest, we employ it in this framework. Regarding the scoring function, we use the function called “sequence specificity” which is also the one used in [6], which basically is defined to be where
is the expected number of times a motif appears in string
with up to
mismatches, assuming the i.i.d model. To complete the tests, we need to choose the parameters of the framework
,
,
,
, and
. We set
,
,
,
, and
. With this setting, we obtain good results like those in [28], [6], and [4] with many transcription factor-binding sites predicted correctly. Table 6 reports some of these correctly predicted binding sites together with the predicted motifs.
Discussion
In this paper we have presented Algorithm qPMS7 for the qPMS problem and tested it on DNA as well as protein sequences. Experimental results indicate that Algorithm qPMS7 is faster than other existing algorithms, especially for large values of and
. Since Algorithm qPMS7 is a search-based algorithm, it uses a small amount of memory. This feature of Algorithm qPMS7 is a major advantage compared to other algorithms such as RISOTTO, Voting, PMS5, and PMS6 which require a large amount of memory when solving instances with large values of
and
. Another advantage of Algorithm qPMS7 over these algorithms is that they cannot deal with the qPMS problem and in particular they only handle the PMS problem.
Algorithm qPMS7 is the result of a combination of an extension of Algorithm qPMSPrune and the core idea of algorithm PMS5. In Algorithm qPMSPrune, a “pivot” -mer is used. In Algorithm qPMS7, we extended this idea by considering two pivot
-mers. This idea can be further generalized by considering more than two pivot
-mers,
In this paper we have also proposed a framework for transcription factor-binding sites discovery. It should be mentioned that our framework together with Algorithm qPMS7 is currently deployed in our online tools at http://pms.engr.uconn.edu or at http://motifsearch.com. We will be very happy to receive any comments and feedback from users.
Author Contributions
Conceived and designed the experiments: HD SR JD. Performed the experiments: HD. Analyzed the data: HD SR. Contributed reagents/materials/analysis tools: HD SR JD. Wrote the paper: HD SR.
References
- 1. Laurent D, Philipp B (1997) Searching for regulatory elements in human noncoding sequences. Current Opinion in Structural Biology 7: 399–406.
- 2. Rajasekaran S (2009) Computational techniques for motif search. Frontiers in Bioscience 14: 5052–5065.
- 3. Bandyopadhyay S, Sahni S, Rajasekaran S (2012) Pms6: A faster algorithm for motif discovery. In: Proceedings of the second IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS 2012): 1–6.
- 4.
Dinh H, Rajasekaran S, Kundeti V (2011) Pms5: an efficient exact algorithm for the (l; d)-motiffinding problem. BMC Bioinformatics 12.
- 5.
Davila J, Balla S, Rajasekaran S (2007) Pampa: An improved branch and bound algorithm for planted (l, d) motif search. Technical report.
- 6.
Davila J, Balla S, Rajasekaran S (2007) Fast and practical algorithms for planted (l; d) motif search. In: IEEE/ACM Transactions on Computational Biology and Bioinformatics. pp. pp 544–552.
- 7. Rajasekaran S, Balla S, Huang CH (2005) Exact algorithms for planted motif challenge problems. Journal of Computational Biology 12: 1117–1128.
- 8.
Chin F, Leung H (2005) Algorithms for discovering long motifs. In: Proceedings of the Third Asia-Pacific Bioinformatics Conference (APBC2005), Singapore. pp. pp 261–271.
- 9.
Pisanti N, Carvalho A, Marsan L, Sagot MF (2006) Risotto: Fast extraction of motifs with mismatches. In: Proceedings of the 7th Latin American Theoretical Informatics Symposium. pp. pp 757–768.
- 10.
Blanchette M, Schwikowski B, Tompa M (2000) An exact algorithm to identify motifs in or-thologous sequences from multiple species. In: Proceedings of Eighth International Conference on Intelligent Systems for Molecular Biology. pp. pp 37–45.
- 11. Brazma A, Jonassen I, Vilo J, Ukkonen E (1998) Predicting gene regulatory elements in silico on a genomic scale. Genome Research 15: 1202–1215.
- 12. Eskin E, Pevzner P (2002) Finding composite regulatory patterns in dna sequences. Bioinformatics S1: 354–363.
- 13. Galas DJ, Eggert M, Waterman MS (1985) Rigorous pattern-recognition methods for dna sequences: Analysis of promoter sequences from escherichia coli. Journal of Molecular Biology 186: 117–128.
- 14.
Sinha S, Tompa M (2000) A statistical method for finding transcription factor binding sites. In: Proceedings of Eighth International Conference on Intelligent Systems for Molecular Biology. pp. pp 344–354.
- 15. Staden R (1989) Methods for discovering novel motifs in nucleic acid sequences. Computer Applications in the Biosciences 5: 293–298.
- 16.
Tompa M (1999) An exact method for finding short motifs in sequences, with application to the ribosome binding site problem. In: Proc. Seventh International Conference on Intelligent Systems for Molecular Biology. pp. pp 262–271.
- 17. Helden J, André B, Collado-Vides J (1998) Extracting regulatory sites from the upstream region of yeast genes by computational analysis of oligonucleotide frequencies. Journal of Molecular Biology 281: 827–842.
- 18.
Bailey T, Elkan C (1994) Fitting a mixture model by expectation maximization to discover motifs in biopolymers. In: Proceedings of Second International Conference on Intelligent Systems for Molecular Biology. pp. pp 28–36.
- 19.
Buhler J, Tompa M (2001) Finding motifs using random projections. In: Proceedings of Fifth Annual International Conference on Computational Molecular Biology (RECOMB). pp. pp 69–76.
- 20. Lawrence CE, Altschul SF, Boguski MS, Liu JS, Neuwald AF, et al. (1993) Detecting subtle sequence signals: a gibbs sampling strategy for multiple alignment. Science 262: 208–214.
- 21.
Pevzner P, Sze SH (2000) Combinatorial approaches to finding subtle signals in dna sequences. In: Proceedings of Eighth International Conference on Intelligent Systems for Molecular Biology. pp. pp 269–278.
- 22.
Rocke E, Tompa M (1998) An algorithm for finding novel gapped motifs in dna sequences. In: Proceedings of Second International Conference on Computational Molecular Biology (RECOMB). pp. pp 228–233.
- 23. Keich U, Pevzner P (2002) Finding motifs in the twilight zone. Bioinformatics 18: 1374–1381.
- 24. Price A, Ramabhadran S, Pevzner PA (2003) Finding subtle motifs by branching from sample strings. Bioinformatics 1: 1–7.
- 25. Hertz G, Stormo G (1999) Identifying dna and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics 15: 563–577.
- 26.
Kuksa P, Pavlovic V (2010) Efficient motif finding algorithms for large-alphabet inputs. BMC Bioinformatics 11.
- 27. Blanchette M (2001) Algorithms for phylogenetic footprinting. In: Proceedings of Fifth International Conference Computational Biology (RECOMB 2001): 49–58.
- 28. Tompa M, Li N, Bailey T, Church G, Moor BD, et al. (2005) Assessing computational tools for the discovery of transcription factor binding sites. Nature Biotechnology 23: 137–144.