Nussinov algorithm - Revision history

129.175.5.195: Corrected an error in the traceback : i must start at 1, not at zero.

2023-04-03T14:52:02Z

Corrected an error in the traceback : i must start at 1, not at zero.

← Previous revision		Revision as of 14:52, 3 April 2023
Line 37:		Line 37:
	After this step, we have a matrix <math>M</math> where <math>M(i,j)</math> represents the optimal score of the folding of <math>S_i...S_j</math>.		After this step, we have a matrix <math>M</math> where <math>M(i,j)</math> represents the optimal score of the folding of <math>S_i...S_j</math>.

	To determine the structure of the folded RNA by traceback, we first create an empty list of pairs <math>P</math>. We initialize with <math>i=0,j=n</math>. Then, we follow one of three scenarios.		To determine the structure of the folded RNA by traceback, we first create an empty list of pairs <math>P</math>. We initialize with <math>i=1,j=n</math>. Then, we follow one of three scenarios.

	# If <math>j\leq i</math>, the procedure stops.		# If <math>j\leq i</math>, the procedure stops.

218.248.13.196: /* Scoring */

2022-05-01T05:15:21Z

Scoring

← Previous revision		Revision as of 05:15, 1 May 2022
Line 9:		Line 9:

	=== Scoring ===		=== Scoring ===
	We score a solution by counting the total number of paired bases. Thus, attempting to maximize the score maximizes the total number of bonds between bases.		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 ===		=== Motivation ===

GardarJuto: The 'for' was missing what it should describe so I completed it to say for what structure.

2021-10-19T14:42:52Z

The 'for' was missing what it should describe so I completed it to say for what structure.

← Previous revision		Revision as of 14:42, 19 October 2021
Line 37:		Line 37:
	After this step, we have a matrix <math>M</math> where <math>M(i,j)</math> represents the optimal score of the folding of <math>S_i...S_j</math>.		After this step, we have a matrix <math>M</math> where <math>M(i,j)</math> represents the optimal score of the folding of <math>S_i...S_j</math>.

	To determine the structure of by traceback, we first create an empty list of pairs <math>P</math>. We initialize with <math>i=0,j=n</math>. Then, we follow one of three scenarios.		To determine the structure of the folded RNA by traceback, we first create an empty list of pairs <math>P</math>. We initialize with <math>i=0,j=n</math>. Then, we follow one of three scenarios.

	# If <math>j\leq i</math>, the procedure stops.		# If <math>j\leq i</math>, the procedure stops.

Citation bot: Add: doi-access. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 300/732

2021-10-04T21:44:37Z

Add: doi-access. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 300/732

