Find the maximum pseudoknot number on the C&C matchings on n edges as a function of n.
admin
1 min read
Project: We also define here a biologically motivated statistic called the pseudoknot number pknot(M). A pseudoknot occurs in a strand of RNA when the strand folds on itself and forms secondary bonds between nucleotides, and then the same strand wraps around and forms secondary bonds again. However, when that pseudoknot has several nucleotides bonded in a row, we do not consider that a “new” pseudoknot. The pseudoknot number of a matching, pknot(M), counts the number of pseudoknots on the RNA motif by deflating any ladders in the matching and then finding the crossing number on the resulting matching. For example in Fig. 1.16 we give two matchings containing hairpins (pseudoknots). Even though their crossing numbers both equal 6, we see that in Fig. 1.16A, these crossing arise from a single pseudoknot, and so their pknot number is 1, while in Fig. 1.16B, the pknot number is 3. Find the maximum pseudoknot number on the C&C matchings on n edges as a function of n. Compare this to the maximum pseudoknot number on all perfect matchings.
