Library

DFA · Regular

Finding the EcoRI site GAATTC in DNA

The restriction enzyme EcoRI cuts DNA at GAATTC. A DFA finds it in one pass: each state is how much of the site has just been matched, and a mismatch falls back to the longest part that still fits — the Knuth–Morris–Pratt idea.

noneGGAGAAGAATGAATTfoundA, C, TGAC, TGAC, TGA, CGTA, CGTA, TCGA, C, G, T
The machine as drawn — 7 states, 28 transitions.

The author’s examples, run

GAATTC → acceptACGTGAATTCTA → acceptGAATTCTA → acceptACGTGAATTCTATA → acceptAAATTC → rejectACGTAAATTCTA → rejectAAATTCTA → rejectACGTAAATTCTATA → reject