RNA Folding (RNA Folding)
Revision as of 10:29, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:RNA Folding (RNA Folding)}} == Description == In RNA Folding we are given a string over some alphabet (e.g. $\{A, C, G, T\}$) with a fixed pairing between its symbols (e.g. $A − T$ match and $C − G$ match), and the goal is to compute the maximum number of non-crossing arcs between matching letters that one can draw above the string (which corresponds to the minimum energy folding in two dimensions). == Parameters == <pre>n: length of the given str...")
Description
In RNA Folding we are given a string over some alphabet (e.g. $\{A, C, G, T\}$) with a fixed pairing between its symbols (e.g. $A − T$ match and $C − G$ match), and the goal is to compute the maximum number of non-crossing arcs between matching letters that one can draw above the string (which corresponds to the minimum energy folding in two dimensions).
Parameters
n: length of the given string
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| k-Clique | assume: k-Clique Hypothesis then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |
| k-Clique | assume: k-Clique Hypothesis then: there is no $O(N^{\{3}-\epsilon}) time combinatorial algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |