Exact matching
In the first experiment, shown in Figure 7(a), we randomly generated 100 structured motif templates, with k ∈ [2,4] simple motifs of length l ∈ [4,7] (k and l are selected uniformly at random within the given ranges). The gap range between each pair of simple motifs is a random sub-interval of [0, 200]. The x-axis is sorted on the number of motifs extracted. For clarity we plot average times for the methods when the number of motifs extracted fall into the given range on the x-axis. For example, the time plotted for the range [102, 103) is the average time for all the random templates that produce between 100 and 1000 motifs. We find that the average running time for RISO across all extracted motifs is 120.7s, whereas for EXMOTIF it takes 88.4s for reporting only the supports, and 91.3s for also reporting all the occurrences. The median times were 26.3s, 8.5s, and 9.2s, respectively, indicating a 3 times speed-up of EXMOTIF over RISO.
In the next set of experiments we varied one parameter while keeping the others fixed. We set the default quorum to 12% (q = 127), the default gap ranges to [0,100], the default simple motif length to l = 4 (NNNN), and the default number of components k = 3 (e.g., NNNN[0,100]NNNN[0,100]NNNN). In Figure 7(b), we plot the time as a function of the number of simple motifs k in the template. We find that as the number of components increases the time gap between EXMOTIF and RISO increases; for k = 4 simple motifs, EXMOTIF is around 5 times faster than RISO. Figure 7(c) shows the effect of increasing gap ranges, from [0,0] to [0,200]. We find that as the gap range increases the time for EXMOTIF increases at a slower rate compared to RISO. For [0,200], EXMOTIF is 3–4 times faster than RISO depending whether only frequency or full occurrences are reported. In Figure 7(d), as the quorum threshold increases, the running time goes down for both methods. For quorum 24%, EXMOTIF is 4–5 times faster than RISO. As support decreases, the gap narrows somewhat, but EXMOTIF remains 2–3 times faster. Finally, Figure 7(e) plots the effect of increasing simple motif lengths l ∈ [2,6]. We find that the time first increases and then decreases. This is because there are a large number of motif occurrences for length 3 and length 4, but relatively few occurrences for length 5 and length 6. Depending on the motif lengths, EXMOTIF can be 3–40 times faster than RISO for comparable output, i.e., reporting only the support. EXMOTIF remains up to 5 times faster when also reporting the actual occurrences.
To compare the performance for extracting structured motifs with length ranges, we used the template T MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFtepvaaa@3847@ = M1[50, 100] M2[1,50]M3[20, 100]M4 with q = 12%, where |M1| ∈ [2,4], |M2| ∈ [3,4], |M3| ∈ [5,6], |M4| ∈ [4,5]. EXMOTIF took 78.4s, whereas RISO took 1640.9s to extract 14,174 motifs.