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, our algorithm determines (if existent) in time $ O(3.31^{k_1 + k_2 } \cdot n) $ O(3.31^{k_1 + k_2 } \cdot n) an arc-preserving subsequence of both sequences, which can be obtained by deleting (together with corresponding arcs) k ₁ letters from the first and k ₂ letters from the second sequence. Thus, the problem is fixed-parameter tractable when parameterized by the number of deletions. This complements 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.