Efficient Chaining of Seeds in Ordered Trees

DOI10.1007/978-3-642-19222-7_27MaRDI QIDQ3000514zbMATH OpenOpenAlexFDO

Authors Julien Allali, Cedric Chauve, Pascal Ferraro, Anne-Laure Gaillard

Publication date 19 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We consider here 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 of m constant size seeds, we describe an algorithm with complexity O(m2 log(m)) in time and O(m2) in space.

Recommendations

• Efficient chaining of seeds in ordered trees
• Packing large trees of consecutive orders
• scientific article; zbMATH DE number 4156450
• Generating ordered trees
• Orderly Spanning Trees with Applications
• Efficient Generation of k-ary Trees in Natural Order
• Optimal chaining in expression trees
• scientific article; zbMATH DE number 7267318
• Efficient generation of binary trees from inorder-postorder sequences
• scientific article; zbMATH DE number 1456949

Cites work

• scientific article; zbMATH DE number 2241899 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• An optimal decomposition algorithm for tree edit distance
• Chaining algorithms for multiple genome comparison
• Efficient chaining of seeds in ordered trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(1)

• Efficient chaining of seeds in ordered trees

This page was built for publication: Efficient Chaining of Seeds in Ordered Trees

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