A subsequence of a DNA string is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

ACGTGTCAAAATCG

has many palindromic subsequences, including ACGCA and AAAA. On the other hand, the subsequence ACT is not palindromic.

Assignment

Write a function palindromeLength that takes a DNA string. The function must return the length of the longest palindromic subsequence of the given DNA string.

Example

In the following interactive session, we assume the FASTA file data.fna¹ to be located in the current directory.

        >>> palindromeLength('ACGTGTCAAAATCG')
8

>>> from Bio import SeqIO
>>> palindromeLength(*SeqIO.parse('data.fna', 'fasta'))
11