Dansk DTU.dk Index Contact Phone book Internal Pages DTU Alumni
 Søgeord
 Research areas Algorithms and Logic Courses People Publications Cognitive Systems Data Analysis Dynamical Systems Embedded Systems Engineering Image Analysis & Computer Graphics Language-Based Technology Mathematical Statistics Scientific Computing Software Engineering Research centers Publications
 Title: Fast Arc-Annotated Subsequence Matching in Linear Space Type: Journal articleJournal article Participant(s): Author:  Bille, Philip (Cwisno: 53341) Technical University of Denmark Email: --- Author:  Gørtz, Inge Li (Cwisno: 33225) 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:
 Top
 Matematiktorvet DTU - Building 303B DK-2800 Kgs. Lyngby --- Tel +45 4525 3031 EAN 5798000428515