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

DOI10.1007/S00453-016-0196-XMaRDI QIDQ1679233zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

inverse combinatorial optimizationRNA structurestring design

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 1748997 (Why is no real title available?)
• 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

Describes a project that uses

Uses Software

• NNDB
• MODENA
• RNAexinv

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)