عنوان پایان‌نامه
استخراج بزرگترین زیر ساختار مشترک در چندین ساختار دوم RNA با دیدگاه کشف کلیک
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 35.;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 55005
- تاریخ دفاع
- ۱۳ شهریور ۱۳۹۱
- دانشجو
- مینا اخوان
- استاد راهنما
- علی معینی
- چکیده
- در این پژوهش، مسئله ی پیدا کردن بزرگترین زیرساختار مشترک در چندین ساختار دوم RNA با دیدگاه جدیدی مورد بررسی قرار گرفته است و الگوریتمی بر مبنای خوشه بندی برای این مسئله ارائه گردیده است. مطالعات اخیر نشان داده است که RNA در سیستم بیولوژیکی گستره ی وسیعی از عملکردها را بر عهده دارد و بنابراین مقایسه ی شباهت ساختارهای دوم آن امری چالش انگیز در زیست مولکولی می باشد، چرا که ساختارهای مشابه اغلب بر رفتارهای مشابه دلالت دارند. در سال های اخیر بیشتر ابزارهای موجود ساختار دوم را بوسیله ی نمایش درختی ارائه می دهند و سپس شباهت را بوسیله ی الگوریتم های Tree Alignment Distance محاسبه می کنند، اما در این رساله مسئله ی پیدا کردن بزرگترین زیر ساختار مشترک در RNA ها را، به مسئله ی کشف بزرگترین کلیک کاهش می دهیم. بدیهی است به جهت کاهش این مسئله ناچاریم گراف ها ی اولیه ای که معرف ساختارهای دوم RNA هستند به ساختار داده ای جدیدی تبدیل کنیم که مسئله ی کلیک به آن قابل اعمال گردد. پس از پیاده سازی و بررسی نتایج الگوریتم Exact مشخص گردید زمانی که تعداد ساختارهای RNA های ورودی افزایش می یابد، مسئله به دلیل بالا بودن زمان اجرا غیر کارا می گردد . برای حل این مشکل در الگوریتم جدید از راه حل خوشه بندی استفاده می نماییم که الگوریتم خوشه بندی مورد استفاده در این رساله UPGMA می باشد. یکی از بخش های پر اهمیت در این الگوریتم این است که پس از پیدا کردن بزرگترین کلیک در ساختار داده ای جدید، بتوانیم به سمت ساختارهای اولیه عقبگرد نماییم و ناحیه های مشترک در هر ساختار RNA را با توجه به کلیک بدست آمده، مشخص نماییم.
- Abstract
- In this thesis maximum common substructure extraction problem in multiple RNA secondary structures has been investigated with a new approach and an algorithm based clustering has been presented for this problem. It has been realized that RNA performs a wide range of functions in biological system and therefore comparing the similarities of RNA secondary structures is one of the challenging tasks in molecular biology as similar structures often imply similar functions. In recent years, most existing tools represent the secondary structures by tree-based presentation and calculate the similarity by tree alignment distance. In this thesis maximum common substructure extraction problem has been reduced to maximum clique detection problem. Clearly for this reducing, it’s essential that primary graphs that represent RNA secondary structures convert to new data structures that clique problem is applicable for them. After implementation and result analysis has been proved when we increase the number of RNA secondary structures in the exact algorithm due to the high runtime, algorithm was impractical. For solving this problem in new algorithm we use clustering solutions. The clustering algorithm that has been used in my thesis is UPGMA. One of the most important sections in this algorithm is that we must can rollback to primary structures after finding maximum clique in new data structure. It means that with regarding current clique we can specify common substructures in RNA secondary structures.
