Nussinov Algorithm

I tried to use subroutines to check the basepairs and minimize my for loops.

Check attached

Example of input

nussinov.pl AUGCUAG

Comparing my data to big O

In my program, the structure is

One For loop to check if there is error in RNA

A subroutine with an ifstatement

One for loop for main diagonal

One for loop diagonal below main diagonal

One for loop with two loops in it to fill the rest of the matrix.

roughly N + C + N + N + N^3 = N^3 + 3N + C

MY DATA:

check attached Experimental Time tab

Nucleotide Length	Time
8	0.0002
16	0.001
32	0.005
64	0.038
128	0.269
256	2.1
384	7.3
512	17
768	59.7
1024	143.8

My bestfit equation with third degree is

f(x) = 1E-07N^3 - 10^5x^2 + 0.0016x - 0.0336, with R value of 1.00. Therefore, L^3 estimates this pretty well.

Here are my values if I plugged the same number of nucleotides into this equation

check attached experimental versus Theoretical tab

Nucleotide Length	Time
8	0
16	0
32	0.0106
64	0.0541
128	0.2171
256	1.3984
384	4.7686
512	11.5859
768	40.5954
1024	98.4932

Notice that when N is very high, the N^3 term takes over. Since each N doubles, the time will increase by a factor of 8.

check attached Experimental versus R^3 tab

Nucleotide Length	Time
8	0.0002
16	0.0016
32	0.0128
64	0.1024
128	0.8192
256	6.5536
384	52.4288

Extra Credit

I modified my randomsequence generator to generate random 100 RNA nucleotides. In that file I also put the Nussinov Algorithm.

I ran the program 20 times and I got the lowest score of 37:

SIMULATED SEQUENCE WITH 20.00% A 20.00% T 20.00% C 40.00% G and length of 100 bp CGAGAUGUUGGGGGAGGGUUGGUUGGCACACUUAGUACUCGCCCUCCCGGCGCGUGGGUAAGACCGGGAAACCUUCAAGA CAUGGUGGAAGGGGUGG The program took 0.183125972747803 seconds to run this sequence. The most number of base pairs found is 37

I	Attachment	Action	Size	Date	Who	Comment
txt	nussinov.pl.txt	manage	3.8 K	2011-10-30 - 04:57	TaiNg	Nussinov File
txt	simulator.pl.txt	manage	11.7 K	2011-10-30 - 05:46	TaiNg	Extra Credit
xlsx	tl.xlsx	manage	19.2 K	2011-10-30 - 06:33	TaiNg	All the graphs

Parents: TWikiUsers > TaiNg