الگوریتم زوکر

الگوریتم جستجوی زوکر Zuker-Algorithmus ساختار ساختار دوم بهینهٔ یک توالی RNAکه دارای کمترین مقدار انرژی است را تحت یک مدل ترمودینامیکی محاسبه می‌کند. بنابراین این الگوریتم یک الگوریتم پیش‌گویی ساختار دوم RNA است. الگوریتم روش برنامه نویسی پویا را به کار می‌برد و در سال ۱۹۸۱ چاپ شده‌است. برنامهٔ mfold پیش‌گویی ساختار RNA یک نسخهٔ اصلاح شده از این الگوریتم را پیاده‌سازی می‌کند.

ایده

ساختار دوم برگ شبدر مانند، اجماعی (consensus) از توالی یک عنصر CIS از خانوادهٔ enterovirus

یک توالی RNA داده شده می‌تواند در ترکیب‌های ممکن بسیاری از جفت بازها به هم پیچیده شود و ساختار تشکیل دهد که به تعداد نمایی می‌توان از این ساختارهای دوم مختلف داشت. هنگامی که ساختار پیش‌بینی می‌شود از طریق فضای جستجو توسط یک پارامتر خاص بهینه می‌شود. برای مثال ساختار با ماکزیمم تعداد جفت بازها انتخاب شده‌است. با این وجود این ساختار می‌تواند از نظر بیوشیمیایی و بیولوژیکی غیرواقعی باشد. چون برای مثال ساختار شامل یک حلقهٔ سنجاق سری (hairpinloop) با فقط یک باز جفت نشده‌است یا یک ساختاری است که از نظر انرژی بسیار ناپایدار است.

معیار معنی‌دار بودن بیولوژیکی در نظر گرفتن انرژی آزاد یک ساختار دوم است. انرژی آزاد یک ساختار کمتر از انرژی آزاد ساختار دیگری باشد، آن ساختار پایدارتر از دومی است. تحت شرایط آزمایشگاهی، می‌توان انرژی آزاد ساختارهای مختلف یک ساختار دوم RNA را اندازه‌گیری کرد. یک مثال از چنین جمع‌آوری داده‌ها ارائه شده‌است.مثلاً انرژی آزاد تشکیل پیوندهای بازی مختلف در یک جدول جمع‌آوری شده‌است. سپس با استفاده از این داده‌ها، می‌توان انرژی آزاد یک ساختار دوم RNA را از روی توالی RNA داده شده تقریب زد.

الگوریتم در حال حاضر برای یک توالی RNA، ساختار با حداقل انرژی آزاد را محاسبه می‌کند. ساختار دوم بهینه در این مدل از نظر کارشناسان (زیست شناسان، بیوشیمی دان‌ها) با ارزیابی بیولوژیکی واقع بینانه به دست می‌آید.

الگوریتم

توالی RNA با $s$ نشان داده شده طوری‌که $n=|s|$. مینیمم انرژی آزاد یک ساختار دوم بهینه به صورت بازگشتی برای همهٔ زیرتوالی‌های $s$ محاسبه شده‌است. ماتریس $W$ در درایه‌های $W[i,j]$ مقدار مینیم انرژی آزاد (mfe) را برای توای ناقص $s[i..j]$ از توالی s ذخیره می‌کند و ماتریس $V$ مقدار mfe ساختار توالی جزئی (ناقص) $s[i..j]$ را در درایه‌های $V[i,j]$ ذخیره می‌کند در جایی که $s[i]$ و $s[j]$ یک جفت باز هستند(پیوند بازی دارند).

مقداردهی اولیه: $W[i,j]=0,j-i=4$

$V[i,j]=8.4kcal/mol,j-i=4$

مولکول‌های RNA کوتاه ساختار دوم پایداری تشکیل نمی‌دهند.

رابطهٔ بازگشتی:

$W[i,j]=\min {\begin{Bmatrix}W[i+1,j]\\W[i,j-1]\\\min _{i<k<j-1}\{W[i,k]+W[k+1,j]\}\\V[i,j]\end{Bmatrix}},i<j,j-i>4,0<i<n,0<j<n$

تجزیه و تحلیل در نظر گرفته شده چهار مورد است: در مورد اول و دوم ساختار بهینهٔ $s[i..j]$ از توالی‌های ناقص $s[i+1,j]$ و $s[i,j-1]$ و یک باز جفت نشده باهم در سمت چپ و راست به دست می‌آید. در هر دو مورد mfe تغییر نخواهد کرد.

در مورد سوم ساختار بهینه برای $s[i..j]$ توسط ساختارهای بهینهٔ قسمت‌هایی از توالی که به هم متصل شده‌اند، به دست می‌آید. کمترین مقدار انرژی آزاد (mfe) مجموع mfeهای ساختارهای ناقص $s[i,k]$ یا $s[k+1,j]$ است.

چهارمین مورد mfe برای توالی جزئی $s[i..j]$ محاسبه شده درجایی که بازهای$s[i]$ و $s[j]$ نشان دهندهٔ جفت بازها هستند. اگر $s[i]$ و $s[j]$ نتوانند یک جفت باز تشکیل دهند سپس قرار می‌دهیم:

$V[i,j]=\inf$

در غیر این صورت $V[i,j]$ به صورت زیر محاسبه می‌شود:

$V[i,j]=\min {\begin{Bmatrix}fh(i,j)\\\min _{i<a<b<j}\{fl(i,j,a,b)+V(a,b)\}\\\min _{i+1<k<j-2}\{W(i+1,k)+W(k+1,j-1)\}\end{Bmatrix}},i<j,j-i>4,0<i<n,0<j<n$

