Efficient chaining of seeds in ordered trees

Conference object, Article, Preprint English OPEN
Allali, Julien ; Chauve, Cedric ; Ferraro, Pascal ; Gaillard, Anne-Laure (2012)
  • Publisher: Elsevier BV
  • Journal: Journal of Discrete Algorithms, volume 14, pages 107-118 (issn: 1570-8667)
  • Related identifiers: doi: 10.1016/j.jda.2011.12.013, doi: 10.1007/978-3-642-19222-7_27
  • Subject: Theoretical Computer Science | [ SDV.BIBS ] Life Sciences [q-bio]/Quantitative Methods [q-bio.QM] | Computational Theory and Mathematics | Quantitative Biology - Quantitative Methods | Discrete Mathematics and Combinatorics | [ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM]

International audience; 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.
  • References (15)
    15 references, page 1 of 2

    1. S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. Basic local alignment search tool. J. Mol. Biol., 215(3):403-410, 1990.

    2. S. Aluru, editor. Handbook of Computational Molecular Biology. CRC Press, 2005.

    3. R. Backofen and S. Will. Local sequence-structure motifs in RNA. J. Bioinform. Comput. Biol., 2(4):681-698, 2004.

    4. E.D. Demaine, S. Mozes, B. Rossman, and O. Weimann. An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms, 6(1):Article 2, 2009.

    5. P.P. Gardner, J. Daub, J.G. Tate, et al. Rfam: updates to the RNA families database. Nucleic Acids Res., 37(Database issue):D136-D140, 2009.

    6. D. Gusfield. Algorithms on Strings, Trees and Sequences. Cambridge University Press, 1997.

    7. S. Heyne, S. Will, M. Beckstette, and R. Backofen. Lightweight comparison of RNAs based on exact sequence-structure matches. Bioinformatics, 25(16):2095- 2102, 2009.

    8. T. Jiang, G. Lin, B. Ma, and K. Zhang. A general edit distance between RNA structures. J. Comput. Biol., 9(2):371-388, 2002.

    9. D. Joseph, J. Meidanis, and P. Tiwari. Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In SWAT 1992, volume 621 of LNCS, pp 326-337. 1992.

    10. D.J. Lipman and W.R. Pearson. Rapid and sensitive protein similarity searches. Science, 227(4693):1435-1441, 1985.

  • Metrics
    No metrics available
Share - Bookmark