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, an-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 n-1] from the alphabet set (A,C,G,T) and returns the (length of the) longest palindromic subsequence. Implement the algorithm in an appropriate language.
Can anyone help, what is dynamic programing ? searched my notes, didnt find anything...
u can use any, i used c++, anyway i have been able to do it, not difficult, but complicated at times
#include<iostream.h>
int pallin(char Z[], int x, int y, int k);
void main()
{
int i, z, e;
char A[14];
for (i=0;i<14;i++)
cin>>A[i];
for(e=0;e<14;e++)
{
z=pallin(A, e, 13, 0);
cout<<e<<"th count is : "<<z<<endl;
}
}
int pallin(char Z[], int x, int y, int k)
{int i, j;
int q;
q=x-y;
cout<<"q is : "<<q<<endl;
cout<<"x is : "<<x<<endl;
cout<<"y is : "<<y<<endl;
if(q >= 0)
{
k=k+1;
return k;
}
else
{
i=x;
j=y;
if(Z[i]==Z[j])
{
++x;
--j;
k=k+2;
cout<<"K is... "<<k<<endl;
pallin(Z, x, j, k);
}
else
{ --j;
cout<<"Count is... "<<k<<endl;
pallin(Z, x, j, k);
}
}
}