3.8 Exercises 1. Given three DNA sequences S1, S2, and S3 of total length n. aagatgt....

Transcribed Image Text:

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 <1? 4. Consider the string S = ACGT ACGTS. (a) What is the suffix array for S? (b) Report the values of (1) LCP(k, k + 1) for k= 1, 2, ...,8 and (2) LCP (k, k+4) for k = 1, 2, 3, 4. (For 3., Hamming distance of <= 1 means that we should look for a substring M in S such that IM| = |P| and there is at most one mismatch between M and P.) Problem 5 (10 pts) Programming project: Write a program to compute the suffix array for a given input string (you may use any programming language). Your program should read in a FASTA file (like HW2). You can assume that the file just contains a single DNA sequence, e.g. > 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. 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 <1? 4. Consider the string S = ACGT ACGTS. (a) What is the suffix array for S? (b) Report the values of (1) LCP(k, k + 1) for k= 1, 2, ...,8 and (2) LCP (k, k+4) for k = 1, 2, 3, 4. (For 3., Hamming distance of <= 1 means that we should look for a substring M in S such that IM| = |P| and there is at most one mismatch between M and P.) Problem 5 (10 pts) Programming project: Write a program to compute the suffix array for a given input string (you may use any programming language). Your program should read in a FASTA file (like HW2). You can assume that the file just contains a single DNA sequence, e.g. > 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.

Answer rating: 100% (QA)

Lets address each of the exercises a Given S1 acgatca S2 gattact and S3 aagatgt we need to find the longest common substring among them In this case t... View the full answer