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

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

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

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

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