Searching Similar Protein under Complementary and No Stop Codon Constraints

The applications in the area of protein engineering motivate a problem, that is to compute an mRNA sequence of maximal similarity to a given mRNA and a given protein, the output mRNA sequence should have the same secondary structure as the given mRNA sequence and should not contain any stop codon. We call this problem as MRSO-SC (MRna structure optimization under no stop codon constraint). Besides, for one nucleotide at most binds with one other nucleotide in the secondary structure of an mRNA sequence, we call the restricted version of MRSO-SC problem as MRSO-SC-d1 problem. In this paper, we first prove that the decision version of MRSO-SC problem and MRSO-SC-d1 problem are both NP-complete. Then, based on some structural feature of stop codon, we propose four kinds of invalid frame, which may lead to stop codon. Whatpsilas more, we attack the MRSO-SC-d1problem by proposing a new approximation algorithm, in the process of this algorithm, any invalid frame could be avoided in finding feasible solution.