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.
1 answer
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.
Log in to answer this question.
-
Snakemake rule to copy files
written by DBScan •
-
R: How to correctly compute p-value of a k-mer?
written by francois •
-
Power analysis for covariate-adjusted two sample t-test
written by coleman_jonathan
-
Forum: So how big is bioinformatics? Well a lot bigger than I thought ...
written by Istvan Albert
-
How To Extract Sequence From Overlapping Regions From Fasta Files With Perl
written by speedgummi •
-
Interpreting Structure Conservation Analysis
written by pld
-
Clonalorigin Error "Segmentation Fault"
written by thakurshalabh •
-
Aligning And Find Secondary Structures
written by saeid •
-
Problems With Sequence Parts In Biopython
written by elmagodelabahia •
-
Categorizing Protein Families?
written by ilovepython •
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).