|In Bioinformatics, a DNA sequence is made up of a
combination of 4 characters, namely A,C,G,T. A
subsequence of a given sequence of characters a0, a1,
1, is any subset of the characters taken in order, of the
form ai0 , ai1 ,
..aik-1 where 0 ≤ i0 <i1
.< ik-1 ≤ n-1.
For example in the sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G,
we can have subsequences A,G,T, A,C,A,A and many more.
A subsequence is palindromic if it is the same whether read
left to right or right to left. For instance, the
sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G, has many
palindromic subsequences, including A,C,G,C,A
and A,A,A,A (on the other hand, the subsequence A,C,T
is not palindromic). Devise an algorithm (using dynamic
programming) that takes a sequence of characters X[0
from the alphabet set (A,C,G,T) and returns the (length of
the) longest palindromic subsequence. Implement the
algorithm in an appropriate language.