Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorRzążewski, Pawel
dc.contributor.authorSikora, Florian
dc.date.accessioned2019-03-21T11:15:46Z
dc.date.available2019-03-21T11:15:46Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18544
dc.descriptionLecture Notes in Computer Science book series (LNCS, volume 10812)en
dc.language.isoenen
dc.subjectprobabilistic modelsen
dc.subjectprobabilityen
dc.subjectproblem solvingen
dc.subject.ddc519en
dc.titleDesigning RNA Secondary Structures Is Harden
dc.typeCommunication / Conférence
dc.description.abstractenAn RNA sequence is a word over an alphabet on four elements {A,C,G,U} called bases. RNA sequences fold into secondary structures where some bases match one another while others remain unpaired. Pseudoknot-free secondary structures can be represented as well-parenthesized expressions with additional dots, where pairs of matching parentheses symbolize paired bases and dots, unpaired bases. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some model of energy and to design sequences of bases which 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). 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 Anne 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 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 paper we show that, in the simplest model of energy which is the Watson-Crick model the design of secondary structures is NP-complete if one adds natural constraints of the form: index i of the sequence has to be labeled by base b. This negative result suggests that the same lower bound holds for more realistic models of energy.en
dc.identifier.citationpages248-250en
dc.relation.ispartoftitleResearch in Computational Molecular Biology - 22nd Annual International Conference (RECOMB 2018)en
dc.relation.ispartofeditorRaphael, Benjamin J.
dc.relation.ispartofpublnameSpringer Berlin Heidelbergen
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2018
dc.relation.ispartofpages298en
dc.relation.ispartofurl10.1007/978-3-319-89929-9en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-3-319-89928-2en
dc.relation.conftitleRECOMB 2018en
dc.relation.confdate2018-04
dc.relation.confcityParisen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-89929-9en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-21T11:04:25Z
hal.person.labIds147435
hal.person.labIds161255
hal.person.labIds989
hal.identifierhal-02075335*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record