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. (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.
