What makes the arc-preserving subsequence problem hard

1 Introduction At a molecular state, the understanding of biological mechanisms is subordinated to RNA functionsdiscovery and study. Indeed, it is established that the conformation of a single-stranded RNA molecule (a linear sequence composed of ribonucleotides A, U, C and G, also called primarystructure) partly determines the molecule function. This conformation results from the folding process due to local pairings between complementary bases (A-U and C-G). The RNA secondarystructure is a collection of folding patterns that occur in it