Hardness of RNA Folding Problem with Four Symbols

Yi-Jun Chang

An RNA sequence is a string composed of four types of nucleotides, $A,C,G$, and $U$. The goal of the RNA folding problem is to find a maximum cardinality set of crossing-free pai…