Combinatorial RNA design: designability and structure-approximating algorithm

DOI10.1007/978-3-319-19929-0_20MaRDI QIDQ2942260zbMATH OpenOpenAlexWikidataFDO

Authors Jozef Haleš, Ján Maňuch, Yann Ponty, Ladislav Stacho

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15) Approximation algorithms (68W25) Algorithms on strings (68W32) Protein sequences, DNA sequences (92D20)

Abstract: In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem which aims at finding a sequence that admits a given target as its unique base pair maximizing structure. We provide complete characterizations for the structures that can be designed using restricted alphabets. Under a classic four-letter alphabet, we provide a complete characterization of designable structures without unpaired bases. When unpaired bases are allowed, we provide partial characterizations for classes of designable/undesignable structures, and show that the class of designable structures is closed under the stutter operation. Membership of a given structure to any of the classes can be tested in linear time and, for positive instances, a solution can be found in linear time. Finally, we consider a structure-approximating version of the problem that allows to extend bands (helices) and, assuming that the input structure avoids two motifs, we provide a linear-time algorithm that produces a designable structure with at most twice more base pairs than the input structure.

Recommendations

• Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models
• An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures
• On realizing shapes in the theory of RNA neutral networks
• Efficient design of compact unstructured RNA libraries covering all k-mers
• scientific article; zbMATH DE number 1953220

Cited in

(10)

• Combinatorial design of pseudoknot RNA
• Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models
• Design of nucleic acid strands with long low-barrier folding pathways
• siRNA design. Methods and protocols
• Efficient design of compact unstructured RNA libraries covering all k-mers
• Balancing minimum free energy and codon adaptation index for Pareto optimal RNA design
• Scalable and interpretable identification of minimal undesignable RNA structure motifs with rotational invariance
• Undesignable RNA structure identification via rival structure generation and structure decomposition
• On realizing shapes in the theory of RNA neutral networks
• An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures

This page was built for publication: Combinatorial RNA design: designability and structure-approximating algorithm

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