Can you just give the models (objective function and constraints) for each question below ?

We will denote s as a string of n characters consisting of nucleotides: Adenine (A), Guanine (G), Uracil (U) and Cytosine (C).

s = ACGUCCAUGCAG.

Moreover, it is averted that the stability of the RNA is measured by the number of bonds. Consequently, the most stable structure is the one with the maximum binding strength; i.e., the largest number of bonds. Having all the above information, there are also some important conditions that should be taken into consideration while dealing with the RNA folding problem.

Nucleotide A must be paired with only U in which C must be paired with only G (or vice versa).

There are 2 hydrogen bonds between A and U, 3 hydrogen bonds between G and C. Therefore, binding strength differs from pair to pair.

Each nucleotide must be paired with at most 1 nucleotide.

The pairings are not allowed to cross each other. For example, let i < i < j < j , then (i, j) and (i , j ) cannot be paired at the same time. Figure 2: Arc representation of cross pairings (pseudoknots)

There is a distance limitation that close nucleotides cannot be paired; i.e., the nucleotide cannot pair with any nucleotide that is less than 4 positions away from it on the sequence s.

We try to find an integer programming (IP) model that solves the following questions while considering the above conditions.

(a) Given the nucleotide sequence s of an RNA molecule, find a nested pairing that achieves the maximum number of pairs.

(b) Now consider that we try to find a nested pairing that gives the minimum total free energy associated with pairs in the sequence (please use Table 2 for energy levels of matched pairs in your model). Make necessary changes in the IP model and compare your results with part (a). What are the differences in terms of solution time and the number of pairs?

(c) Now consider that there must be at least 7 nucleotides (rather than 4) between pairing ones while keeping the total free energy at minimum as in part (b). What are the differences in terms of solution time and the number of pairs?

(d) A matched pair (i, j) in a nested pairing is defined as a stacked pair if either (i + 1, j 1) or (i 1, j + 1) is also a matched pair in the nested pairing. In other words, there is a stacked pair if and only if both (i, j) and (i + 1, j 1) are in the nested pairing. It is also known that a stack with k matched pairs adds more to stability than k individual matched pairs, which do not belong to any stacks. The stack pair correspond to an energy level, which is shown in Table 1. For instance, if the structure of the sequence s is s = ACGAAAACGU, then the stacked pairs energy level will be (-2.1) +( 2.2) = - 4.3, since we have A-U, C-G, and G-C as nested pairs. That is to say, there has to be at least 2 stacked pairs to lead the energy level. If there is one pair, it is not included in the energy level calculation. We now try to incorporate a count of the number of stacked pairings to obtain more stable structure. Include the given information of stacked pairs and make necessary changes in the IP model in part (b) that finds the minimum total free energy correspond to stacked pairs. Hint: Define a new decision variable to incorporate the stacked pairs into the model.

	A-U	C-G	G-C	G-U	U-G	U-A
A-U	-1.1	-2.1	-2.2	-1.4	-0.9	-0.6
C-G	-2.1	-2.4	-3.3	-2.1	-2.1	-1.4
G-C	-2.2	-3.3	-3.4	-2.5	-2.4	-1.5
G-U	-1.4	-2.1	-2.5	-1.3	-1.3	-0.5
U-G	-0.9	-2.1	-2.4	-1.3	-1.3	-1.0
U-A	-0.6	-1.4	-1.5	-0.5	-1.0	-0.3

Table 1: energy levels of stacking pairs

	U (A)	G (C)
A (U)	-1.33	-
C (G)	-	-1.45

Table 2: Energy levels for matched pairs