Fast arc-annotated subsequence matching in linear space

DOI10.1007/S00453-010-9451-8MaRDI QIDQ2428660zbMATH OpenOpenAlexWikidataFDO

Authors Philip Bille, Inge Li Gørtz

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.0577

zbMATH Keywords

algorithmssubsequence matchingarc-annotated strings

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

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

Recommendations

• Fast arc-annotated subsequence matching in linear space
• scientific article; zbMATH DE number 1954383
• scientific article; zbMATH DE number 2087047
• Pattern matching for arc-annotated sequences
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

Cites work

• scientific article; zbMATH DE number 1954383 (Why is no real title available?)
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Algorithmic aspects of bioinformatics. Translated from the German original
• Automata, Languages and Programming
• Computing the similarity of two sequences with nested arc annotations
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast RNA Structure Alignment for Crossing Input Structures
• How to Compare Arc-Annotated Sequences: The Alignment Hierarchy
• More Efficient Algorithm for Ordered Tree Inclusion
• On the computational complexity of 2-interval pattern matching problems
• Ordered and Unordered Tree Inclusion
• The longest common subsequence problem for sequences with nested arc annotations.
• What Makes the Arc-Preserving Subsequence Problem Hard?

Cited in

(3)

• A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment
• Fast arc-annotated subsequence matching in linear space
• scientific article; zbMATH DE number 1954383 (Why is no real title available?)

This page was built for publication: Fast arc-annotated subsequence matching in linear space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428660)