English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Arc-annotated sequences are useful for representing structural information ofRNAs and have been extensively used for comparing RNA structures in both termsof sequence and structural similarities. Among the many paradigms referring toarc-annotated sequences and RNA structures comparison (see\cite{IGMA_BliDenDul08} for more details), the most important one is thegeneral edit distance. The problem of computing an edit distance between twonon-crossing arc-annotated sequences was introduced in \cite{Evans99}. Theintroduced model uses edit operations that involve either single letters orpairs of letters (never considered separately) and is solvable inpolynomial-time \cite{ZhangShasha:1989}. To account for other possible RNAstructural evolutionary events, new edit operations, allowing to considereither silmutaneously or separately letters of a pair were introduced in\cite{jiangli}; unfortunately at the cost of computational tractability. It hasbeen proved that comparing two RNA secondary structures using a full set ofbiologically relevant edit operations is {\sf\bf NP}-complete. Nevertheless, in\cite{DBLP:conf/spire/GuignonCH05}, the authors have used a strongcombinatorial restriction in order to compare two RNA stem-loops with a fullset of biologically relevant edit operations; which have allowed them to designa polynomial-time and space algorithm for comparing general secondary RNAstructures. In this paper we will prove theoretically that comparing two RNAstructures using a full set of biologically relevant edit operations cannot bedone without strong combinatorial restrictions.

Comparing RNA structures using a full set of biologically relevant edit operations is intractable