Nussinov algorithm
The Nussinov algorithm is a nucleic acid structure prediction algorithm used in computational biology to predict the folding of an RNA molecule that makes use of dynamic programming principles. The algorithm was developed by Ruth Nussinov in the late 1970s. Background. RNA origami occurs when an RNA molecule "folds" and binds to itself. This folding often determines the function of the RNA molecule. RNA folds at different levels, this algorithm predicts the secondary structure of the RNA. Algorithm. Scoring. We score a solution by counting the total number of paired bases. Thus, attempting to maximize the score that  maximizes the total number of bonds between bases. Motivation. Consider an RNA sequence formula_1 whose elements are taken from the set formula_2. Let us imagine we have an optimal solution to the subproblem of folding formula_3 to formula_4, and an optimal solution for folding formula_5 to formula_6 formula_7 . Now, to align formula_3 to formula_9, we have two options: Algorithm. Consider an RNA sequence formula_1 of length formula_23 such that formula_24. Construct an formula_25 matrix formula_26. Initialize formula_26 such that formula_28 formula_29 for formula_30. formula_31 will contain the maximum score for the subsequence formula_32. Now, fill in entries of formula_26 up  and to the right, so that formula_34 where formula_35 After this step, we have a matrix formula_26 where formula_31 represents the optimal score of the folding of formula_32. To determine the structure of the folded RNA by traceback, we first create an empty list of pairs formula_39. We initialize with formula_40. Then, we follow one of three scenarios. When the traceback finishes, formula_39 contains all of the paired bases. Limitations. The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict RNA pseudoknots. Furthermore, in its basic form, it does not account for a minimum stem  loop size. However, it is still useful as a fast algorithm for basic prediction of secondary structure.