عنوان پایان‌نامه
بررسی خواص ترکیبیاتی ساختار های دوم دوبخشی RNA
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 4949;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 57302
- تاریخ دفاع
- ۲۳ بهمن ۱۳۹۱
- دانشجو
- علیرضا شفیعی فرد
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- ساختارهای دوم اسیدهای نوکلوئوتید کلاس خاصی از ساختارهای وقوع هستند. اهمیت زیاد مولکولهای RNA بدلیل شبه گره‌ها و ویژگیهای ساختاری است که با تعریف قدیمی ساختارهای دوم که فاقد شبه گره هستند، متفاوت است.در اینجا ساختارهای دوم عمومی را با شبه گره های غیر متداخل یکی می‌گیریم که به آن ساختارهای دوم-دوبخشی می‌گوییم. ساختارهای دوم دوبخشی، گراف های مسطح هستند که یک کران بالا برای تعداد آنها(به‌صورت تابعی از n ) بدست می آوریم. نتایج نشان می‌دهند که تعداد ساختارهای دوم-دوبخشی بطور تقریبی رشدی برابر با ?2.35?^n دارد. در این پایان‌نامه با کمک یک الگوریتم بازگشت به عقب توانستیم تعداد دقیق این ساختارها را بصورت دنباله هایی به طول n بدست آوریم (ازطریق تبدیل آنها به () و []). همچنین با ایجاد مفهومی به نام مکان یک الگوریتم برای کران پایین و بالا در این ساختارها ایجاد گردید.
- Abstract
- of contact structures. Many important RNA molecules, however, contain pseudo-knots, a structural feature that is excluded explicitly from the conventional definition of secondary structures. We propose here a generalization of secondary structures incorporating ‘non-nested’ pseudo-knots, which we call bi-secondary structures, and discuss measures for the complexity of more general contact structures based on their graph-theoretical properties. At present time, bi-secondary structures are still a combinatorial mystery: no generating function is known (ever found). Bi-secondary structures are planar trivalent graphs that are characterized by special embedding properties. We derive exact upper bounds on their number (as a function of the chain length n) implying that there are fewer different structures than sequences. Computational results show that the number of bi-secondary structures grows approximately like ?2.35?^n . Numerical studies based on kinetic folding and a simple extension of the standard energy model show that the global features of the sequence-structure map of RNA do not change when pseudo-knots are introduced into the secondary structure picture. In this thesis, we developed a backtracking algorithm to generate all bi-secondary RNA structures. Afterwards, we defined a new concept called “location” and through this definition we were able to place an upper bound on enumerating structures
