Article ID Journal Published Year Pages File Type
431646 Journal of Discrete Algorithms 2012 12 Pages PDF
Abstract

We consider the problem of chaining seeds in ordered trees. Seeds are mappings between two trees Q and T and a chain is a subset of non-overlapping seeds that is consistent with respect to postfix order and ancestrality. This problem is a natural extension of a similar problem for sequences, and has applications in computational biology, such as mining a database of RNA secondary structures. For the chaining problem with a set S of m   seeds of cumulated size ‖S‖‖S‖, we describe an algorithm with complexity O(‖S‖log(‖S‖)+m‖S‖log(m))O(‖S‖log(‖S‖)+m‖S‖log(m)) in time and O(m‖S‖)O(m‖S‖) in space.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,