Exponentially few RNA structures are designable
| Autor: | Hua-Ting Yao, Yann Ponty, Mireille Régnier, Cedric Chauve |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), McGill Centre for Bioinformatics (MCB), McGill University = Université McGill [Montréal, Canada], Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms and Models for Integrative BIOlogy (AMIBIO), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), ALARNA, École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Neutral Networks
Fold (higher-order function) Pattern Avoidance 0102 computer and information sciences 01 natural sciences 03 medical and health sciences Design objective Pattern Matching Exponential growth Pattern matching Exponential decay Protein secondary structure 030304 developmental biology Mathematics 0303 health sciences Neutral network RNA Inverse Folding Generating functions 010201 computation theory & mathematics RNA Sequence Analytic combinatorics [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] Biological system RNA Design Analytic Combinatorics |
| Zdroj: | ACM-BCB 2019-10th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics ACM-BCB 2019-10th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, Sep 2019, Niagara-Falls, United States. pp.289-298, ⟨10.1145/3307339.3342163⟩ BCB |
| DOI: | 10.1101/652313 |
| Popis: | The problem of RNA design attempts to construct RNA sequences that perform a predefined biological function, identified by several additional constraints. One of the foremost objective of RNA design is that the designed RNA sequence should adopt a predefined target secondary structure preferentially to any alternative structure, according to a given metrics and folding model. It was observed in several works that some secondary structures are undesignable, i.e. no RNA sequence can fold into the target structure while satisfying some criterion measuring how preferential this folding is compared to alternative conformations.In this paper, we show that the proportion of designable secondary structures decreases exponentially with the size of the target secondary structure, for various popular combinations of energy models and design objectives. This exponential decay is, at least in part, due to the existence of undesignable motifs, which can be generically constructed, and jointly analyzed to yield asymptotic upper-bounds on the number of designable structures. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|