基于圖的標志SNP位點選擇算法研究.pdf

1、單核苷酸多態(tài)性（SingleNucleotidePolymorphism，SNP）是指在基因組水平上由單個核苷酸變異所引起的DNA序列的多態(tài)性。在各類單體型中，少部分SNP位點包含絕大部分的遺傳變異信息，這些位點稱為標志SNP位點（TagSNP或htSNP）。通過生物實驗從基因型序列中獲取確定的單體型序列，即單體分型（Haplotyping）可以得到比較精確、可靠的結(jié)果。然而，代價高昂，難以滿足當前海量生物數(shù)據(jù)分析。因此，借助數(shù)學和計算

2、機結(jié)合的計算分子生物學手段尋找TagSNP位點，是解決單體分型問題的一個有效途徑。
　　本文對TagSNP位點選擇問題進行了詳細的闡述，并在充分研究和分析當前SNP位點選擇算法的基礎上，創(chuàng)新性地提出了基于圖的TagSNP位點選擇算法MDStagger，有效的提高了預測精確度，縮短了算法的運行時間。
　　具體地，本文的主要研究內(nèi)容和創(chuàng)新點如下：
　　第一，描述了TagSNP位點的選擇問題，包括解決該問題的數(shù)學模型和算法思

3、想。同時，本文還分析了這些算法的優(yōu)缺點及各自適用的范圍。
　　第二，提出了基于圖的TagSNP位點選擇算法MDStagger。文中闡述了圖模型的構(gòu)建法則以及將SNP位點的信息轉(zhuǎn)化為最大密度子圖的思想。重點描述了通過最大密度子圖來尋找TagSNP位點的思想。實驗表明，該算法能夠避免因為隨機算法帶來的局部最優(yōu)問題和枚舉法產(chǎn)生的高時間復雜度等問題，與當前主要的TagSNP位點選擇算法相比較，具有較優(yōu)性能。
　　第三，提出了一種改進

4、的精確度預測方法，該方法基于多TagSNP位點聯(lián)合預測非TagSNP位點。實驗表明，多TagSNP位點聯(lián)合預測比單一TagSNP位點預測，能夠得到更高的精確度。該預測方法不僅提高了精確度，同時也為SNP位點評價準則的改進以及缺失位點的預測指明了一個新的方向。
　　第四，實現(xiàn)了TagSNP位點選擇算法及其精確度預測系統(tǒng)。該系統(tǒng)使用了文中提出的基于圖的選擇算法。該系統(tǒng)的數(shù)據(jù)預處理模塊也適用于其它TagSNP位點選擇算法的前期數(shù)據(jù)處理。