الگوریتم ناسینوف

یک ساختار دوم بهینه‌ی توالی RNA ژنوم یک ویروس که با الگوریتم ناسینوف محاسبه شده است. ساختار 18 تا جفت باز دارد و 41 ساختار دوم مشترک بهینه (co-optimal) برای این توالی ورودی با 18 تا جفت باز وجود دارد.
الگوریتم ناسینوف (Nussinov Algorithm) حداکثر تعداد جفت بازهای ممکن یک توالی اسید نوکلئیک داده شده را محاسبه می‌کند. در مرحله‌ی بعدتر، ساختار دوم با حداکثر تعداد جفت بازها(base pair) می‌تواند ساخته شود. این الگوریتم روش‌های برنامه نویسی پویا را به کار می‌برد.
الگوریتم
طول توالی ورودی است. N یک ماتریس در است و تابع اگر مکمل باشد،(یعنی باهم پیوند بازی تشکیل دهند) 1 برمی گرداند و درغیراین صورت 0 برمی گرداند.
پیوندهای بازی مجاز نیستند که باهم تداخل داشته باشند. برای جفت بازهایی با اندیس‌های
با شرط و اندیس‌های با شرط
هیچ پیوندی یا ایجاد نمی‌شود.
زیررشته‌ی که با نمایش می‌شود، زیررشته‌ی به طول 1 و زیررشته‌ی که با نمایش داده می‌شود، زیررشته‌ی به طول 0 یا همان زیررشته‌ی تهی نامیده می‌شود.
مقداردهی اولیه
زیررشته‌ی به طول 1 و زیررشته‌ی تهی به طول 0 شامل حداکثر 0 جفت باز است.(یعنی هیچ وقت i با خودش پیوند بازی تشکیل نمی‌دهد.)
رابطه‌ی بازگشتی
Ni,j=\max \begin{Bmatrix
Ni,j-1 - \\
\max_{i\le k<j-1 (Ni,k-1 + 1 + Nk+1,j-1)\cdot \sigma(k, j) -
\end{Bmatrix,
0\le i<n,
0<j<n
, i<j
در انتهای الگوریتم در خانه‌ی ماتریس N ، تعداد ماکزیمم جفت بازهای زیررشته‌های از به دست می‌آید. به طوری که حداکثر تعداد جفت بازهای ممکن توالی ورودی کلی در ذخیره شده است.
موارد متمایز در رابطه‌ی بازگشتی دو مورد می‌باشد. یا اینکه در زیررشته‌ی حداکثر تعداد جفت بازها محاسبه شده است و در حال حاضر هدف گسترش آن با یک باز است که با هیچ باز دیگری جفت نشده است. یا به طور کامل‌تر باز با یک باز دیگر در پیوند تشکیل دهد.
در مورد دوم k تا باز ممکن وجود دارد که می‌تواند جفت باز تشکیل دهد.انتخاب باز مکمل ، زیررشته‌های را به دو زیررشته‌ی
و تقسیم می‌کند و این‌ها طوری به هم وصل می‌شوند که حداکثر تعداد جفت بازها به صورت بازگشتی محاسبه شود.
اگر مکمل باشد، مقدار تابع ،
و در غیراین صورت است.
تمایز موارد مطابق با گرامر مستقل از متن زیر است :
به طوریکه به یک باز جفت نشده(تنها) اشاره می‌کند و براکت نشان دهنده‌ی همه‌ی متغیرهای جفت بازهای مکمل ممکن است. پس از این گرامر همه‌ی ساختارهای به دست آمده از الگوریتم ناسینوف می‌توانند بهینه تلقی شوند.
ساختار دوم شامل ماکزیمم تعداد پیوندهای بازی است که می‌توانند توسط روش برگشت به عقب از خانه‌ی ماتریس به دست آیند. یعنی روی ماتریس مسیرهای برگشتی وجود دارد که نتیجه‌ی بهینه در را می‌دهند و این الگوریتم برگشت به عقب عملیاتی را انجام می‌دهد که مسیرهای بهینه‌ی ساختار دوم را تولید می‌کند.
کارایی
الگوریتم یک ماتریسی با درایه به کار می‌برد، بنابراین به حافظه نیاز دارد و هر درایه از طریق عنصر بهینه خواهد شد پس زمان اجرای الگوریتم است.
علامت گذاری
مشخصات ماتریس بالا مطابق با نمایش ناسینوف بازگشتی در سال 1978 می‌باشد. گاهی اوقات به ادبیات اخیر به عنوان یک تنوعی برای این الگوریتم ناسینوف بازگشتی اشاره شده است(z. B. Durbin, 2006). در مقاله‌ی Durbin در سال 2006 بازگشت، 4 مورد متمایز است. این گوناگونی، مقادیر محاسبه شده توسط ماتریس را تغییر نمی‌دهد، اما روش برگشت به عقب چندین مسیر مختلف در یک ساختار دوم ارائه می‌دهد که تمایز آنها از نظر معنایی مبهم است.
ارتباط بیولوژیکی
ساختار دومی که شامل ماکزیمم تعداد جفت بازهاست لزوما آن ساختاری نیست که در طبیعت (در یک سلول) اتفاق بیفتد. بنابراین در عمل الگوریتم ناسینوف برای پیش گویی ساختار دوم توالی‌های RNA به کار برده نمی‌شود. در عمل ساختار دوم پیش گویی شده تحت یک مدل ترمودینامیکی (برای مثال الگوریتم زوکر Zuker Algorithm را ببینید)است که منجر به نتایج معنادار بیولوژیکی می‌شود.با این حال الگوریتم ناسینوف از نظر تئوری در آموزش و پژوهش مورد توجه و علاقه است.برای مثال
الگوریتم روش برگشت به عقب واترمن بایرز، Waterman-Byers-backtracking برای پیدا کردن زیرساختارهای بهینه به کار برده شد تا یک مثال از ماتریس برگشتی معین را توصیف کند. مطالعه الگوریتم آموزنده است، چرا که ، مانند الگوریتم‌های دیگر پیش بینی ساختار RNA، از روش برنامه نویسی پویا استفاده می‌کند که دارای یک ماتریس بازگشتی است و به آسانی قابل درک است.