Question: Computing The Number Of Possible Rna Secondary Structures
1
gravatar for soosus
6.9 years ago by
soosus80
soosus80 wrote:

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.

rna structure secondary • 1.9k views
ADD COMMENTlink modified 6.9 years ago by jockbanan390 • written 6.9 years ago by soosus80

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).

ADD REPLYlink modified 6.9 years ago • written 6.9 years ago by Devon Ryan96k
0
gravatar for jockbanan
6.9 years ago by
jockbanan390
Czech Republic
jockbanan390 wrote:

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.

ADD COMMENTlink written 6.9 years ago by jockbanan390
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 671 users visited in the last hour