عنوان پایان‌نامه
الگوریتم موازی برای تشخیص رشته های تکراری
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 3915;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 43015
- تاریخ دفاع
- ۲۹ بهمن ۱۳۸۷
- استاد راهنما
- هایده اهرابیان, عباس نوذری دالینی
- دانشجو
- میثم باستانی
- چکیده
- یکی از مهمترین منابع برای به دست آوردن اطلاعات مربوط به بیان شدن ژنها در یک سلول یا گروهی از سلولها، برچسبهای توالی بیان شده (Expressed Sequence Tags) یا ESTها و همین طور رشته های مکمل دی ان ای (complementary DNA) یا cDNAها هستند. یکی از مسائل مهم در این زمینه بررسی ESTها بر طرف کردن مشکلاتی است که در اثر حضور تکرارها در دنباله های EST ایجاد میشود. برای بر طرف کردن این مشکلات دو راه حل وجود دارد. راه حل اول، تشخیص و حذف دنباله های تکرار با استفاده از روشهای مبتنی بر اطلاعات کتابخانه ای از تکرارها می باشد که توسط زیست شناسان در آزمایشگاه ها به دست آمده و شامل انواع تکرارهای موجودات مختلف است. راه حل دوم، استفاده از روشهایی است که بدون نیاز به کتابخانهها، دنباله های تکرار را تشخیص داده و حذف میکنند. در این پایان نامه، برای اولین بار الگوریتمی موازی برای تکراریابی این رشته ها بدون استفاده از کتابخانه های تکرار ارائه شده است. این روش بر اساس بررسی آماری رشته های EST کار میکند. بررسی های وسیع و جامع صورت گرفته بر روی این روش با استفاده از مجموعه داده های بسیار حجیمی از ESTها (از آن جمله میتوان به 800000 EST متعلق به گیاه آرابیدوپسیس تالیانا اشاره کرد) نشان میدهد که این روش نه تنها کارایی مناسبی برای داده های حجیم دارد بلکه نتایج به دست آمده از این الگوریتم در مقایسه با نتایج به دست آمده از برنامه های همتای آن از دقتی مشابه و دربرخی موارد حتی بالاتر برخوردار است. کلیده واژه ها: الگوریتمها موازی، درخت پسوندی، درخت پسونی عمومی، تکرار یابی، EST
- Abstract
- Expressed sequence tag (EST) and complementary DNA (cDNA) sequences are currently the most important resources for transcriptome exploration of an organism. An important step in the EST analysis is to overcome the problems caused by the presence of repeats in these sequences. These errors particularly occur in the EST clustering where they can cause false matches. To avoid these problems ESTs are masked either against a known library of repeats or using a library-less method. In this dissertation we present a new parallel library-less algorithm for masking repeats in EST sequences, based on statistical analysis of match distribution within the EST collection. Extensive testing on data sets such as 800,000 ESTs of Arabidopsis thaliana shows that this method is not only practical on huge data sets but it also produces results that are better than, or at least as accurate as, the results obtained by other available methods.