تابع $fh$ انرژی آزاد برای یک حلقهٔ سنجاق سری توالی جزئی (ناقص) $s[i..j]$ است. به عنوان مثال، مقادیر حلقه‌های با اندازهٔ مختلف و جفت بازها می‌توانند به‌طور تجربی تحت شرایط یکنواخت تعیین شوند، و در یک جدول کمکی ذخیره شوند. تابع $fl$ یک نماینده‌است و انرژی آزاد یک حلقهٔ داخلی (internal loop)، یک حلقهٔ بالج (bulge loop) یا یک ناحیهٔ استکی (stacking region)را می‌دهد که در آن دنبالهٔ جزئی $s[i..a]$ $s[b..j]$ دخالت دارند. در این مورد mfe مجموع mfe این ساختار و توالی ناقص $s[a,b]$ است, که باید با یک جفت باز محاط شود. مورد چهارم یک ساختار شاخه‌ای از ساختاری که به صورت بازگشتی ایجاد شده را مدل می‌کند.

برگشت به عقب: بعد از محاسبهٔ ماتریس بازگشتی، mfe برای توالی کامل RNA تحت یک ساختار دوم بهینه در درایهٔ $W[0,n-1]$ ذخیره شده‌است. برای تعیین ساختار دوم بهینه mfe بهینه باید از طریق روش برگشت به عقب به دست آید.

پیچیدگی

این دو جدول $W$ و $V$ مربعی هستند، بنابراین نیاز به حافظه $O(n^{2})$ دارند. بهینه شدن تحت $O(n^{2})$ تحلیل برای حلقه‌های درونی دو متغیر نیاز دارد که برای هر خانه در یک پیاده‌سازی معمولی نیاز است. از طریق یک پیش پردازش هوشمند، مقادیر حلقه‌های درونی قبل از محاسبه می‌تواند تعیین شود، همچنین این توزیع انرژی در زمان خطی انجام می‌شود. به‌طور دلخواه می‌توانید اندازهٔ حلقه‌ها را با یک مقدار ثابت محدود کنید، پس زمان اجرای الگوریتم $O(n^{3})$ است.

حالت نمایش

حالت نمایش در هنگام به دست آوردن برگشتی $W$ می‌تواند به صورت خلاصه و فشرده‌ای فرمول بندی شود طوری‌که ساختار دوم به صورت نقطه-پرانتز نمایش داده شود همان گونه که به‌طور مثال در Vienna-string به دست می‌آید. به این صورت که یک نقطه نمایش دهندهٔ یک باز جفت نشده یا تنها است و یک پرانتز باز و بسته نشان دهندهٔ یک پیوند بازی (یا یک جفت باز)به‌طوری‌که حالت نمایش بازگشت $W$ به صورت زیر است:

$u=v.|.v|(v)|vw$

$u$ کل ساختار دوم یک زیررشته نامیده می‌شود و $v$ و $w$ زیرساختارهای $u$ نامیده می‌شوند.

این توضیحات معادل با نمودار زیر است:

• 
  i , j پیوند بازی دارند
• 
  منشعب

برگشت به عقب

الگوریتم برگشت به عقب می‌تواند به دلایل تفاوت موارد الگوریتم زوکر، چندین مسیر برگشتی مختلف برای نمایش یک ساختار دوم یکسان بدهد. حالت‌های تمایز و نمایش از نظر معنایی مبهم هستند. برای مثال یک بازگشت $W$ از مورد 1 به مورد 2 در مورد 1،همان ساختاری را تولید می‌کند که بازگشت از مورد 1 به مورد 1 در مورد 2 تولید می‌کند. برای دیدن مثال دیگر این لینک را ببینید..

این ابهام در مورد مسئله پیدا کردن ساختار دوم بهینه مشکل ساز است. با این حال صرف گذراندن و شمارش همهٔ ساختارهای دوم مشابه از نظر بهینگی یا شمارش یا انتشار همه زیرساختارهای کمتر از حد مطلوب، الگوریتم برگشت به عقب حداقل فقط به سختی به صورت درست و کامل و کارا پیاده‌سازی می‌شود. در یک پیاده‌سازی استاندارد برگشت به عقب، ساختارهای برکنار شده در یک تعداد نمایی شمرده شده‌اند یا نمایش داده شده‌اند.

علامت‌گذاری

این الگوریتم در مقایسه با الگوریتم ناسینوف یک جدول اضافی را به کار می برد. تا یک دنباله از بازهای جفت شده (یعنی یک ناحیهٔ stacking) بتواند به صورت متفاوتی ارزیابی شود.الگوی مشابهی نیز الگوریتم Gotohرا برای محاسبه فاصله دو هم ترازی دنباله برای گسترش گپ تکراری به کار می برد.

الگوریتم ناسینوف در سال 1987، ساختار دوم یک توالی از ورودی RNA که بیشترین تعداد جفت بازها را دارد را محاسبه کرد. چون این ساختارها از نظر بیولوژیکی لزوماً معنی دار نیستند، الگوریتم ناسینوف در عمل قابل اعمال نیست. در عمل الگوریتم‌هایی برای پیش‌گویی ساختار دوم RNA به کار برده می‌شوند که ساختاری با مینیمم مقدار انرژی آزاد را محاسبه می‌کنند یا ساختارهایی با کمترین انرژی آزاد که انرژی آنهااز یک آستانهٔ معینی بیشتر نیست را محاسبه می‌کنند. کاربرد الگوریتم mfold زوکر در پیاده‌سازی هنوز هم گسترش دارد. هر چند در حال حاضر نیز الگوریتم‌های پیش‌بینی ساختار دوم، که یک تحلیل موردی جزئی می سازند و تمایز موارد مبهم نیست. یک نمونه از چنین الگوریتم mfe بهبود یافته Wuchty98 algorithm است.