基于圖的標(biāo)志SNP位點(diǎn)選擇算法研究.pdf

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

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

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

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