عنوان پایان‌نامه
یافتن SNP های شاخص با استفاده از الگوریتم جستجوی هارمونی
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 54840
- تاریخ دفاع
- ۲۹ شهریور ۱۳۹۱
- دانشجو
- فاطمه بهجتی اردکانی
- استاد راهنما
- محمد گنج تابش
- چکیده
- چندریختی‌های تک‌نوکلئوتیدی (SNPs) جز با ارزش‌ترین منابع تحقیق و بررسی در زمین? یافتن علت بیماری‌های ژنتیکی محسوب می‌شوند. برخی از این چندریختی‌های نوکلئوتیدی ممکن است زمینه را برای بروز بیماری‌هایی از قبیل دیابت، فشارخون و سرطان فراهم کنند و یا حتی در روند رشد بیماری تأثیرگذار باشند. ابزار بیوانفورماتیک نقش مهم و به سزایی در رابطه با کشف SNPها و تجزیه و تحلیل آن‌ها ایفا می‌کند. روش‌های محاسباتی گوناگونی در زمینه تعیین SNPها و پیش‌بینی اینکه آیا یک SNP عملکردی خنثی دارد یا مخرب ارائه شده است. متاسفانه حجم پایگاه داده‌ای SNPها بسیار عظیم و گسترده است، به همین دلیل محققین سعی بر یافتن زیرمجموعه‌ای از SNPها دارند به طوری که این زیرمجموعه بتواند به خوبی سایر SNPها را توصیف نماید. اصطلاحاً به SNPهای موجود در این زیرمجموعه، SNPهای شاخص گفته می‌شود. انتخاب زیرمجموعه تحت تأثیر فاکتورهای مختلفی می‌باشد. از این فاکتورها می‌توان به مواردی از قبیل تخمین اعتماد به SNP، فاکتورهای بیوشیمی، کارایی زیرمجموعه برای نگاشت کل ژن‌ها و تشخیص محل بروز بیماری اشاره کرد. به طورکلی یافتن چنین زیرمجموعه‌ای در زمان چندجمله‌ای امکان‌پذیر نیست و برای حل این مسأله محتاج بکارگیری روش‌های تقریبی هستیم. تاکنون روش‌های متعددی در زمین? یافتن SNPهای شاخص ارائه شده است ولی در این میان روش‌های تکاملی از برتری بیشتری نسبت به سایرین برخوردار بوده‌اند. علی‌الخصوص که الگوریتم‌های تکاملی، ابزاری کاملاً مناسب برای مسائل بهینه‌سازی چندهدفه که اغلب فضای جستجوی پیچیده‌ای را پوشش می‌دهند، محسوب می‌شوند. روش بکار گرفته شده در این پایان‌نامه الگوریتم تکاملی جستجوی هارمونی می‌باشد که نتایج بدست آمده از این روش با سایر روش‌های موجود مقایسه گردیده و در این پایان‌نامه فراهم آورده شده است. کلمات کلیدی: چندریختی تک‌نوکلئوتیدی، SNPهای شاخص، الگوریتم جستجوی هارمونی.
- Abstract
- Single nucleotide polymorphisms (SNPs) are valuable resources for investigating the genetic basis of diseases. These variants can serve as markers for genetic mapping experiments and genome-wide association studies. Certain of these nucleotide polymorphisms may predispose individuals to illnesses such as diabetes, hypertension, or cancer, or even affect disease progression. Bioinformatics techniques can play an important role in SNP discovery and analysis. Computational methods are used to identify SNPs and to predict whether they are likely to be neutral or deleterious. Due to the large databases of SNPs, typically the investigators must choose a subset of SNPs from these databases to employ in their studies. The choice of subset is influenced by many factors, including estimated reliability of the SNP, biochemical factors, effectiveness of the subset for mapping genes or identifying disease loci. Finding such subset of SNPs is impossible in polynomial time. Therefore, a heuristic approach is required to tackle this challenge. To date, various tagging SNP methods have been proposed but those following the evolutionary techniques are prevalent. Evolutionary algorithms are particularly suited for optimization problems that involve multi-objectives and a complex search space on which exact methods such as exhaustive enumeration cannot be applied. In this thesis, the evolutionary algorithm called Harmony Search algorithm, is employed to solve the tag SNPs selection problem and the obtained results are compared to some other extant methods. Keywords: single nucleotide polymorphism, tag SNPs, harmony search algorithm.
