| | |
| | |
Stat |
Members: 3645 Articles: 2'504'928 Articles rated: 2609
25 April 2024 |
|
| | | |
|
Article overview
| |
|
Combinatorial RNA Design | Jozef Haleš
; Alice Héliou
; Ján Maňuch
; Yann Ponty
; Ladislav Stacho
; | Date: |
11 Mar 2016 | Abstract: | We consider the Combinatorial RNA Design problem, a minimal instance of RNA
design where one must produce an RNA sequence that adopts a given secondary
structure as its minimal free-energy structure. We consider two free-energy
models where the contributions of base pairs are additive and independent: the
purely combinatorial Watson-Crick model, which only allows equally-contributing
A -- U and C -- G base pairs, and the real-valued Nussinov-Jacobson model,
which associates arbitrary energies to A--U, C -- G and G -- U base pairs. We
first provide a complete characterization of designable structures using
restricted alphabets and, in the four-letter alphabet, provide a complete
characterization for designable structures without unpaired bases. When
unpaired bases are allowed, we characterize extensive classes of
(non-)designable structures, and prove the closure of the set of designable
structures under the stutter operation. Membership of a given structure to any
of the classes can be tested in $Theta$(n) time, including the generation of a
solution sequence for 2 Jozef Halev{s} et al. positive instances. Finally, we
consider a structure-approximating relaxation of the design, and provide a
$Theta$(n) algorithm which, given a structure S that avoids two trivially
non-designable motifs, transforms S into a designable structure constructively
by adding at most one base-pair to each of its stems. Acknowledgements The
authors would like to thank C’edric Chauve (Simon Fraser University) for
fruitful discussions and constructive criticisms. YP is greatly indebted to the
French Centre National de la Recherche Scientifique and the Pacific Institute
for the Mathematical Sciences for funding an extended visit at the Simon Fraser
University. | Source: | arXiv, 1603.3577 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |