Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. Recently, the
longest arc-preserving common subsequence problem has been introduced in [[6],[7]] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences
with various arc structures and present some new algorithmic and complexity results on the longest arc-preserving common subsequence
problem. Some of our results answer an open question in [[6],[7]] and some others improve the hardness results in [[6],[7]].
Keywords Sequence annotation - longest common subsequence - approximation - algorithm - maximum independent set - MAX SNP-hard - dynamic programming
Supported in part by NSERC Research Grant OGP0046613, a CITO grant, and a UCR startup grant.
Supported in part by NSERC Research Grant OGP0046613 and a CITO grant.
Supported in part by NSERC Research Grant OGP0046506 and a CGAT grant.
Supported in part by NSERC Research Grant OGP0046373.