بررسي روش هاي موجود در تحليل تفاوت هاي ژنتيكي و اسنيپ ها و ارائه راه حل جديد

چكيده انگليسي :

A Study of Existing Methods for the Analysis of Genetic Variations and SNPs and Providing a New Solution Samaneh Nemati Samaneh nemati@ec iut ac ir Date of Submission 2012 08 02 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor Seyyed Rasoul Mousavi srm@cc iut ac ir Majid Talebi mtalebi@cc iut ac ir Abstract A haplotype is a sequence of Single Nucleotide Polymorphism SNPs from a given DNA and provides valuable genetic information SNP is the most common form of structural variant and haplotypes encode SNPs in a single DNA Haplotype information is useful in several genetics studies including mapping complex disease genes and drug design Also haplotype information is essential for understanding the detailed analysis of the mechanisms of some diseases So the study of haplotypes and consequently reconstructing them has been an important research area in the recent years However retrieving haplotype directly from DNA samples using existing technologies is expensive and also time consuming This motivates the increasing interests in techniques for reconstruction of haplotypes from fragments which can be obtained quickly and economically Fragments obtained from sequencing instruments are always associated with errors which makes the haplotype construction difficult In particular the problem based on the Minimum Error Correction MEC model which is the most frequently used model is NP hard A formal definition for the Haplotype Assembly problem is as follows given a set of inconsistent SNP fragments obtained by DNA sequencing find and correct the errors in the data to retrieve a maximally consistent pair of haplotypes compatible with the corrected fragments Various methods have been proposed since Lancia introduced the first algorithm to solve this problem in 2001 Methods for solving this problem are divided into two categories namely exact and inexact methods Because the size of real data is usually huge unfortunately exact algorithms are not practical for such data Hence the uses of heuristic algorithms on these data are recommended The current state of the art method for the problem is HapSAT This algorithm makes a sat based model and tries to solve the model by using an existing sat solver In this dissertation three heuristic algorithms are proposed each of which tries to improve the solution of current heuristic algorithm with separation of homozygote columns from heterozygote ones The separation operation is performed before constructing the sat based model The first algorithm ErrHapSAT is based on using the error rate of the underlying sequencing machine In this algorithm the error rate is used as a threshold for recognize the homozygous columns The second algorithm named BoundHapSAT separates the homozygous columns from heterozygous ones using statistical analyses of SNP matrix Finally in the third algorithm called MinedHapSAT the separation task is performed using the C4 5 algorithm The C4 5 is a decision tree induction algorithm which is one of the methods in machine learning The performance of proposed algorithm was evaluated on several datasets The datasets are divided into two groups namely random generated simulated and real datasets One of the real datasets is obtained from the Phase II of the HapMap projects and the other one is the HuRef data that is a commonly used dataset for such researches Each algorithm is compared with the best current algorithm The results indicate that the proposed methods with no sensible effect on running time increase the accuracy of the reconstructed haplotypes which is very plausible for the subsequent analyses of the obtained haplotypes Therefore the proposed methods replace the current state of the art for the Haplotype Assembly problem Keywords Haplotype Reconstruction Single Nucleotide Polymorphism SNP Minimum Error Correction MEC heuristic algorithm NP hard

نعمتي، سمانه

بررسي روش هاي موجود در تحليل تفاوت هاي ژنتيكي و اسنيپ ها و ارائه راه حل جديد

بازسازي هاپلوتايپ , حداقل تصحيح خطا , الگوريتم مكاشفه اي , NP- سخت