الگوریتم ناسینوف کیست؟ توضیح بده.
الگوریتم ناسینوف (Nussinov Algorithm) حداکثر تعداد جفت بازهای ممکن یک توالی اسید نوکلئیک داده شده را محاسبه می‌کند. در مرحلهٔ بعدتر، ساختار دوم با حداکثر تعداد جفت بازها(base pair) می‌تواند ساخته شود. این الگوریتم روش‌های برنامه نویسی پویا را به کار می برد.الگوریتم.formula_1 طول توالی ورودی است. N یک ماتریس formula_1 در formula_1 است و تابع formula_4 اگر formula_5 مکمل formula_6 باشد،(یعنی باهم پیوند بازی تشکیل دهند) 1 برمی گرداند و درغیراین صورت 0 برمی گرداند.پیوندهای بازی مجاز نیستند که باهم تداخل داشته باشند. برای جفت بازهایی با اندیس‌های formula_7 با شرط formula_8 با شرط formula_9هیچ پیوندی formula_10 که با formula_11 نمایش می‌شود، زیررشتهٔ به طول 1 و زیررشتهٔ formula_5 که با formula_13 نمایش داده می‌شود، زیررشتهٔ به طول 0 یا همان زیررشتهٔ تهی نامیده می‌شود.مقداردهی اولیه.formula_14formula_15 به طول 1 و زیررشتهٔ تهی formula_16 به طول 0 شامل حداکثر 0 جفت باز است.(یعنی هیچ وقت i با خودش پیوند بازی تشکیل نمی‌دهد.)رابطهٔ بازگشتیformula_17در انتهای الگوریتم در خانهٔ formula_18 ماتریس N ، تعداد ماکزیمم جفت بازهای زیررشته‌های formula_19 از formula_20 به دست می آید. به طوری که حداکثر تعداد جفت بازهای ممکن توالی ورودی کلی formula_20 در formula_22 ذخیره شده‌است.موارد متمایز در رابطهٔ بازگشتی دو مورد می‌باشد . یا اینکه در زیررشتهٔ formula_23 حداکثر تعداد جفت بازها محاسبه شده‌است و در حال حاضر هدف گسترش آن با یک باز است که با هیچ باز دیگری جفت نشده‌است. یا به‌طور کامل تر باز formula_24 با یک باز دیگر در formula_23 پیوند تشکیل دهد.در مورد دوم k تا باز ممکن وجود دارد که formula_24 می‌تواند جفت باز تشکیل دهد.انتخاب باز مکمل formula_24، زیررشته‌های formula_28 را به دو زیررشتهٔ formula_29 و formula_30 تقسیم می‌کند و این‌ها طوری به هم وصل می‌شوند که حداکثر تعداد جفت بازها به صورت بازگشتی محاسبه شود.اگر formula_31 مکمل formula_32 باشد، مقدار تابع formula_33 ،formula_34 و در غیراین صورت formula_35 است.تمایز موارد مطابق با گرامر مستقل از متن زیر است :formula_36به طوریکه formula_37 به یک بازِ جفت نشده(تنها) اشاره می‌کند و براکت نشان دهندهٔ همهٔ متغیرهای جفت بازهای مکمل ممکن است. پس از این گرامر همهٔ ساختارهای به دست آمده از الگوریتم ناسینوف می توانند بهینه تلقی شوند.ساختار دوم شامل ماکزیمم تعداد پیوندهای بازی است که می توانند توسط روش برگشت به عقب از خانهٔ formula_38 ماتریس به دست آیند. یعنی روی ماتریس مسیرهای برگشتی وجود دارد که نتیجهٔ بهینه در formula_39 را می دهند و این الگوریتم برگشت به عقب عملیاتی را انجام می‌دهد که مسیرهای بهینهٔ ساختار دوم را تولید می‌کند.کارایی.الگوریتم یک ماتریسی با formula_40 درایه به کار می برد، بنابراین به formula_41 حافظه نیاز دارد و هر درایه از طریق formula_42 عنصر بهینه خواهد شد پس زمان اجرای الگوریتم formula_43 است.علامت گذاری.مشخصات ماتریس بالا مطابق با نمایش ناسینوف بازگشتی در سال 1978 می‌باشد . گاهی اوقات به ادبیات اخیر به عنوان یک تنوعی برای این الگوریتم ناسینوف بازگشتی اشاره شده‌است(z. B. Durbin, 2006). در مقالهٔ Durbin در سال 2006 بازگشت، 4 مورد متمایز است. این گوناگونی، مقادیر محاسبه شده توسط ماتریس formula_44 را تغییر نمی‌دهد، اما روش برگشت به عقب چندین مسیر مختلف در یک ساختار دوم ارائه می‌دهد که تمایز آن‌ها از نظر معنایی مبهم است.ارتباط بیولوژیکی.ساختار دومی که شامل ماکزیمم تعداد جفت بازهاست لزوماً آن ساختاری نیست که در طبیعت (در یک سلول) اتفاق بیفتد. بنابراین در عمل الگوریتم ناسینوف برای پیش گویی ساختار دوم توالی‌های RNA به کار برده نمی‌شود. در عمل ساختار دوم پیش گویی شده تحت یک مدل ترمودینامیکی (برای مثال الگوریتم زوکر Zuker Algorithm را ببینید)است که منجر به نتایج معنادار بیولوژیکی می‌شود.با این حال الگوریتم ناسینوف از نظر تئوری در آموزش و پژوهش مورد توجه و علاقه است.برای مثال الگوریتم روش برگشت به عقب واترمن بایرز، Waterman-Byers-backtracking برای پیدا کردن زیرساختارهای بهینه به کار برده شد تا یک مثال از ماتریس برگشتی معین را توصیف کند. مطالعه الگوریتم آموزنده است، چرا که ، مانند الگوریتم‌های دیگر پیش‌بینی ساختار RNA، از روش برنامه‌نویسی پویا استفاده می‌کند که دارای یک ماتریس بازگشتی است و به آسانی قابل درک است.