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.
翻译:种子是两棵树Q和T之间的测绘图,一个链子是非重叠种子的子集,符合后缀顺序和祖传性。这是一个类似序列问题的自然延伸问题,在计算生物学中也有应用,如开采RNA二级结构数据库。对于一组恒定大小种子的链条问题,我们描述了一个在时间上复杂的O(m2log(m))和在空间上复杂的O(m2log(m))的算法。