بررسي روش هاي موجود و ارائه روشي جديد در ارتباط با تغييرات ساختار ژنوم

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

A study of existing methods and proposing a new method for genome structural variants Samira Ramazani s ramazani@ec iut ac ir Date of Submission 2011 09 20 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Seyed Rasoul Mousavi srm@cc iut ac ir Majid Talebi mtalebi@cc iut ac irAbstractA haplotype is a set of Single Nucleotide Polymorphisms SNPs from a given DNA and has valuablegenetic information SNPs are the most common genetic structural variants and haplotypes encode SNPs ina single DNA Haplotype has a relevant role in several genetics studies like mapping complex disease gens drug design and so on However retrieving directly haplotype from DNA sample using existingtechnonolgies is expensive and also time consuming This motivates the increasing interests in techniquesfor inferring haplotype data from genotypes which can be obtained quickly and economically Eachgenotype is a description of the conflated on two haplotypes inherited from both parents Although anumber of association studies can be done using only genotypes haplotype information is essential for thedetailed analysis of the mechanisms of disease While assessing the genetic contribution to traits it mayoften be much more informative to have haplotype data rather than to have only genotype data Thehaplotype inference problem under the assumption of pure parsimony consists in finding the smallestnumber of haplotypes that explain a given set of genotypes This problem is proved to be NP hard Severalmethods have been proposed since Clarck introduced the first algorithm to solve haplotype inferenceproblem in 1990 Methods for solving this problem are divided into two algorithms namely exact andinexact methods Existing exact methods guarantee obtaining purely parsimonious solutions but haveexponential time complexities and are not practical for large number or length of genotypes However inexact methods are relatively fast but do not always obtain optimum solutions In this dissertation at fristan exact algorithm called ISHIPs is proposed which has an improvement on an existing sat based algorithmnamelySHIPs SHIPs is the best current exact algorithm for haplotype inference probleb by pure parsimony ISHIPs uses a heuristic algorithm namely Collhaps to compute an upper bound for the problem in thepreprocessing phase Then make a sat based model given genotypes And try to solve the model by using anexisting sat solver In the next part of the dissertation a heuristic method proposed to solve haplotypeinference problem called freeCollhaps freeCollhaps algorithm introduces freedom degree concept and usesit to compute differences between a pair haplotypes freeCollhaps has an iterative procedure In the next stepwe use freeCollhaps as preprocessing phase of ISHIPs algorithm For improving freeCollhaps algorithm we add a simplification phase to this algorithm The simplification phase causes to reduce the complexity ofthe problem instances the best current heuristic until now is Collhaps which has a good performance onlarge scale datasets The performance of proposed algorithm was evaluated on several datasets Datasets aredivided into two groups random generated simulated datasets and real datasets The random generateddatasets are obtained by using some known software The real datasets are some parts of data which areexist in hapmap projects Each algorithm is compared with the best current algorithm Experimental resultsshow the efficiency of proposed algorithm in the running time and the number of inferred haplotypes foreach datasets KeywordsHaplotype inference pure parsimony exact algorithm heuristic algorithm NP hard م

رمضاني، سميرا

بررسي روش هاي موجود و ارائه روشي جديد در ارتباط با تغييرات ساختار ژنوم

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