الگوریتم زوکر
الگوریتم جستجوی زوکر Zuker-Algorithmus ساختار ساختار دوم بهینهٔ یک توالی RNAکه دارای کمترین مقدار انرژی است را تحت یک مدل ترمودینامیکی محاسبه می‌کند. بنابراین این الگوریتم یک الگوریتم پیش‌گویی ساختار دوم RNA است. الگوریتم روش برنامه نویسی پویا را به کار می‌برد و در سال ۱۹۸۱ چاپ شده‌است. برنامهٔ mfold پیش‌گویی ساختار RNA یک نسخهٔ اصلاح شده از این الگوریتم را پیاده‌سازی می‌کند.
یک توالی RNA داده شده می‌تواند در ترکیب‌های ممکن بسیاری از جفت بازها به هم پیچیده شود و ساختار تشکیل دهد که به تعداد نمایی می‌توان از این ساختارهای دوم مختلف داشت. هنگامی که ساختار پیش‌بینی می‌شود از طریق فضای جستجو توسط یک پارامتر خاص بهینه می‌شود. برای مثال ساختار با ماکزیمم تعداد جفت بازها انتخاب شده‌است. با این وجود این ساختار می‌تواند از نظر بیوشیمیایی و بیولوژیکی غیرواقعی باشد. چون برای مثال ساختار شامل یک حلقهٔ سنجاق سری (hairpinloop) با فقط یک باز جفت نشده‌است یا یک ساختاری است که از نظر انرژی بسیار ناپایدار است.
معیار معنی‌دار بودن بیولوژیکی در نظر گرفتن انرژی آزاد یک ساختار دوم است. انرژی آزاد یک ساختار کمتر از انرژی آزاد ساختار دیگری باشد، آن ساختار پایدارتر از دومی است. تحت شرایط آزمایشگاهی، می‌توان انرژی آزاد ساختارهای مختلف یک ساختار دوم RNA را اندازه‌گیری کرد. یک مثال از چنین جمع‌آوری داده‌ها ارائه شده‌است.مثلاً انرژی آزاد تشکیل پیوندهای بازی مختلف در یک جدول جمع‌آوری شده‌است. سپس با استفاده از این داده‌ها، می‌توان انرژی آزاد یک ساختار دوم RNA را از روی توالی RNA داده شده تقریب زد.
الگوریتم در حال حاضر برای یک توالی RNA، ساختار با حداقل انرژی آزاد را محاسبه می‌کند. ساختار دوم بهینه در این مدل از نظر کارشناسان (زیست شناسان، بیوشیمی دان‌ها) با ارزیابی بیولوژیکی واقع بینانه به دست می‌آید. توالی RNA با formula_1 نشان داده شده طوری‌که formula_2. مینیمم انرژی آزاد یک ساختار دوم بهینه به صورت بازگشتی برای همهٔ زیرتوالی‌های formula_1 محاسبه شده‌است. ماتریس formula_4 در درایه‌های formula_5 مقدار مینیم انرژی آزاد (mfe) را برای توای ناقص formula_6 از توالی s ذخیره می‌کند و ماتریس formula_7 مقدار mfe ساختار توالی جزئی (ناقص) formula_6 را در درایه‌های formula_9 ذخیره می‌کند در جایی که formula_10 و formula_11 یک جفت باز هستند(پیوند بازی دارند).
"مقداردهی اولیه:" formula_12
formula_13
مولکول‌های RNA کوتاه ساختار دوم پایداری تشکیل نمی‌دهند.
"رابطهٔ بازگشتی:"
W[i+1,j] \\ W[i,j-1] \\ \min_{i4, 0
تجزیه و تحلیل در نظر گرفته شده چهار مورد است: در مورد اول و دوم ساختار بهینهٔ formula_6 از توالی‌های ناقص formula_15 و formula_16 و یک باز جفت نشده باهم در سمت چپ و راست به دست می‌آید. در هر دو مورد mfe تغییر نخواهد کرد.
در مورد سوم ساختار بهینه برای formula_6 توسط ساختارهای بهینهٔ قسمت‌هایی از توالی که به هم متصل شده‌اند، به دست می‌آید. کمترین مقدار انرژی آزاد (mfe) مجموع mfeهای ساختارهای ناقص formula_18 یا formula_19 است.
چهارمین مورد mfe برای توالی جزئی formula_6 محاسبه شده درجایی که بازهایformula_10 و formula_11 نشان دهندهٔ جفت بازها هستند. اگر formula_10 و formula_11 نتوانند یک جفت باز تشکیل دهند سپس قرار می‌دهیم:
formula_25
در غیر این صورت formula_9 به صورت زیر محاسبه می‌شود:
formula_27 انرژی آزاد برای یک حلقهٔ سنجاق سری توالی جزئی (ناقص) formula_6 است. به عنوان مثال، مقادیر حلقه‌های با اندازهٔ مختلف و جفت بازها می‌توانند به‌طور تجربی تحت شرایط یکنواخت تعیین شوند، و در یک جدول کمکی ذخیره شوند. تابع formula_29 یک نماینده‌است و انرژی آزاد یک حلقهٔ داخلی (internal loop)، یک حلقهٔ بالج (bulge loop) یا یک ناحیهٔ استکی (stacking region)را می‌دهد که در آن دنبالهٔ جزئی formula_30 formula_31 دخالت دارند. در این مورد mfe مجموع mfe این ساختار و توالی ناقص formula_32 است, که باید با یک جفت باز محاط شود. مورد چهارم یک ساختار شاخه‌ای از ساختاری که به صورت بازگشتی ایجاد شده را مدل می‌کند.
"برگشت به عقب:" بعد از محاسبهٔ ماتریس بازگشتی، mfe برای توالی کامل RNA تحت یک ساختار دوم بهینه در درایهٔ formula_33 ذخیره شده‌است. برای تعیین ساختار دوم بهینه mfe بهینه باید از طریق روش برگشت به عقب به دست آید.
این دو جدول formula_4 و formula_7 مربعی هستند، بنابراین نیاز به حافظه formula_36 دارند. بهینه شدن تحت formula_36 تحلیل برای حلقه‌های درونی دو متغیر نیاز دارد که برای هر خانه در یک پیاده‌سازی معمولی نیاز است. از طریق یک پیش پردازش هوشمند، مقادیر حلقه‌های درونی قبل از محاسبه می‌تواند تعیین شود، همچنین این توزیع انرژی در زمان خطی انجام می‌شود. به‌طور دلخواه می‌توانید اندازهٔ حلقه‌ها را با یک مقدار ثابت محدود کنید، پس زمان اجرای الگوریتم formula_38 است.
حالت نمایش در هنگام به دست آوردن برگشتی formula_4 می‌تواند به صورت خلاصه و فشرده‌ای فرمول بندی شود طوری‌که ساختار دوم به صورت نقطه-پرانتز نمایش داده شود همان گونه که به‌طور مثال در Vienna-string به دست می‌آید. به این صورت که یک نقطه نمایش دهندهٔ یک باز جفت نشده یا تنها است و یک پرانتز باز و بسته نشان دهندهٔ یک پیوند بازی (یا یک جفت باز)به‌طوری‌که حالت نمایش بازگشت formula_4 به صورت زیر است:
formula_41
formula_42 کل ساختار دوم یک زیررشته نامیده می‌شود و formula_43 و formula_44 زیرساختارهای formula_42 نامیده می‌شوند.
این توضیحات معادل با نمودار زیر است:
الگوریتم برگشت به عقب می‌تواند به دلایل تفاوت موارد الگوریتم زوکر، چندین مسیر برگشتی مختلف برای نمایش یک ساختار دوم یکسان بدهد. حالت‌های تمایز و نمایش از نظر معنایی مبهم هستند. برای مثال یک بازگشت formula_4 از مورد 1 به مورد 2 در مورد 1،همان ساختاری را تولید می‌کند که بازگشت از مورد 1 به مورد 1 در مورد 2 تولید می‌کند. برای دیدن مثال دیگر این لینک را ببینید..
این ابهام در مورد مسئله پیدا کردن ساختار دوم بهینه مشکل ساز است. با این حال صرف گذراندن و شمارش همهٔ ساختارهای دوم مشابه از نظر بهینگی یا شمارش یا انتشار همه زیرساختارهای کمتر از حد مطلوب، الگوریتم برگشت به عقب حداقل فقط به سختی به صورت درست و کامل و کارا پیاده‌سازی می‌شود. در یک پیاده‌سازی استاندارد برگشت به عقب، ساختارهای برکنار شده در یک تعداد نمایی شمرده شده‌اند یا نمایش داده شده‌اند. این الگوریتم در مقایسه با الگوریتم ناسینوف یک جدول اضافی را به کار می برد. تا یک دنباله از بازهای جفت شده (یعنی یک ناحیهٔ stacking) بتواند به صورت متفاوتی ارزیابی شود.الگوی مشابهی نیز الگوریتم Gotohرا برای محاسبه فاصله دو هم ترازی دنباله برای گسترش گپ تکراری به کار می برد.
الگوریتم ناسینوف در سال 1987، ساختار دوم یک توالی از ورودی RNA که بیشترین تعداد جفت بازها را دارد را محاسبه کرد. چون این ساختارها از نظر بیولوژیکی لزوماً معنی دار نیستند، الگوریتم ناسینوف در عمل قابل اعمال نیست. در عمل الگوریتم‌هایی برای پیش‌گویی ساختار دوم RNA به کار برده می‌شوند که ساختاری با مینیمم مقدار انرژی آزاد را محاسبه می‌کنند یا ساختارهایی با کمترین انرژی آزاد که انرژی آنهااز یک آستانهٔ معینی بیشتر نیست را محاسبه می‌کنند. کاربرد الگوریتم mfold زوکر در پیاده‌سازی هنوز هم گسترش دارد. هر چند در حال حاضر نیز الگوریتم‌های پیش‌بینی ساختار دوم، که یک تحلیل موردی جزئی می سازند و تمایز موارد مبهم نیست. یک نمونه از چنین الگوریتم mfe بهبود یافته Wuchty98 algorithm است.