موضوع مقاله: الگوریتم زوکر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم زوکر | مقدمه: هنگامی که ساختار پیش‌بینی می‌شود از طریق فضای جستجو توسط یک پارامتر خاص بهینه می‌شود. | ## بخش 1: الگوریتم زوکر | چون برای مثال ساختار شامل یک حلقهٔ سنجاق سری (hairpinloop) با فقط یک باز جفت نشده‌است یا یک ساختاری است که از نظر انرژی بسیار ناپایدار است. انرژی آزاد یک ساختار کمتر از انرژی آزاد ساختار دیگری باشد، آن ساختار پایدارتر از دومی است. تحت شرایط آزمایشگاهی، می‌توان انرژی آزاد ساختارهای مختلف یک ساختار دوم RNA را اندازه‌گیری کرد. یک مثال از چنین جمع‌آوری داده‌ها ارائه شده‌است.مثلاً انرژی آزاد تشکیل پیوندهای بازی مختلف در یک جدول جمع‌آوری شده‌است. سپس با استفاده از این داده‌ها، می‌توان انرژی آزاد یک ساختار دوم RNA را از روی توالی RNA داده شده تقریب زد. الگوریتم در حال حاضر برای یک توالی RNA، ساختار با حداقل انرژی آزاد را محاسبه می‌کند. ساختار دوم بهینه در این مدل از نظر کارشناسان (زیست شناسان، بیوشیمی دان‌ها) با ارزیابی بیولوژیکی واقع بینانه به دست می‌آید. مینیمم انرژی آزاد یک ساختار دوم بهینه به صورت بازگشتی برای همهٔ زیرتوالی‌های محاسبه شده‌است. ماتریس در درایه‌های مقدار مینیم انرژی آزاد (mfe) را برای توای ناقص از توالی s ذخیره می‌کند و ماتریس مقدار mfe ساختار توالی جزئی (ناقص) را در درایه‌های ذخیره می‌کند در جایی که و یک جفت باز هستند(پیوند بازی دارند). رابطهٔ بازگشتی: تجزیه و تحلیل در نظر گرفته شده چهار مورد است: در مورد اول و دوم ساختار بهینهٔ از توالی‌های ناقص و و یک باز جفت نشده باهم در سمت چپ و راست به دست می‌آید. در مورد سوم ساختار بهینه برای توسط ساختارهای بهینهٔ قسمت‌هایی از توالی که به هم متصل شده‌اند، به دست می‌آید. | ## بخش 2: الگوریتم زوکر | چهارمین مورد mfe برای توالی جزئی محاسبه شده درجایی که بازهای و نشان دهندهٔ جفت بازها هستند. اگر و نتوانند یک جفت باز تشکیل دهند سپس قرار می‌دهیم: در غیر این صورت به صورت زیر محاسبه می‌شود: تابع انرژی آزاد برای یک حلقهٔ سنجاق سری توالی جزئی (ناقص) است. به عنوان مثال، مقادیر حلقه‌های با اندازهٔ مختلف و جفت بازها می‌توانند به‌طور تجربی تحت شرایط یکنواخت تعیین شوند، و در یک جدول کمکی ذخیره شوند. در این مورد mfe مجموع mfe این ساختار و توالی ناقص است, که باید با یک جفت باز محاط شود. مورد چهارم یک ساختار شاخه‌ای از ساختاری که به صورت بازگشتی ایجاد شده را مدل می‌کند. برگشت به عقب: بعد از محاسبهٔ ماتریس بازگشتی، mfe برای توالی کامل RNA تحت یک ساختار دوم بهینه در درایهٔ ذخیره شده‌است. بهینه شدن تحت تحلیل برای حلقه‌های درونی دو متغیر نیاز دارد که برای هر خانه در یک پیاده‌سازی معمولی نیاز است. از طریق یک پیش پردازش هوشمند، مقادیر حلقه‌های درونی قبل از محاسبه می‌تواند تعیین شود، همچنین این توزیع انرژی در زمان خطی انجام می‌شود. به‌طور دلخواه می‌توانید اندازهٔ حلقه‌ها را با یک مقدار ثابت محدود کنید، پس زمان اجرای الگوریتم است. حالت نمایش حالت نمایش در هنگام به دست آوردن برگشتی می‌تواند به صورت خلاصه و فشرده‌ای فرمول بندی شود طوری‌که ساختار دوم به صورت نقطه-پرانتز نمایش داده شود همان گونه که به‌طور مثال در Vienna-string به دست می‌آید. به این صورت که یک نقطه نمایش دهندهٔ یک باز جفت نشده یا تنها است و یک پرانتز باز و بسته نشان دهندهٔ یک پیوند بازی (یا یک جفت باز)به‌طوری‌که حالت نمایش بازگشت به صورت زیر است: کل ساختار دوم یک زیررشته نامیده می‌شود و و زیرساختارهای نامیده می‌شوند. | ## بخش 3: الگوریتم زوکر | این توضیحات معادل با نمودار زیر است: برگشت به عقب الگوریتم برگشت به عقب می‌تواند به دلایل تفاوت موارد الگوریتم زوکر، چندین مسیر برگشتی مختلف برای نمایش یک ساختار دوم یکسان بدهد. برای مثال یک بازگشت از مورد 1 به مورد 2 در مورد 1،همان ساختاری را تولید می‌کند که بازگشت از مورد 1 به مورد 1 در مورد 2 تولید می‌کند. با این حال صرف گذراندن و شمارش همهٔ ساختارهای دوم مشابه از نظر بهینگی یا شمارش یا انتشار همه زیرساختارهای کمتر از حد مطلوب، الگوریتم برگشت به عقب حداقل فقط به سختی به صورت درست و کامل و کارا پیاده‌سازی می‌شود. در یک پیاده‌سازی استاندارد برگشت به عقب، ساختارهای برکنار شده در یک تعداد نمایی شمرده شده‌اند یا نمایش داده شده‌اند. علامت‌گذاری این الگوریتم در مقایسه با الگوریتم ناسینوف یک جدول اضافی را به کار می برد. تا یک دنباله از بازهای جفت شده (یعنی یک ناحیهٔ stacking) بتواند به صورت متفاوتی ارزیابی شود.الگوی مشابهی نیز الگوریتم Gotohرا برای محاسبه فاصله دو هم ترازی دنباله برای گسترش گپ تکراری به کار می برد. الگوریتم ناسینوف در سال 1987، ساختار دوم یک توالی از ورودی RNA که بیشترین تعداد جفت بازها را دارد را محاسبه کرد. چون این ساختارها از نظر بیولوژیکی لزوماً معنی دار نیستند، الگوریتم ناسینوف در عمل قابل اعمال نیست. در عمل الگوریتم‌هایی برای پیش‌گویی ساختار دوم RNA به کار برده می‌شوند که ساختاری با مینیمم مقدار انرژی آزاد را محاسبه می‌کنند یا ساختارهایی با کمترین انرژی آزاد که انرژی آنهااز یک آستانهٔ معینی بیشتر نیست را محاسبه می‌کنند. | ## جمع‌بندی | هر چند در حال حاضر نیز الگوریتم‌های پیش‌بینی ساختار دوم، که یک تحلیل موردی جزئی می سازند و تمایز موارد مبهم نیست.