Efficient Chaining of Seeds in Ordered Trees
From MaRDI portal
Publication:3000514
DOI10.1007/978-3-642-19222-7_27zbMATH Open1326.05031arXiv1007.0942OpenAlexW2038351187MaRDI QIDQ3000514FDOQ3000514
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)
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.
Full work available at URL: https://arxiv.org/abs/1007.0942
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
- Algorithms on Strings, Trees and Sequences
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- Chaining algorithms for multiple genome comparison
- An optimal decomposition algorithm for tree edit distance
- Efficient chaining of seeds in ordered trees
- Title not available (Why is that?)
Cited In (1)
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)
