RNA Folding: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: length of the given string | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 13:04, 15 February 2023
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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/abstract/document/8104058 | link |