Computing the similarity of two sequences with nested arc annotations

摘要

We present exact algorithms for the NP-complete LONGEST COMMON SUBSEQUENCE problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences of length at most n and nested arc structure, one of our algorithms determines (if existent) in O(3.31{sup}(k{sub}1+k{sub}2)·n) time an arc-preserving subsequence of both sequences, which can be obtained by deleting (together with corresponding arcs) k{sub}1 letters from the first and k{sub}2 letters from the second sequence. A second algorithm shows that (in case of a four letter alphabet) we can find a length l arc-annotated subsequence in O(12{sup}l·l·n) time. This means that the problem is fixed-parameter tractable when parameterized by the number of deletions as well as when parameterized by the subsequence length. Our findings complement known approximation results, which give a quadratic time factor-2-approximation for the general and polynomial time approximation schemes for restricted versions of the problem. In addition, we obtain further fixed-parameter tractability results for these restricted versions.