HW$10-$ Challenge Problem $-$ RNA Structure Prediction $1.$ Given an RNA sequence, such as ACAGU, we can predict its secondary structure by tagging each nucleotide as $(,.,$ or $).$ Each matching pair of $()$ must be AU$,$ GC$,$ or GU $($or their mirror symmetries: UA$,$ CG$,$ UG$).$ We also assume pairs can $\_$not$\_$ cross each other. The following are valid structures for ACAGU: ACAGU $........()..(.).(.).(...)((.))$ We want to find the structure with the maximum number of matching pairs. In the above example, the last structure is optimal $(2$ pairs$).>>>$ best$("$ACAGU$")(2,\text{'}((.))\text{'})$ Tie$-$breaking: arbitrary. Don't worry as long as your structure is one of the correct best structures. the program does not pass all test some other cases $($more cases at the bottom$)$: GCACG $(2,\text{'}().()\text{'})$ UUCAGGA $(3,\text{'}(((.)))\text{'})$ GUUAGAGUCU $(4,\text{'}(.()((.)))\text{'})$ AUAACCUUAUAGGGCUCUG $(8,\text{'}.(((..)()()((()))))\text{'})$ AACCGCUGUGUCAAGCCCAUCCUGCCUUGUU $(11,\text{'}(((.(..(.((.)((...().))()))))))\text{'})$ GAUGCCGUGUAGUCCAAAGACUUCACCGUUGG $(14,\text{'}.()()(()(()())(((.((.)(.))()))))\text{'})$ CAUCGGGGUCUGAGAUGGCCAUGAAGGGCACGUACUGUUU $(18,\text{'}(()())(((((.)))()(((())(.(.().()()))))))\text{'})$ ACGGCCAGUAAAGGUCAUAUACGCGGAAUGACAGGUCUAUCUAC $(19,\text{'}.()(((.)(..))(((.()()(())))(((.)((())))))())\text{'})$ AGGCAUCAAACCCUGCAUGGGAGCACCGCCACUGGCGAUUUUGGUA $(20,\text{'}.(()())...((((()()))((()(.()(((.)))()())))))()\text{'})2.$ Total number of all possible structures $>>>$ total$("$ACAGU$")63.$ k$-$best structures: output the $1-$best, $2$nd$-$best, $...$ kth$-$best structures. $>>>$ kbest$("$ACAGU$",3)[(2,\text{'}((.))\text{'}),(1,\text{'}(...)\text{'}),(1,\text{'}.(.).\text{'})]$ The list must be sorted. Tie$-$breaking: arbitrary. In case the input k is bigger than the number of possible structures, output all. Sanity check: kbest$($s$,1)[0][0]==$ best$($s$)[0]$ for each RNA sequence s$.$