Location:Home > Engineering science > Computer Science > Computer Science and Technology > Research on Graph-Based Algorithm for Tagsnps Selection

Research on Graph-Based Algorithm for Tagsnps Selection

Downloads: []
Tutor: GuoMaoZu
School: Harbin Institute of Technology
Course: Computer Science and Technology
Keywords: TagSNPs selection,graph based algorithm,maximum density subgraph,precision predi
CLC: Q78
Type: Master's thesis
Year:  2008
Facebook Google+ Email Gmail Evernote LinkedIn Twitter Addthis

not access Image Error Other errors

Single Nucleotide Polymorphism (SNP) is a DNA set of polymorphism based on the single nucleotide variations at the genomic level. A small subset of informative SNPs, known as TagSNPs or htSNPs, is able to capture most variations in these haplotypes. However, it is expensive and hard to deal with massive data. So it is very necessary to develop mathematic and computational methods to select TagSNPs.In this paper, several algorithms about TagSNPs selection are discussed in detail. By fully taking advantages of these algorithms, a new method named MDStagger is proposed in this paper to improve the prediction precision and reduce time consumption.The creativities and contribution are discussed in detail as follows:Firstly, the methods to select TagSNPs are introduced, including the mathematic models. Moreover, these methods are compared to show their advantages, disadvanges and their scope of application.Secondly, a graph-based TagSNPs selection algorithm named MDStagger is proposed including graph construction and the maximum density subgraph idea. And TagSNPs selection using maximum density subgraph is emphatically introduced. Experiments prove that the algorithm largely solves the problem of local optimization and the accuracy of the prediction results is further improved.Thirdly, a method for precision prediction using multiple TagSNPs is proposed. Experiments prove that this method not only improves prediction precision but also points out prospecting directions for missing SNPs and evaluation criterions for TagSNPs selection algorithms.Finally, we developed a system based on MDStagger and the improved precision prediction method. The data preprocessing module is suitable for other TagSNPs selection algorithms as well.
Related Dissertations
Last updated
Sponsored Links
Home |About Us| Contact Us| Feedback| Privacy | copyright | Back to top