Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models

DOI10.1007/S00453-016-0196-XzbMATH Open1383.92058arXiv1603.03577OpenAlexW2498333024WikidataQ57220929 ScholiaQ57220929MaRDI QIDQ1679233FDOQ1679233

Authors: Jozef Haleš, Alice Héliou, Ján Maňuch, Yann Ponty, Ladislav Stacho 

Publication date: 9 November 2017

Published in: Algorithmica (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1603.03577

Recommendations

• Combinatorial RNA design: designability and structure-approximating algorithm
• An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures
• On realizing shapes in the theory of RNA neutral networks
• Combinatorics of locally optimal RNA secondary structures
• Impact of the energy model on the complexity of RNA folding with pseudoknots

zbMATH Keywords

inverse combinatorial optimizationRNA structurestring design

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Fluctuations and ergodicity of the form factor of quantum propagators and random unitary matrices

Cited In (6)

• Combinatorial RNA design: designability and structure-approximating algorithm
• Efficient design of compact unstructured RNA libraries covering all \(k\)-mers
• On realizing shapes in the theory of RNA neutral networks
• Balancing minimum free energy and codon adaptation index for Pareto optimal RNA design
• An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures
• Transcript design problem of oritatami systems

Uses Software

• RNAexinv
• MODENA
• NNDB

This page was built for publication: Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679233)