Skip to Main content Skip to Navigation
Journal articles

A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes

Abstract : In this paper, we propose a new algorithm for the alignment of nested arc-annotated sequences, having applications in the comparison of RNA secondary structures without pseudo-knots. We use a general edit distance model between arc-annotated sequences, that considers classical sequences of edit operations and structural edit operations on arcs. In this model, the general edit distance problem under a non-constrained weight scheme, is NP-hard. Recently, a hierarchy of arc-annotated sequence alignment problems that highlights less general, but tractable, problems was introduced. We refine this hierarchy of alignment problems and extend the class of tractable alignment problems. Up to date, the alignment problem we solve is the most general one that is known to be tractable in the considered edit distance model and under arbitrary weight schemes. This algorithm is efficient, as its asymptotic time and space complexities are the same as the complexities of the best previously published algorithm.
Document type :
Journal articles
Complete list of metadata
Contributor : Aïda Ouangraoua Connect in order to contact the contributor
Submitted on : Monday, October 24, 2011 - 3:28:35 PM
Last modification on : Thursday, January 20, 2022 - 5:30:35 PM

Links full text




Aïda Ouangraoua, Valentin Guignon, Hamel Sylvie, Cedric Chauve. A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes. Theoretical Computer Science, Elsevier, 2011, 412 (8-10), pp.753-764. ⟨10.1016/j.tcs.2010.11.020⟩. ⟨inria-00635043⟩



Record views