Problem 4. (25 points) Consider the problem of searching for genes in DNA sequences using Horspool's algorithm. A DNA sequence consists of a text on the alphabet {A, C, G, T}

and the gene or gene segment is the pattern. a. Construct the shift table for the following gene segment of your chromosome 10: ТССТАТТСТТ b. Apply Horspool's algorithm to locate the above pattern in the following DNA sequence: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT