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 |
||
| (One intermediate revision by the same user not shown) | |||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: length of the given string | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:28, 10 April 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 |