×

zbMATH — the first resource for mathematics

Arc-preserving subsequences of arc-annotated sequences. (English) Zbl 1244.68037
Summary: 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-fragment LAPCS(crossing,chain) and the decision version of the 0-diagonal LAPCS(crossing,chain) are 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-fragment LAPCS(unlimited, plain) and the decision version of the 0-diagonal LAPCS(unlimited, plain) are NP-complete.
MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W32 Algorithms on strings
PDF BibTeX XML Cite