عنوان پایان‌نامه
پیش بینی ساختار دوم RNA با استفاده از الگوریتم های ژنتیک
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 48521
- تاریخ دفاع
- ۲۰ بهمن ۱۳۸۹
- دانشجو
- میلاد چناقلو
- استاد راهنما
- عباس نوذری دالینی, محمد گنج تابش
- چکیده
- در این پایان‌نامه مساله پیش‌بینی ساختار دوم RNA با استفاده از الگوریتم‌های ژنتیک مورد بررسی قرار گرفته و برای حل این مساله یک الگوریتم شبیه‌سازی گداخت[30] و یک الگوریتم ژنتیک [34] مورد مطالعه قرار گرفته و الگوریتم ژنتیک مورد اشاره بهبود بخشیده شده است. ابتدا روشی برای افزایش سرعت الگوریتم ژنتیک ارائه شده است. در این روش، به جای اینکه جمعیت اولیه به صورت تصادفی انتخاب شود، از یک الگوریتم ژنتیک اولیه برای تولید جمعیت اولیه الگوریتم ژنتیک اصلی استفاده شده است. این الگوریتم ژنتیک اولیه روی هلیکس‌های بهتر انجام می‌شود؛ یعنی روی هلیکس‌هایی که به احتمال بیشتر در ساختار دوم شرکت می‌کنند. سپس برای افزایش دقت الگوریتم ژنتیک، به جای هلیکس‌های ماکسیمال از هلیکس‌های غیرماکسیمال استفاده شده است و همچنین در الگوریتم ژنتیک، روی بخشی از اعضای هر نسل،از یک روش مکاشفه‌ای به نام هیل‌کلایمینگ برای دستیابی به ساختارهای با دقت بالاتر به صورت هدفمند استفاده شده است. در نهایت توانایی پیش‌بینی ساختارهای با پیوندهای متقاطع به الگوریتم اضافه شده است. در این روش، بهترین ساختاری که به دست آمده است را انتخاب کرده و نوکلئوتیدهایی که در پیوندها شرکت کرده‌اند حذف می‌شود. سپس کل هلیکس‌های رشته حاصل محاسبه شده و از یک الگوریتم ژنتیک برای تعیین یک ساختار با پیوندهای متقاطع استفاده شده است. کلمات کلیدی: پیش‌بینی ساختار دوم RNA، شبیه‌سازی گداخت، الگوریتم‌های ژنتیک.
- Abstract
- In this thesis a simulated annealing algorithm [30] and a genetic algorithm [34] is proposed and the genetic algorithm has been optimized. First, a method is presented to speed up the convergence of the genetic algorithm. In this method, instead of creating the initial population randomly, an initial genetic algorithm is used to create the initial population of the main genetic algorithm. The initial genetic algorithm uses the better helices, helices that participate in the secondary structure with more probability. Then, in order to get higher accuracy, instead of using maximal helices, nonMaximal helices are used and in the genetic algorithm, a heuristic method called Hill Climbing is used to get higher accuracy in a targeted manner in a portion of the population. At last the ability to predict structure with pseudoknots has been added to the algorithm. The best found structure is selected and the nucleotides participating in the secondary structure are removed from the sequence. Then all helices of the remaining sequence is computed and a genetic algorithm is used to predict a structure with pseudoknots. Keywords: RNA secondary structure prediction, Simulated Annealing, Genetic Algorithm
