A palindrome is a string that reads the same backwards and forwards. A complemen

Question

A palindrome is a string that reads the same backwards and forwards. A complemented palindrome is one that when read backwards is the complement of the string reading forwards (the pairs A-T and G-C are considered complements). A maximal palindrome is one that is not contained in any other. For example, in the string "ATATGAGGAGGCCT" the substrings “AGGCCT” are maximal complemented palindromes.

(a) Write algorithms that determine all maximal palindromes and complemented palindromes for a given input string.

(b) What are the running times of your algorithms?

(c) Implement and test your algorithm on a DNA sequence.

Explanation / Answer

a) MAXIMAL PALINDROME:

dp(i,j) = (dp(i+1, j-1) ? (S(i) == S(j) ? 1 : 0 ): 0)

res = (dp(i,j) ? max(res, j-i+1) : res)

MAXIMAL COMPLEMENTED PLAINDROME:

  dp(i,j) = (dp(i+1, j-1) ? (complement[S(i)] == S(j) ? 1 : 0 ): 0)

res = (dp(i,j) ? max(res, j-i+1) : res)

b) O(n2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.