Friday, 2020-02-28 BioInfo Pakistan
Section categories
 Related Subjects [38]This category includes brief overview of all related subjects. Defining BioInformatics [7]In this section we tried to briefly explain what bioinformatics is ? Unviersities [30]This contains information about universities that are offering bioinformatics degree programs. Resources [24]Contains information about bioinformatics resources including databases, tools and techniques. Algorithms [31]This category includes some of the basic algorithms that are usually used by bioinformaticians.
 Our poll Pakistani Student Yes No Total of answers: 0
 Chat Box Only authorized users can post messages
 Statistics Total online: 1 Guests: 1 Users: 0
Home » 2011 » August » 19 » Nussinov Algorithm
10:40 PM
Nussinov Algorithm

 Nussinov Algorithm1. Description:   Nussinov algorithm is an algorithm to predict possible RNA secondary structure (folding), discovering parts that have complementary sequences. Unlike search algorithms, this method works with the single sequence. It computes the sequence against itself using dynamic programming table, however the matching scores are set so that the letters are treated as "matching" if the corresponding nucleotides would pair. Hence A "matches" U and G "matches" C, but none of the four (AGUC) nucleotides matches itself as two identical nucleotides do not pair. 2. Algorithm:   The algorithm is formally written as   Here w(i,j) = 1 if chars at the positions i and j are complementary (AU, UA, GC, CG). Otherwise this function is 0.   Another formula set that may be simpler is given in  and referred as Nussinov-Jacobson algorithm:   With initialization   Nussinov algorithm does not necessary generates the most stable structure and may have scattered matches that are not biologically reasonable. It is too simple to be accurate but has been a stepping stone for more complex algorithms.3. Key points:Given an RNA sequence of length L.Find the structure with the most base pairsThere are four ways of getting the best structure between position i and j from the best structures of the smaller subsequences:Add unpaired position i onto best structure for subsequence i+1, jAdd unpaired position j onto best structure for subsequence i, j-1Add i,j pair onto best structure found for subsequence i+1, j-1Combine two optimal structures i,k and k+1, jFour CasesThe numbers above each case corresponds to the enumeration on the previous slide.Compares a sequence against itself in a dynamic programming matrix.Since structure folds upon itself, it is only necessary to calculate half the matrix.The value of M[i,j] is the number of base pairs in the maximally base-paired structure.Four rules for scoring the structure at a particular point.4. Pseudocode:Initialization: fill the main diagonal and the diagonal just below it with zerosFormally, the scoring matrix, M, is initialized:M[i,i] = 0 for i = 1 to L (main diagonal)M[i,i-1] = 0 for i = 2 to L (diagonal below main diagonal)Matrix Fill: Starting with all subsequences of length 2, to length LdoM[i,j] = max of the following :M[i+1,j] (base i is hanging off by itself)M[i,j-1] (base j is hanging off by itself)M[i+1,j-1] + S(xi, xj) (bases i and j are paired; if xi = complement of xj, then S(xi, xj) = 1; otherwise it is 0)M[i,j] = MAXi
Category: Algorithms | Views: 9358 | Added by: Ansari | Rating: 0.0/0
 0 2 MelbaUrive   (2017-01-13 11:02 AM) [Entry] free resume templates for illustrator free business plan for call center format of effective resume http://1terra.net/web/link.aspx?url=http://fiveshots.us

 0 1 beardswyiaj   (2012-08-15 9:39 PM) [Entry] 锘縖url=http://www.activationsale.com] win key sale[/url] yepsww 锘縖url=http://www.activationsale.com] Office Professional Plus 2007[/url] bjhy

Name *:
Email *:
Code *: