Abstract
Selenocysteine is the 21th amino acid, which occurs in all kingdoms of life. Selenocysteine is en-coded by the STOP-codon UGA. For its insertion, it requires a specific mRNA sequence downstream the UGA-codon that forms a hairpin like structure (called Sec insertion sequence (SECIS). We consider the computational problem of generating new amino acid sequences containing selenocysteine. This requires to find an mRNA se-quence that is similar to the SECIS-consensus, is able to form the secondary structure required for selenocysteine insertion, and whose translation is maximally similar to the original amino acid sequence. We show that the problem can be solved in linear time when considering the hairpin-like SECIS-structure (and, more generally, when consider-ing a structure that does not contain pseudoknots).