← Previous revision		Revision as of 21:44, 4 October 2021
Line 1:		Line 1:
	{{short description\|Nucleic acid structure prediction algorithm}}		{{short description\|Nucleic acid structure prediction algorithm}}
	{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}		{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}
	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.<ref>{{Cite journal\|last1=Nussinov\|first1=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|doi=10.1073/pnas.77.11.6309\|issn=0027-8424\|pmid=6161375\|pmc=350273\|bibcode=1980PNAS...77.6309N}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.		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.<ref>{{Cite journal\|last1=Nussinov\|first1=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|doi=10.1073/pnas.77.11.6309\|issn=0027-8424\|pmid=6161375\|pmc=350273\|bibcode=1980PNAS...77.6309N\|doi-access=free}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.

	== Background ==		== Background ==

TheLastClassicist1750: Fix misspelling found by Wikipedia:Typo Team/moss – you can help!

2021-05-24T04:54:49Z

Fix misspelling found by Wikipedia:Typo Team/moss – you can help!

← Previous revision		Revision as of 04:54, 24 May 2021
Line 14:		Line 14:
	Consider an RNA sequence <math>S</math> whose elements are taken from the set <math> \{A, U, C, G\}</math>. Let us imagine we have an optimal solution to the subproblem of folding <math>S_i</math> to <math>S_{j-1}</math>, and an optimal solution for folding <math>S_u</math> to <math>S_v</math> <math>i\leq u\leq v\leq j-1</math> . Now, to align <math>S_i</math> to <math>S_{j}</math>, we have two options:		Consider an RNA sequence <math>S</math> whose elements are taken from the set <math> \{A, U, C, G\}</math>. Let us imagine we have an optimal solution to the subproblem of folding <math>S_i</math> to <math>S_{j-1}</math>, and an optimal solution for folding <math>S_u</math> to <math>S_v</math> <math>i\leq u\leq v\leq j-1</math> . Now, to align <math>S_i</math> to <math>S_{j}</math>, we have two options:

	# Leave <math>S_{j}</math> unpaired, and keep the structure of <math>S_i</math> to <math>S_{j-1}</math>. The score for this alignment will be equal to the score of the ~~aligmnent~~ of <math>S_i</math> to <math>S_{j-1}</math>, as no new base pairs were created.		# Leave <math>S_{j}</math> unpaired, and keep the structure of <math>S_i</math> to <math>S_{j-1}</math>. The score for this alignment will be equal to the score of the alignment of <math>S_i</math> to <math>S_{j-1}</math>, as no new base pairs were created.
	# Pair <math>S_{j}</math> with <math>S_{k}</math>, where <math>i\leq k<j</math>. The score for this alignment will be the score of the base pairing, plus the score of the best alignment of <math>S_i</math> to <math>S_{k-1}</math> and <math>S_{k+1}</math> to <math>S_{j-1}</math>.		# Pair <math>S_{j}</math> with <math>S_{k}</math>, where <math>i\leq k<j</math>. The score for this alignment will be the score of the base pairing, plus the score of the best alignment of <math>S_i</math> to <math>S_{k-1}</math> and <math>S_{k+1}</math> to <math>S_{j-1}</math>.

Wprlh: /* Background */Fixed typo.

2021-05-15T18:11:23Z

Background: Fixed typo.

← Previous revision		Revision as of 18:11, 15 May 2021
Line 3:		Line 3:
	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.<ref>{{Cite journal\|last1=Nussinov\|first1=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|doi=10.1073/pnas.77.11.6309\|issn=0027-8424\|pmid=6161375\|pmc=350273\|bibcode=1980PNAS...77.6309N}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.		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.<ref>{{Cite journal\|last1=Nussinov\|first1=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|doi=10.1073/pnas.77.11.6309\|issn=0027-8424\|pmid=6161375\|pmc=350273\|bibcode=1980PNAS...77.6309N}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.

	== ~~Backgound~~ ==		== 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.		[[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 ==		== Algorithm ==

Citation bot: Add: bibcode, pmc, doi, authors 1-1. Removed proxy or dead URL that duplicated free-DOI or unique identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Pages linked from cached Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | via #UCB_webform_linked 372/705

2021-02-23T19:43:00Z

Add: bibcode, pmc, doi, authors 1-1. Removed proxy or dead URL that duplicated free-DOI or unique identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Pages linked from cached Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | via #UCB_webform_linked 372/705

← Previous revision		Revision as of 19:43, 23 February 2021
Line 1:		Line 1:
	{{short description\|Nucleic acid structure prediction algorithm}}		{{short description\|Nucleic acid structure prediction algorithm}}
	{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}		{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}
	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.<ref>{{Cite journal\|~~last~~=Nussinov\|~~first~~=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.~~\|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC350273/~~\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|issn=0027-8424\|pmid=6161375}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.		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.<ref>{{Cite journal\|last1=Nussinov\|first1=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|doi=10.1073/pnas.77.11.6309\|issn=0027-8424\|pmid=6161375\|pmc=350273\|bibcode=1980PNAS...77.6309N}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.

	== Backgound ==		== Backgound ==

114.44.73.17: /* Algorithm */

2021-01-06T12:56:12Z

Algorithm

← Previous revision		Revision as of 12:56, 6 January 2021
Line 30:		Line 30:
	<math>M(i,j)</math> will contain the maximum score for the subsequence <math>S_i...S_j</math>. Now, fill in entries of <math>M</math> up and to the right, so that		<math>M(i,j)</math> will contain the maximum score for the subsequence <math>S_i...S_j</math>. Now, fill in entries of <math>M</math> up and to the right, so that

	<math>M(i,j) = \~~min_~~{i\leq k<j}\begin{cases}M(i, k-1)+M(k+1, j-1)+\text{Score}(S_k,S_j) \\ M(i, j-1)\end{cases}</math>		<math>M(i,j) = \max_{i\leq k<j}\begin{cases}M(i, k-1)+M(k+1, j-1)+\text{Score}(S_k,S_j) \\ M(i, j-1)\end{cases}</math>

	where <math>\text{Score}(S_k,S_j)=\begin{cases}1,&S_k\text{ and }S_j \text{ complementary}\\		where <math>\text{Score}(S_k,S_j)=\begin{cases}1,&S_k\text{ and }S_j \text{ complementary}\\

Monkbot: Task 18 (cosmetic): eval 2 templates: del empty params (8×); del |url-status= (1×);

2020-12-22T16:26:47Z

Task 18 (cosmetic): eval 2 templates: del empty params (8×); del |url-status= (1×);

← Previous revision		Revision as of 16:26, 22 December 2020
Line 1:		Line 1:
	{{short description\|Nucleic acid structure prediction algorithm}}		{{short description\|Nucleic acid structure prediction algorithm}}
	{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}		{{Infobox algorithm\|name=<!-- Defaults to article name -->\|class=Nucleic acid structure prediction\|image=\|caption=\|data=\|time=<math>O(n^3)</math>\|best-time=\|average-time=\|space=<math>O(n^2)</math>}}
	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.<ref>{{Cite journal\|last=Nussinov\|first=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC350273/\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|issn=0027-8424\|pmid=6161375~~\|via=~~}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.		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.<ref>{{Cite journal\|last=Nussinov\|first=R\|last2=Jacobson\|first2=A B\|date=Nov 1980\|title=Fast algorithm for predicting the secondary structure of single-stranded RNA.\|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC350273/\|journal=Proceedings of the National Academy of Sciences of the United States of America\|volume=77\|issue=11\|pages=6309–6313\|issn=0027-8424\|pmid=6161375}}</ref> The algorithm was developed by [[Ruth Nussinov]] in the late 1970s.

	== Backgound ==		== Backgound ==
Line 46:		Line 46:

	== Limitations ==		== Limitations ==
	The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict [[Pseudoknot\|RNA pseudoknots]].<ref>{{Cite web~~\|last=\|first=\|date=~~\|title=RNA Structure and RNA Structure Prediction\|url=https://math.mit.edu/classes/18.417/Slides/rna-prediction-nussinov.pdf~~\|url-status=live\|archive-url=\|archive-date=\|access-date=\|website=~~}}</ref> 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.		The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict [[Pseudoknot\|RNA pseudoknots]].<ref>{{Cite web\|title=RNA Structure and RNA Structure Prediction\|url=https://math.mit.edu/classes/18.417/Slides/rna-prediction-nussinov.pdf}}</ref> 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.

	== References ==		== References ==

WikiCleanerBot: v2.04b - Bot T18 CW#553 - Fix errors for CW project ( tags)

2020-11-23T11:43:11Z

v2.04b - Bot T18 CW#553 - Fix errors for CW project (<nowiki> tags)

← Previous revision		Revision as of 11:43, 23 November 2020
Line 46:		Line 46:

	== Limitations ==		== Limitations ==
	The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict [[Pseudoknot\|RNA ~~pseudoknot~~]]~~<nowiki/>s~~.<ref>{{Cite web\|last=\|first=\|date=\|title=RNA Structure and RNA Structure Prediction\|url=https://math.mit.edu/classes/18.417/Slides/rna-prediction-nussinov.pdf\|url-status=live\|archive-url=\|archive-date=\|access-date=\|website=}}</ref> 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.		The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict [[Pseudoknot\|RNA pseudoknots]].<ref>{{Cite web\|last=\|first=\|date=\|title=RNA Structure and RNA Structure Prediction\|url=https://math.mit.edu/classes/18.417/Slides/rna-prediction-nussinov.pdf\|url-status=live\|archive-url=\|archive-date=\|access-date=\|website=}}</ref> 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.

	== References ==		== References ==