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

$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