Computing The Number Of Possible Rna Secondary Structures

Question

[soosus]

If I am to let z(n) denote the number of possible secondary structures of a given RNA of n nucleotides without crossing, what would be the recursive relation of z(n)?

I must also argue that the time it takes to compute z(n) only grows as n to some power (or a power-law in n).

I want to write a simple iterative program to compute z(n) and estimate how z(n) depends on n using the numerical data generated by your program, but am uncertain where to start.

[Devon Ryan]

You realize that the possible secondary structures of an RNA aren't only dependent on length, but also on nucleotide sequence. If you have an RNA that's only U's, then it'll be disordered, regardless of length.

BTW, the time taken to compute something depends on the algorithm used (compare a directed search against a brute-force search).

Answer 1

[jockbanan]

There is no such recurrence relation. You have to find these structures in order to count them. The basic way of doing this is Nussinov algorithm - a dynamic programming algorithm very similar to Smith-Waterman, not hard to code. It runs in polynomial time and space. Just note that Nussinov is not able to handle pseudoknots, so any structure containing pseudoknots will not be discovered this way. It is generally much harder to find structures with pseudoknots.