Fast Arc-Annotated Subsequence Matching in Linear Space

Abstract

An arc-annotated string is a string of characters, called bases, augmented with a set of pairs, called arcs, each connecting two bases. Given arc-annotated strings $P$ and $Q$ the arc-preserving subsequence problem is to determine if $P$ can be obtained from $Q$ by deleting bases from $Q$. Whenever a base is deleted any arc with an endpoint in that base is also deleted. Arc-annotated strings where the arcs are ``nested'' are a natural model of RNA molecules that captures both the primary and secondary structure of these. The arc-preserving subsequence problem for nested arc-annotated strings is basic primitive for investigating the function of RNA molecules. Gramm et al. [ACM Trans. Algorithms 2006] gave an algorithm for this problem using $O(nm)$ time and space, where $m$ and $n$ are the lengths of $P$ and $Q$, respectively. In this paper we present a new algorithm using $O(nm)$ time and $O(n+m)$ space, thereby matching the previous time bound while significantly reducing the space from a quadratic term to linear. This is essential to process large RNA molecules where the space is likely to be a bottleneck. To obtain our result we introduce several novel ideas which may be of independent interest for related problems on arc-annotated strings.

To appear in Algoritmica