Write a python script that prompts for a DNA sequence (assume all caps, no space

Question

Write a python script that prompts for a DNA sequence (assume all caps, no spaces, and only 'A, 'T, 'C, 'G'). Your script should find all palindromic sequences within the DNA sequence. For each palindromic sequence found, print the start index, end index, and sequence on one line. Only report palindromic sequences that are 4 nucleotides or longer. Example. For input DNA TGGAATTCGTGAGCGGATAAGCTTAC, the output should be (vertical order of lines is not important for grading, vertical order may be a hint for next stage though...) 2 7 GAATTC 3 6 AATT 17 24 TAAGCTTA 18 23 AAGCTT 19 22 AGCT

Explanation / Answer

#python 3.5.2
def palindromeSubStrs(s):
    m = dict()
    n = len(s)

    # table for storing results (2 rows for odd-
    # and even-length palindromes
    R = [[0 for x in range(n+1)] for x in range(2)]

    # Find all sub-string palindromes from the given input
    # string insert 'guards' to iterate easily over s
    s = "@" + s + "#"

    for j in range(2):
        rp = 0    # length of 'palindrome radius'
        R[j][0] = 0

        i = 1
        while i <= n:

            # Attempt to expand palindrome centered at i
            while s[i - rp - 1] == s[i + j + rp]:
                rp += 1 # Incrementing the length of palindromic
                        # radius as and when we find valid palindrome

            # Assigning the found palindromic length to odd/even
            # length array
            R[j][i] = rp
            k = 1
            while (R[j][i - k] != rp - k) and (k < rp):
                R[j][i+k] = min(R[j][i-k], rp - k)
                k += 1
            rp = max(rp - k, 0)
            i += k

    # remove guards
    s = s[1:len(s)-1]

    # Put all obtained palindromes in a hash map to
    # find only distinct palindrome
    m[s[0]] = 1
    for i in range(1,n):
        for j in range(2):
            for rp in range(R[j][i],0,-1):
                m[s[i - rp - 1 : i - rp - 1 + 2 * rp + j]] = 1
        m[s[i]] = 1

    # printing all distinct palindromes from hash map
    print ("Below are " + str(len(m)) + " pali sub-strings")
    for i in m:
      if(len(i)>4):
        print(string.index(i),string.index(i)+len(i)-1,i)

# Driver program
string= input("Enter string:")
palindromeSubStrs(string)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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