Motifs

SUBS — Finding a Motif in DNA

solved Problem statement

Finding every occurrence, overlaps included, because real motifs do overlap. The motifs worth finding are restriction sites (REVP) and binding sites — though a real binding site is a tendency rather than a fixed string, which KSIM and MPRT address.

LCSM — Finding a Shared Motif

solved Problem statement

Any longest common substring is a valid answer, so the assertion checks the length and that the motif really is shared, not one particular string.

SSEQ — Finding a Spliced Motif

solved Problem statement

A subsequence rather than a substring — the characters need not be contiguous. That is the right model for a motif split across exons, since the intervening introns are spliced out before the protein is made.

MPRT — Finding a Protein Motif

solved Problem statement

Calls NCBI, so it needs a network connection and its answer can change over time.

Fetches from UniProt, so it runs in the advisory job rather than the hermetic gate. The motif matcher itself is asserted offline — N{P}[ST]{P} has alternatives and exclusions, so it is a pattern rather than a substring search.

ITWV — Finding Disjoint Motifs in a Gene

solved Problem statement

Two motifs competing for the same characters, which is what makes this different from finding each separately. Every reachable state must consume the current character or the window ends — carrying one forward unconsumed would let the motifs match unrelated parts of the sequence.

KSIM — Finding All Similar Motifs

solved Problem statement

A binding site is a tendency rather than a fixed string, so exact search finds a fraction of real sites — the motif here does not occur exactly at all. Checks every (start, length) pair directly, which is O(n^2) and stated as such: a 50 kbp genome would need the fitting-alignment form instead.