2009/11/03 by Philip Bille, Bille, Philip, Inge Li Goertz +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #RNA and protein synthesis mechanisms #RNA modifications and cancer #cs.DS
paper · pdf · doi:10.48550/arxiv.0911.0577
To appear in Algoritmica
openalex publication_date 2009/11/03 · arxiv created 2010/09/08 · arxiv updated 2010/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.