Computer Science – Computational Complexity
Scientific paper
2011-04-22
Acta Univ. Sapientiae, Informatica 3, 1 (2011) 35--47
Computer Science
Computational Complexity
Scientific paper
Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The longest arc-preserving common subsequence problem has been introduced as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures. We consider the longest arc preserving common subsequence problem. In particular, we show that the decision version of the 1-{\sc fragment LAPCS(crossing,chain)} and the decision version of the 0-{\sc diagonal LAPCS(crossing,chain)} are {\bf NP}-complete for some fixed alphabet $\Sigma$ such that $|\Sigma| = 2$. Also we show that if $|\Sigma| = 1$, then the decision version of the 1-{\sc fragment LAPCS(unlimited, plain)} and the decision version of the 0-{\sc diagonal LAPCS(unlimited, plain)} are {\bf NP}-complete.
No associations
LandOfFree
Arc-preserving subsequences of arc-annotated sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Arc-preserving subsequences of arc-annotated sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arc-preserving subsequences of arc-annotated sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-330746