Question

Given DNA can be represented with an alphabet consisting of characters A,C,G, and T develop the shift table for the following ( TCCTATTCTT) and then explain how this table could be applied to sequences of DNA.

Answer 1

Shift table stores the actual value of last occurrence of a character in pattern.

Given Pattern : T C C T A T T C T T
index   : 0 1 2 3 4 5 6 7 8 9
last occurrence of(A) = 4
last occurrence of(C) = 7
last occurrence of(G) = -1
last occurrence of(T) = 9

Upon mismatch, we shift the pattern until
1) The mismatch becomes a match(using shift table)
2) Pattern P move past the mismatched character(using shift table).
Shift the pattern so that the bad character in text aligns with the last occurrence of it in pattern.