پديد آورنده :
خدادادي، ايلناز
عنوان :
ارائه ي الگوريتم مبتني بر Max-SAT وزن دار، مدل مبتني بر محتمل ترين و روش ارزيابي جديد براي مساله ي بازسازي هاپلوتيپ هاي يك فرد
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
هوش مصنوعي
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر
صفحه شمار :
نه،70ص.: مصور،جدول،نمودار
يادداشت :
ص.ع.به فارسي و انگليسي
استاد راهنما :
رسول موسوي
استاد مشاور :
ناصر قديري مدرس
توصيفگر ها :
اسنيپ , ارضاء پذيري
تاريخ نمايه سازي :
13/2/93
دانشكده :
مهندسي برق و كامپيوتر
چكيده فارسي :
چكيده ژنوم نسانها در مكانهاي مشخصي با يكديگر تفاوت د رند چندريختي تكنوكلئوتيدي يا بـه ختصـار سـنيپ متـد ولتـرين نـوع يـن تفاوتهاست سنيپها نقش مهمي در كاربردهاي وسيعي مانند تشخيص پزشكي و طر حي د رو يفا ميكنند و علاوه بر آن مكان رديـابي ژنهاي بيماري ر فر هم ميآورند در موجود ت ديپلوئيدي مانند نسان دو كپي ز هر كروموزوم وجود د رد يكـي ز مـادر و ديگـري ز پدر به رث ميرسد تو لي سنيپها روي هركد م ز دو كپي هاپلوتيپ ناميده ميشود تكنولوژيهاي تـو لييـابي فعلـي فقـط مـيتو ننـد قطعههايي ز ژنوم ر به طول چند هز ر جفت باز در ختيار قر ر دهند ما نميتو نند مشخص كنند هر قطعه به كد م كپي تعلـق د رد بنـابر ين ز روشهاي محاسباتي بر ي بدست آوردن هاپلوتيپها ز روي ين قطعهها ستفاده ميشود تكنولوژيهاي تو لييابي مقد ر كيفيت Q ر به عنو ن نگاشت صحيحي ز حتمال شتباه بودن باز در ختيـار قـر ر مـيدهنـد بهتـرين روش ر ئه شده مبني بر فرمولهسازي مسأله با ستفاده ز Max SAT ميباشد در ين پاياننامه روش جديدي ر ئـه شـده كـه در آن ز Max SAT وزند ر و همچنين مدل WMLF به جاي Max SAT و مدل MEC به منظور به كار بردن مقادير كيفيت بر ي دستيابي به دقت بالاتر ستفاده شده ست مدلهاي مختلفي بر ي مسألهي بازسازي هاپلوتيپهاي يك فرد وجـود د رد در يـن پايـاننامـه نشـان د ده شـده كـه يـك مـدل مبتنـي بـر محتملترين پس ز عمال تقريبهاي عمدت معقولي به مدل MEC تبديل ميشود كه ين مر نشاندهندهي منطقي بودن ين مدل عليرغم ا برخي ز نتقاد ت در دبيات مربوطه ست معيار رزيابي جديدي نيز به نام نرخ بازسازي وزند ر معرفي كرده يم و به منظـور رزيـابي روش پيشنهادي آن ر با دو روش ديگر بر ساس معيارهاي پيشنهادي و MEC مقايسه كرده يم نتايج يـن مقايسـه روي د دهي و قعـي متعلـق بـه 87821 NA بهبود جزئي ر نشان ميدهد لازم به ذكر ست كه دقت لگوريتمها بالاي ۰۹ ميباشد كلمات كليدي ۱ سنيپ ۲ هاپلوتيپ ۳ بازسازي هاپلوتيپها ۴ رضا پذيري
چكيده انگليسي :
An Algorithm Based on Weighted Max SAT a Maximum Likelihood Model and a New Metric for Single Individual Haplotyping Problem Ilnaz Khodadadi i khodadadi@ec iut ac ir Date of Submission January 2014 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan Iran Degree M Sc Language FarsiSupervisor Seyed Rasoul Mousavi srm@cc iut ac irAbstract Human genomes vary from each other in certain positions Single nucleotide polymorphism SNP isthe most common type of these variations SNPs are of importance in drug design and medical diagnosticapplications and they also offer highest resolution for tracking disease genes In diploid organisms such ashuman the chromosomes come in two copies one inherited from the mother and one from the father TheSNP sequence on each copy of chromosome is called haplotype Current sequencing technologies can onlyprovide fragments in at most several thousand base pairs and they cannot tell which copy of chromosome thefragments belong to Hence computational methods are used to rebuild two haplotypes from these fragments Sequencing technologies provide quality value Q which is an integer mapping of q the probability thatthe corresponding base call is incorrect The current state of the art single individual haplotyping algorithmuses Max SAT In this research we have proposed a novel method that uses weighted Max SAT and WMLFmodel instead of Max SAT and MEC model with purpose of using quality values to make results moreaccurate There are several models for single individual haplotyping problem In this research it is shown that amaximum likelihood model and the MEC model are equivalent under reasonable approximations Althoughthere are some criticisms on the MEC model this shows its rationality We also have proposed a novel metriccalled Weighted Reconstruction Rate To evaluate the proposed algorithm we compared it with two othermethods using MEC and the proposed metric The results of this comparison on real data for NA12878 showslight improvements given that the accuracy of methods is more than 90 Keywords SNP haplotype Single Individual Haplotyping Haplotype Assembly Satisfiablity
استاد راهنما :
رسول موسوي
استاد مشاور :
ناصر قديري مدرس
