Combinatorial RNA

Let's call $R_N$ the number of different arrangements of an RNA molecule consisting of $N$ bases.

Consider the very first base of the chain, there are two possibilities for it:

• If it's free, then the other bases can be arranged in $R_{N-1}$ different ways.

• If it's paired, there are $N-1$ possible couples for it and in each case, the remaining bases can be arranged in $R_{N-2}$ different ways.

We have a recurrence relation! starting whith $R_1=1$ and $R_2=2$ : $R_N=R_{N-1}+(N-1)R_{N-2}$

One could try here to find a closed form for the recurrence, but it is generally not easy to do so. I just wrote a little Python code to find $R_{100}=24053347438333478953622433243028232812964119825419485684849162710512551427284402176$ that has $\boxed{83}$ digits.

1
2
3
4
5

R=[1,1,2]
for N in range(3,101):
    R.append(R[N-1]+(N-1)*R[N-2])
print(R[100])
print(len(str(R[100])))

This problem is an application of permutations .

Let's break down the steps required to count the number of arrangements. We'll have to

1. Select the number of pairs $k$ to consider.
2. Select $2k$ bases to form the $k$ pairs out of.
3. Partition the $2k$ bases into $k$ pairs, each of which have $2$ bases.

For Step 1, we'll have to sum up all possible number of pairs, from $0$ (a completely unpaired molecule of $N$ bases) to $N/2$ (every base is paired). So from this step, we'll just take some number $k$ to stand for the number of base pairs we'll be considering for the later steps.

For Step 2 , we need to choose $2k$ bases from the $N$ total bases in the molecule to participate in the $k$ base pairs. This is a pretty straightforward quantity that we can express using the binomial " $N$ choose $2k$ ":

$\binom{N}{2k} = \frac{N!}{(2k)!(n-2k)!}.$

For Step 3 , things get a bit more dicey. Since this is a partitioning problem, we seek to find the number of ways to put $2k$ interchangeable bases into $k$ pairs, so that each pair has exactly $2$ bases in it. A good first guess might be to use the multinomial, something like this:

$\binom{N}{2,...2},$

where the number of $2$ in the multinomial is $k$ , the number of pairs we wish to form. This multinomial is equivalently stated using factorials as:

$\binom{N}{2,...2} = \frac{(2k)!}{2^k},$

since $2! = 2$ .

But we'd be way over-counting if we took this term as the number of ways of performing Step 3. If we use a straight up binomial, we're assuming an ordering on the pairs even though they don’t have one, the order of the pairs that we select don't matter when we're uniquely determining an RNA structure, so we are over-counting by a factor of the number of ways of arranging the $k$ base pairs. So to correct for this factor, we can still use the multinomial but we also have to divide by a factor of $k!$ . So the number of ways of performing Step 3 is:

$\binom{N}{2,...2} \times \frac{1}{k!} = \frac{(2k)!}{2^k k!}.$

Add 'em up

So combining Steps 2 and 3, we can figure out the number of arrangements for a given number of base pairs $k$ :

$n(k) = \frac{N!}{(2k)!(N-2k)!} \frac{(2k)!}{2^k} \frac{1}{k!}$

As we mentioned for Step 1, we need to add up all the possible numbers of base pairs $n$ , from $0$ to $N/2$ . Of course if $N$ is odd, we don't want a fraction, so really we want the floor: $\left \lfloor{\frac{N}{2}}\right \rfloor .$

$n = \sum_0^{\left \lfloor{\frac{N}{2}}\right \rfloor} \frac{N!}{(N-2k)! 2^k k!}$

Now that we've got this function, we can just plug in the number of bases we're considering, $N=100$ , to yield the number of arrangements. I did this with Mathematica. It's a really big number:

$n(100) = 24053347438333478953622433243028232812964119825419485684849162710512551427284402176$

Which has 83 digits.

Side Note

For short RNA sequences, enumerating all the possible arrangements and scoring them using their sequence is practical. Given a sequence, if an $\tt A$ base pairs with a $\tt U$ base the score goes up by $1$ , as with a $\tt C$ base pairing with a $\tt G$ base. Other "wobble" pairs like $\tt U$ and $\tt G$ add a somewhat lower number to the score.

But there's no way anyone is ever going to enumerate and score all of the arrangements for a $N=100$ RNA molecule. Thanks to some enterprising work by a biologist named Ruth Nussinov in the late 1970s, we don't have to. Her algorithm uses dynamic programming to decrease the time requirements from combinatorial $O(n!)$ to low polynomial time $O(n^3)$ .

If we have n nodes, the number of pairs that can be formed ranges from $0$ to $\lfloor \frac{n}{2}\rfloor$ .

To place p pairs among n nodes can be done in $\frac{n!}{(n-2p)!2^p p!}$ ways.

For n=100, we sum this expression for p ranging from 0 to 50 and get

$\sum_{p=0}^{50} \frac{n!}{(n-2p)!2^p p!}=24053347438333478953622433243028232812964119825419485684849162710512551427284402176$

which has $\boxed{83}$ digits.

See also Sloane's OEIS