3.8 Exercises 1. Given three DNA sequences S1, S2, and S3 of total length n. aagatgt. What is the (b) Describe an efficient algorithm that computes the length of the longest common substring. What is the time complexity? (a) Suppose Si acgatca, S2 = gattact, S3 longest common substring of S1, S2, and S3? PRO (c) It is possible that the longest common substring for S, S2, and S3 is not unique. Can you describe an efficient algorithm to report the number of possible longest common substrings of S, S2, and S3? What is the time complexity? 2. Please give the generalized suffix tree for S = ACGTS and S TGCA#. 3. Given a DNA sequence S and a pattern P, can you describe an O(|P| + |S) time algorithm to find all occurrences of P in S with hamming distance seql ACTGGGAAATCGAAGACCCGG Remember to add a $' to the end of the string. The output should just be the suffix array table, e.g. SA [1] = x SA [2] = y etc. Bonus question (1 pt): Implement a binary search based pattern matching algorithm in the above program that searches the suffix array for a given pattern.