CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Information Processing Letters (0020-0190). Vol. 100 (2006), 2, p. 64-68.
[Artikel, refereegranskad vetenskaplig]

The Arc-Preserving Subsequence (APS) problem appears in the comparison of RNA structures in computational biology. Given two arc-annotated sequences of length n and m, APS asks if the shorter sequence (length m) can be obtained from the longer one by deleting certain elements along with their incident arcs. It is known that APS with pairwise nested arcs can be solved in O(mn) time. We give an algorithm running in O(m*m+n) time in the worst case, actually it is even faster in particular if the shorter sequence has many arcs. The result may serve as a buidling block for improved APS algorithms in the general case.

Nyckelord: RNA structure, pattern matching, dynamic programming

Denna post skapades 2006-09-05. Senast ändrad 2015-02-11.
CPL Pubid: 22440