Skip to Main content Skip to Navigation
Conference papers

Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions

Abstract : Arc-annotated sequences are useful for representing struc- tural information of RNAs and have been extensively used for compar- ing RNA structures in both terms of sequence and structural similari- ties. Among the many paradigms referring to arc-annotated sequences and RNA structures comparison (see [2] for more details), the most im- portant one is the general edit distance. The problem of computing an edit distance between two non-crossing arc-annotated sequences was in- troduced in [5]. The introduced model uses edit operations that involve either single letters or pairs of letters (never considered separately) and is solvable in polynomial-time [12]. To account for other possible RNA structural evolutionary events, new edit operations, allowing to consider either silmutaneously or separately letters of a pair were introduced in [9]; unfortunately at the cost of com- putational tractability. It has been proved that comparing two RNA sec- ondary structures using a full set of biologically relevant edit operations is NP-complete. Nevertheless, in [8], the authors have used a strong com- binatorial restriction in order to compare two RNA stem-loops with a full set of biologically relevant edit operations; which have allowed them to design a polynomial-time and space algorithm for comparing general secondary RNA structures. In this paper we will prove theoretically that comparing two RNA struc- tures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620327
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:30:07 PM
Last modification on : Monday, July 20, 2020 - 12:34:51 PM
Long-term archiving on: : Tuesday, November 13, 2012 - 2:52:20 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620327, version 1

Citation

Guillaume Blin, Sylvie Hamel, Stéphane Vialette. Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions. 4th Workshop on Algorithms and Computation (WALCOM'10), Feb 2010, Dhaka, Bangladesh, Bangladesh. pp.149-160. ⟨hal-00620327⟩

Share

Metrics

Record views

419

Files downloads

293