Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.jda.2011.12.013 | Journal of Discrete Algorithms |
Keywords | Field | DocType |
m2 log,trees q,chaining problem,rna secondary structure,chaining seed,efficient chaining,complexity o,m constant size seed,computational biology,natural extension,similar problem,chaining,algorithm | Discrete mathematics,Combinatorics,Chaining,Time complexity,Mathematics | Conference |
Volume | ISSN | Citations |
14 | 21st International Workshop on Combinatorial Algorithms, London :
United Kingdom (2010) | 2 |
PageRank | References | Authors |
0.40 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Allali | 1 | 64 | 8.16 |
| cedric chauve | 2 | 429 | 41.81 |
| Pascal Ferraro | 3 | 77 | 11.54 |
| Anne-Laure Gaillard | 4 | 2 | 0.40 |