Fall11 > TWikiUsers > TaiNg > TaiLunNgHomeWorkFive

Changes | Index | Search | Go
-- %TEACHINGWEB%.TaiNg - 29 Oct 2011

# 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
Copyright © 2008-2013 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback