Designing RNA secondary structures is hard
Conference paper
Bonnet, E., Rzążewski, P. and Sikora, F. 2018. Designing RNA secondary structures is hard. 22nd Annual International Conference on Research in Computational Molecular Biology (RECOMB 2018). Paris, France 21 - 24 Apr 2018 Springer. pp. 248-250
Type | Conference paper |
---|---|
Title | Designing RNA secondary structures is hard |
Authors | Bonnet, E., Rzążewski, P. and Sikora, F. |
Abstract | An 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), whereas Lyngsø has shown it is NP-complete 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 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. |
Conference | 22nd Annual International Conference on Research in Computational Molecular Biology (RECOMB 2018) |
Page range | 248-250 |
ISSN | 0302-9743 |
ISBN | |
Hardcover | 9783319899282 |
Publisher | Springer |
Publication dates | |
24 Apr 2018 | |
Publication process dates | |
Deposited | 23 Apr 2018 |
Accepted | 21 Dec 2017 |
Output status | Published |
Accepted author manuscript | |
Copyright Statement | The final authenticated version is available online at https://doi.org/10.1007/978-3-319-89929-9 |
Additional information | published as Édouard Bonnet, Paweł Rzążewski, and Florian Sikora, Designing RNA Secondary Structures Is Hard. In: Raphael B. (eds) Research in Computational Molecular Biology. RECOMB 2018. pp. 248-250. Lecture Notes in Computer Science, vol 10812. Springer, Cham |
Web address (URL) | https://doi.org/10.1007/978-3-319-89929-9 |
Language | English |
Book title | Research in Computational Molecular Biology: 22nd Annual International Conference, RECOMB 2018, Paris, France, April 21-24, 2018, Proceedings |
https://repository.mdx.ac.uk/item/879y4
Download files
30
total views7
total downloads1
views this month0
downloads this month