Computer Science – Data Structures and Algorithms
Scientific paper
2009-11-03
Computer Science
Data Structures and Algorithms
To appear in Algoritmica
Scientific paper
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.
Bille Philip
Goertz Inge Li
No associations
LandOfFree
Fast Arc-Annotated Subsequence Matching in Linear Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Arc-Annotated Subsequence Matching in Linear Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Arc-Annotated Subsequence Matching in Linear Space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-256617