|  |
| Title:
|
Fast Arc-Annotated Subsequence Matching in Linear Space |
| Type:
|
Journal articleJournal article |
| Participant(s):
|
Technical University of Denmark
Email:
Technical University of Denmark
Email:
|
| 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 2(1): 44-65, 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. © 2010 Springer Science+Business Media, LLC. |
| Published:
|
in journal: Algorithmica (ISSN: 0178-4617) (DOI: http://dx.doi.org/10.1007/s00453-010-9451-8), vol: 62, issue: 1-2, pages: 209-223, 2012 |
| DOI:
|
|
|
|