Missing components
In some applications a partial match of the structured motif might still be of interest. SMOTIF allows up to q simple motif components to be missing during the search. Let ℳ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBamrtHrhAL1wy0L2yHvtyaeHbnfgDOvwBHrxAJfwnaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaWaaeGaeaaakeaaimaacqWFZestaaa@3790@ be a structured motif with k components. SMOTIF first enumerates all possible sub-motifs having k' components, where k' ∈ [k - q, k]. Next, the gap ranges are adjusted in each sub-motif to account for skipping over the missing components. The new gap range, [li,j, ui,j], between components Mi and Mj (with 1 ≤ i <j ≤ k) in a sub-motif, is calculated as follows: li,j=∑n=1j−1ln MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGSbaBdaWgaaWcbaGaemyAaKMaeiilaWIaemOAaOgabeaakiabg2da9maaqadabaGaemiBaW2aaSbaaSqaaiabd6gaUbqabaaabaGaemOBa4Maeyypa0JaeGymaedabaGaemOAaOMaeyOeI0IaeGymaedaniabggHiLdaaaa@3E5F@, and ui,j=ui+∑n=i+1j−1(un+|Mn|) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWG1bqDdaWgaaWcbaGaemyAaKMaeiilaWIaemOAaOgabeaakiabg2da9iabdwha1naaBaaaleaacqWGPbqAaeqaaOGaey4kaSYaaabmaeaacqGGOaakcqWG1bqDdaWgaaWcbaGaemOBa4gabeaakiabgUcaRiabcYha8jabd2eannaaBaaaleaacqWGUbGBaeqaaOGaeiiFaWNaeiykaKcaleaacqWGUbGBcqGH9aqpcqWGPbqAcqGHRaWkcqaIXaqmaeaacqWGQbGAcqGHsislcqaIXaqma0GaeyyeIuoaaaa@4D0D@.
For example, if we allow one (q = 1) missing component for our structured motif in Table 4, the set of sub-motifs that need to be searched for are: GC[0,1]TTA[1,4]CAT, GC[1,8]CAT, GC[0,1]TTA and TTA[1,4]CAT. Note that it is straightforward to incorporate other approaches to compute new ranges into SMOTIF since it would only change the gap constraints. For example, li,j = minn ∈ [i,j-1] {ln} and ui,j = maxn ∈ [i,j-1] {un} is another possible way to compute the adjusted gap ranges.
Instead of searching each sub-motif separately, we do an optimized search. We reuse the partial pos-lists created when using a depth first search to enumerate and search the sub-motifs. The idea is to re-use the pos-lists created for common suffixes when enumerating their sub-motif extensions.