عنوان پایان‌نامه
تخمین ساختار دوم RNA ها به منظور تسهیل برهم کنش های مختلف با استفاده از رویکردهای موازی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 91..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75413;کتابخانه پردیس یک فنی شماره ثبت: 91..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75413
- تاریخ دفاع
- ۱۰ شهریور ۱۳۹۳
- دانشجو
- پونیا طاهری مخصوص
- استاد راهنما
- علی معینی
- چکیده
- از زمان ورود بشر به حوزه ژن شناسی، شناخت عملکرد بیولوژیک بیومولکول ها یکی از مهم ترین موضوعات در این حوزه بوده است. از آنجا که RNA یکی از مولکول های اساسی در سیستم بیولوژی است، فهم و درک چگونگی عملکرد توابع آن یک موضوع کلیدی در شناخت و استنتاج عملکردش به حساب می آید. توابع بیولوژیک RNA بوسیله بررسی ساختارهای دوم و سوم آن تخمین زده می شوند. در این میان، روش های تجربی برای تخمین ساختارهای دوم و سوم بسیار پرهزینه، پیچیده و مستعد خطا هستند. این موضوع استفاده از چنین روش هایی را در عمل با مشکل مواجه می سازد. از آنجا که میزان زیادی از اطلاعات ترتیب¬های RNA موجود و قابل دسترس است، امروزه روش هایی که از مدل سازی ها و شبیه سازی های ریاضی و الگوریتمیک برای پیش بینی این ساختارها استفاده می کنند، به طور گسترده مورد استفاده قرار می گیرند. بر اساس این واقعیت که نیروی انباشته پایه در مولکول RNA یکی از نیروهای اساسی در پایدارسازی ساختار دوم مولکول است، پیش بینی ساختار دوم می تواند به یک مساله بهینه سازی ترکیبی که بر مبنای ترکیب نواحی استم و دنبال کردن حداقل انرژی آزاد استوار است، تبدیل گردد. از طرف دیگر، هوش محاسباتی یکی از ساخته های مهم هوش مصنوعی است که در حل بسیاری از مسائل به کار گرفته شده است. بسیاری از روش های هوش محاسباتی از قبیل الگوریتم ژنتیک، بازپخت شبیه سازی شده و تنوعی از الگوریتم های هوش گروهی نظیر بهینه سازی گروهی ذرات، برای مساله پیش بینی ساختار دوم نیز به طور موفقیت آمیزی به کار گرفته شده اند. علی الخصوص، الگوریتم های هوش گروهی که کارایی خوبی در مسائل بهینه سازی ترکیبی دارند، نتایج قابل توجهی در این حوزه داشته اند. توسعه های زیادی بر الگوریتم بهینه سازی ذرات گروهی پیشنهاد شده است و در این پژوهش نیز از آن ها برای مساله پیشگویی ساختار دوم استفاده شده است که علاوه بر بهبود دقت پیشگویی، مدل موازی پیشنهاد شده ای از آن به میزان قابل توجهی موجب تسریع فرآیند پیشگویی می گردد. به طور کلی نوآوری این پژوهش در دو بخش قابل بیان است: بخش اول، بکارگیری توسعه جدیدی از روش بهینه سازی ذرات گروهی می باشد که برای اولین بار در این حوزه مورد استفاده قرار می گیرد. این روش علاوه بر آنکه به دلیل جستجوی محلی نسبت به روش کلاسیک PSO، موجب دقت پیشگویی می گردد به گونه ای است که وابستگی داده ای کمتری ایجاد نموده و امکان اجرای موازی آن بالاتر است. بخش دوم نوآوری در این پژوهش، ارائه الگوریتم موازی توسعه مورد استفاده و پیاده سازی آن با استفاده از فرآیند OPENMP است. ارزیابی روش پیشنهادی و مقایسه آن با برخی روش های مشابه و مطرح در این حوزه با استخراج نتایج حاصل از آزمایش بر روی دنباله های با طول های متفاوت، نشان از برتری روش پیشنهادی در افزایش سرعت اجرای فرآیند پیش بینی دنبالاه های با طول بیشتر از 1000 دارد.
- Abstract
- Abstract Ever since human’s entry to the field of Genomics, recognition of biologic performance of biomolecules has been one of the most important issues in this field. Since RNA in one of the basic molecules in biology, understanding of how its functions perform has been considered the key topic in recognition and deduction of its performance. Biologic functions of RNA are estimated by investigation of secondary and tertiary structures. Meanwhile, experimental methods for estimation of secondary and tertiary structures are costly, susceptible to error and complex. This makes it difficult to use these methods in practice. Since a lot of sequences of RNA are available and based on that, methods that use modeling and algorithmic simulations to prediction of secondary and tertiary structure of RNA molecule have been applied widely. Free energy base in RNA molecule is one of the basic forces in stability of secondary structure of the molecule and anticipation the secondary structure can be a combinatorial optimization which is based on following the minimum free energy. On the other hand, computational intelligence in one of the important built-in artificial intelligence approaches, which is applied in resolving the problems. Most of the methods of computational intelligence such as genetic algorithm, simulated annealing and a wide variety of swarm intelligence algorithms such as particle swarm optimization, have been used successfully for RNA secondary structure prediction. Especially, such swarm intelligence algorithms with suitable performance in combinatorial optimization algorithms, had impressive results in this field. Many extensions have been proposed for the PSO improvement. In this research a modification of PSO has been proposed, too. This proposed method, increases the accuracy of RNA secondary structure prediction and also a parallel implementation of the method, can significantly speed up the prediction process. In general, innovation in this research is expressed in two parts: the first part, applying a new modification of PSO which were used in this area for the first time. This method, in addition to the local search compared to classical PSO caused the predictive accuracy, is causing less dependence and higher ability to run in parallel. The second innovation in this study is to present applied developing parallel algorithm and implementation of that using the OPENMP API. The proposed method is evaluated in comparison with some other methods. The results of tests on the sequence of different lengths showed that the proposed method of accelerating the implementation process can predict sequences with the length more than 1000.
