面向長序列數(shù)據(jù)的單體分型算法研究.pdf

1、單體型序列是生物遺傳分析中的一類重要信息。由于實(shí)驗(yàn)方法獲取單體型序列具有價(jià)格過高、速度慢等缺點(diǎn)，使用計(jì)算手段從易于獲取的基因型序列得到單體型序列成為人們的首選，并發(fā)展為基因組學(xué)里一個基礎(chǔ)的計(jì)算問題，稱為單體分型問題。隨著基因組學(xué)的發(fā)展，研究所需的單體型序列越來越長，有的甚至達(dá)到上百萬個位點(diǎn)，這給單體分型問題提出了新的挑戰(zhàn)。目前幾乎所有的大規(guī)模單體分型算法在個人計(jì)算機(jī)上都只能處理長度小于十萬的序列，因此迫切需要能處理長序列數(shù)據(jù)的單體分型算

2、法。本文主要研究在內(nèi)存有限的個人計(jì)算機(jī)上，分型長度十萬位點(diǎn)以上的長序列數(shù)據(jù)集的快速單體分型算法，具體工作如下:
　　1.面向長序列數(shù)據(jù)集的WinHAP2.0單體分型算法改進(jìn)及并行化
　　WinHAP2.0算法是近年來我們研究小組提出的一個長序列單體分型算法，本文對WinHAP2.0算法從兩方面進(jìn)行了改進(jìn)，一是使用投票策略改進(jìn)了段合并方法，二是進(jìn)行了并行化。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的WinHAP2.0算法相比于原算法在段合并處的位點(diǎn)

3、的交換錯誤率下降了20％-30％左右。相比于其他算法，改進(jìn)后的算法計(jì)算精度與最好的算法相似，而計(jì)算時(shí)間和空間消耗低數(shù)倍到數(shù)十倍。該算法能夠在個人計(jì)算機(jī)上使用12.8MB的內(nèi)存分型500條長度一百萬個位點(diǎn)的序列，而其他算法均無法完成這一任務(wù)。算法的并行化獲得了幾乎線性的加速比。
　　2.面向大規(guī)模長序列數(shù)據(jù)集的單體分型算法
　　由于WinHAP2.0算法存在當(dāng)序列條數(shù)很多時(shí)計(jì)算時(shí)間過長的缺陷，本項(xiàng)工作進(jìn)行了進(jìn)一步的改進(jìn)，引入了

4、序列聚類思想，提出了CbWinHAP算法。CbWinHAP算法首先將比較相似的序列聚成一類，再分別進(jìn)行推導(dǎo)，由于聚類提高了相似序列的作用從而精度得到提高。而序列條數(shù)的減少又使得計(jì)算時(shí)間和空間得到降低。實(shí)驗(yàn)結(jié)果表明CbWinHAP算法在保證計(jì)算精度相比于原WinHAP算法和WinHAP2.0算法不下降的情況下，計(jì)算時(shí)間和空間均降低了數(shù)倍。為了進(jìn)一步提高計(jì)算速度，我們也為CbWinHAP算法進(jìn)行了并行化。實(shí)驗(yàn)表明并行后的算法獲得了接近于線性