Direct vs 2-stage approaches to structured motif finding

Abstract

Background: The notion of DNA motif is a mathematical abstraction used to model regions of the DNA (known as Transcription Factor Binding Sites, or TFBSs) that are bound by a given Transcription Factor to regulate gene expression or repression. In turn, DNA structured motifs are a mathematical counterpart that models sets of TFBSs that work in concert in the gene regulations processes of higher eukaryotic organisms. Typically, a structured motif is composed of an ordered set of isolated (or simple) motifs, separated by a variable, but somewhat constrained number of "irrelevant" base-pairs. Discovering structured motifs in a set of DNA sequences is a computationally hard problem that has been addressed by a number of authors using either a direct approach, or via the preliminary identification and successive combination of simple motifs.

Results: We describe a computational tool, named SISMA, for the de-novo discovery of structured motifs in a set of DNA sequences. SISMA is an exact, enumerative algorithm, meaning that it finds all the motifs conforming to the specifications. It does so in two stages: first it discovers all the possible component simple motifs, then combines them in a way that respects the given constraints. We developed SISMA mainly with the aim of understanding the potential benefits of such a 2-stage approach w.r.t. direct methods. In fact, no 2-stage software was available for the general problem of structured motif discovery, but only a few tools that solved restricted versions of the problem. We evaluated SISMA against other published tools on a comprehensive benchmark made of both synthetic and real biological datasets. In a significant number of cases, SISMA outperformed the competitors, exhibiting a good performance also in most of the cases in which it was inferior.

Conclusions: A reflection on the results obtained lead us to conclude that a 2-stage approach can be implemented with many advantages over direct approaches. Some of these have to do with greater modularity, ease of parallelization, and the possibility to perform adaptive searches of structured motifs. As another consideration, we noted that most hard instances for SISMA were easy to detect in advance. In these cases one may initially opt for a direct method; or, as a viable alternative in most laboratories, one could run both direct and 2-stage tools in parallel, halting the computations when the first halts.

Figure 1

Simple and structured motifs. Part (a): some DNA sequences with instances of the two simple motifs GATAAG (one base substitution tolerated) and TATAAAA (up two base substitutions tolerated), highlighted in blue and red, respectively. Part (b): three instances of a structured motif (6,1)-[2,4]-(6,1)-[3,5] -(7,2).

Figure 2

Risotto vs SISMA_Smile on synthetic datasets (a) Number of iterations in which SISMA_Smile outperforms Risotto or vice versa, and (b) number of tools failures. Notice that when one tool fails, the other might end computation, hence, failures might not sum up to the total number of runs.

Figure 3

Risotto’s and SISMA_Smile’s running times on synthetic datasets. Worst and average run times and standard deviations (in seconds) for SISMA_Smile and Risotto. Average runtime and standard deviations have been computed omitting best and worst runs. (a) (b) (c) Running times of all runs are considered. (a’) (b’) (c’) Only running times of runs in which both tools end computation are considered. Notice that the scale on Y-axes is not the same for all charts.

Figure 4

Examples: SISMA_Smile vs Risotto. Running times of Risotto, SISMA_Smile’s stages 1 and 2, and of all SISMA_Smile’s list intersection step (during stage 2). A 0s time for list intersection means that the corresponding step took time smaller than timer resolution. The box index selection order during stage 2 is shown. In example (a) SISMA_Smile outperforms Risotto. Observe that SMILE is called once on the (10,2) pair, so that the time reported for the 6^th box is 0. In this example Risotto is 473 times slower than SISMA. In example (b) Risotto outperforms SISMA_Smile because the stage 1 performed by SMILE is slow due to the presence of a box for which a large number of simple motifs is found. In this case SISMA_Smile is 28 times slower than Risotto. In particular, the most time consuming task is the extraction of the (15,4) box (about 91.7%of total execution time), for which 21631 simple motifs are found.

Figure 5

Running times on biological datasets. Running times (in seconds) of (a) SISMA_Smile and Risotto (b) SISMA_Speller and ExMotif on biological datasets, when using an uniprocessor machine with 1GB of RAM.