Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorRzążewski, Paweł
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2021-10-20T14:24:18Z
dc.date.available2021-10-20T14:24:18Z
dc.date.issued2020
dc.identifier.issn1066-5277
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22053
dc.language.isoenen
dc.subjectNP-completenessen
dc.subjectRNA designen
dc.subjectRNA design extensionen
dc.subject.ddc005en
dc.titleDesigning RNA Secondary Structures Is Harden
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA ribonucleic acid (RNA) sequence is a word over an alphabet on four elements called bases. RNA sequences fold into secondary structures where some bases pair with one another, while others remain unpaired. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some models of energy and to design sequences of bases that will fold into targeted secondary structures. Predicting how a given RNA sequence folds into a pseudoknot-free secondary structure is known to be solvable in cubic time since the eighties and in truly subcubic time by a recent result of Bringmann et al. (FOCS, 2016), whereas Lyngsø has shown it is computationally hard if pseudoknots are allowed (ICALP, 2004). As a stark contrast, it is unknown whether or not designing a given RNA secondary structure is a tractable task; this has been raised as a challenging open question by Condon (ICALP, 2003). Because of its crucial importance in a number of fields such as pharmaceutical research and biochemistry, there are dozens of heuristics and software libraries dedicated to the RNA secondary structure design. It is therefore rather surprising that the computational complexity of this central problem in bioinformatics has been unsettled for decades. In this article, we show that in the simplest model of energy, which is the Watson–Crick model, the design of secondary structures is computationally hard if one adds natural constraints of the form: indexiof the sequence has to be labeled by baseb. This negative result suggests that the same lower bound holds for more realistic models of energy. It is noteworthy that the additional constraints are by no means artificial: they are provided by all the RNA design pieces of software and they do correspond to the actual practice (e.g., the instances of the EteRNA project).en
dc.relation.isversionofjnlnameJournal of Computational Biology
dc.relation.isversionofjnlvol27en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2020
dc.relation.isversionofjnlpages302–316en
dc.relation.isversionofdoi10.1089/cmb.2019.0420en
dc.relation.isversionofjnlpublisherMary Ann Lieberten
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2021-10-19T10:58:06Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record