A DNA sequence can be represented by a string consisting only of the letters A, C, G and T. The inverse complement of a DNA sequence is obtained by reversing the order of the letters in the string, and switching each A to a T (and vice versa), and each G to a C (and vice versa). For example, the inverse complement of the DNA sequence AGCTGCT is AGCAGCT. A palindromic sequence is a DNA sequence of which the inverse complement reads exactly the same. For example, the inverse complement of the DNA sequence AATGCATT equals the original DNA sequence, and such a DNA sequence is thus an example of a palindromic sequence.

Assignment

1. Write a function DNAPalindrome to which a DNA sequence must be passed as argument. This function must return the value True if the given DNA sequence is a palindromic sequence. Otherwise, the value False must be returned.

2. Use the DNAPalindrome function for writing a longestPalindrome function. This function must be passed a DNA sequence as argument. The function must return the longest palindromic subsequence of the given sequence as a result. In order to find the longest palindromic subsequence you can go through all possible subsequences of the given DNA sequence, test whether it is a palindromic sequence, and eventually retain the longest palindrome. To go through all possible subsequences of a given DNA sequence, you can go through all the possible starting positions and through all possible stop positions for each possible starting position. That way you can find any subsequence as the sequence between any combination of possible start and stop positions.
   

Example

>>> DNAPalindrome('GAATTC')
True
>>> DNAPalindrome('GAAATTC')
False
>>> DNAPalindrome('ACCGGT')
True
>>> longestPalindrome('GGGCCTATTGACTTCTTATCGTAGCCGGCCTTGTTAGTAGATGAGAATCA')
'GCCGGC'
>>> longestPalindrome('AGCGCCTTGCAGCCGGGGACGGTGAGTTGGTAGCGCCCCTCAGGTCACTG')
'GCGC'