Skip to main content
SUPERVISOR
Seyed Rasul Moosavi,Naser Ghadiri modaress
سید رسول موسوی (استاد راهنما) ناصر قدیری مدرس (استاد مشاور)
 
STUDENT
Ilnaz Khodadadi
ایلناز خدادادی

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1390
Human genomes vary from each other in certain positions. Single nucleotide polymorphism (), is the most common type of these variations. are of importance in drug design and medical diagnostic applications and they also offer highest resolution for tracking disease genes. In diploid organisms such as human, the chromosomes come in two copies (one inherited from the mother and one from the father). The sequence on each copy of chromosome is called haplotype. Current sequencing technologies can only provide fragments in at most several thousand base pairs and they cannot tell which copy of chromosome the fragments 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 that the corresponding base call is incorrect). The current state-of-the-art single individual haplotyping algorithm uses Max-SAT. In this research, we have proposed a novel method that uses weighted Max-SAT and WMLF model instead of Max-SAT and MEC model, with purpose of using quality values to make results more accurate. There are several models for single individual haplotyping problem. In this research, it is shown that a maximum likelihood model and the MEC model are equivalent under reasonable approximations. Although there are some criticisms on the MEC model, this shows its rationality. We also have proposed a novel metric called "Weighted Reconstruction Rate". To evaluate the proposed algorithm, we compared it with two other methods using MEC and the proposed metric. The results of this comparison on real data for NA12878 show slight improvements, given that the accuracy of methods is more than 90%. Keywords: , haplotype, Single Individual Haplotyping, Haplotype Assembly, Satisfiablity
ژنوم انسان‌ها در مکان‌های مشخصی با یک‌دیگر تفاوت دارند. چندریختی تک‌نوکلئوتیدی یا به اختصار اسنیپ، متداول‌ترین نوع این تفاوت‌هاست. اسنیپ‌ها نقش مهمی در کاربردهای وسیعی مانند تشخیص پزشکی و طراحی دارو ایفا می‌کنند و علاوه بر آن امکان ردیابی ژن‌های بیماری را فراهم می‌آورند. در موجودات دیپلوئیدی مانند انسان، دو کپی از هر کروموزوم وجود دارد (یکی از مادر و دیگری از پدر به ارث می‌رسد)؛ توالی اسنیپ‌ها روی هرکدام از دو کپی، هاپلوتیپ نامیده می‌شود. تکنولوژی‌های توالی‌یابی فعلی فقط می‌توانند قطعه‌هایی از ژنوم را به طول چند هزار جفت باز در اختیار قرار دهند اما نمی‌توانند مشخص کنند هر قطعه به کدام کپی تعلق دارد. بنابراین از روش‌های محاسباتی برای بدست آوردن هاپلوتیپ‌ها، از روی این قطعه‌ها استفاده می‌شود. تکنولوژی‌های توالی‌یابی مقدار کیفیت Q را به عنوان نگاشت صحیحی از احتمال اشتباه بودن باز در اختیار قرار می‌دهند. بهترین روش ارائه شده مبنی بر فرموله‌سازی مسأله با استفاده از Max-SAT می‌باشد. در این پایان‌نامه، روش جدیدی ارائه شده که در آن از Max-SAT وزن‌دار و هم‌چنین مدل WMLF به جای Max-SAT و مدل MEC به منظور به کار بردن مقادیر کیفیت برای دستیابی به دقت بالاتر استفاده شده است. مدل‌های مختلفی برای مسأله‌ی بازسازی هاپلوتیپ‌های یک فرد وجود دارد. در این پایان‌نامه نشان داده شده که یک مدل مبتنی بر محتمل‌ترین، پس از اعمال تقریب‌های عمدتاً معقولی به مدل MEC تبدیل می‌شود که این امر نشان‌دهنده‌ی منطقی بودن این مدل علیرغم برخی از انتقادات در ادبیات مربوطه است. معیار ارزیابی جدیدی نیز به نام نرخ بازسازی وزن‌دار معرفی کرده‌ایم و به منظور ارزیابی روش پیشنهادی، آن را با دو روش دیگر براساس معیارهای پیشنهادی و MEC مقایسه کرده‌ایم. نتایج این مقایسه روی داده‌ی واقعی متعلق به NA12878 بهبود جزئی را نشان می‌دهد. لازم به ذکر است که دقت الگوریتم‌ها بالای 90% می‌باشد. کلمات کلیدی: 1- اسنیپ‌ 2- هاپلوتیپ 3- بازسازی هاپلوتیپ‌ها 4- ارضاءپذیری

ارتقاء امنیت وب با وف بومی