大規(guī)?；蚪M比對算法.pdf

1、隨著測序技術的發(fā)展，越來越多的動植物、微生物的全基因組序列得以測定完成，基因組數(shù)據(jù)和規(guī)模正在以前所未有的速度迅速增長?；蚪M在進化過程中常常會有基因復制，基因缺失，易位，倒置等大規(guī)模突變發(fā)生?；驈椭茣a(chǎn)生旁系同源基因；基因缺失會導致物種的直系同源性模糊；而易位或者倒置通常會引起遺傳物質(zhì)的重排。長基因組的序列比對可以查找基因組突變，是基因組數(shù)據(jù)的比較分析，物種的進化分析和基因功能研究的基礎。 傳統(tǒng)的動態(tài)規(guī)劃算法[1][2]的計算

2、復雜度為O(n<'2>)，其中n是輸入序列的平均長度．動態(tài)規(guī)劃只能處理長度在500K以內(nèi)的氨基酸序列或者基因組序列。基于統(tǒng)計推斷的SPA算法[3]的計算復雜度為O(n)，可以準確的比較長度在2M之內(nèi)的基因組序列，但是隨著長度的增加和輸入序列同源性的降低，比對誤差越來越大。 要比對長度規(guī)模更大的基因組序列，需要新的高效精確的算法。本文的結果就是開發(fā)適合大規(guī)?；蚪M序列比對的算法。具體結果如下： 1．首次將數(shù)據(jù)壓縮的思想用于

3、序列比對，對SPA算法做了改進，拓展了SPA算法的應用范圍，開發(fā)出GSPA-I算法，該算法可用于大規(guī)模的微生物基因組和真核生物基因組的序列比對，測試結果表明GSPA-I算法比傳統(tǒng)的序列比對算法速度大大提高，作長度大于2M的序列的比對結果的精確度高比SPA算法有明顯提高。 2．首次將基于語法的編碼 Yang-Kieffer算法[4]用于序列比對，開發(fā)出基于語法的比對算法GSPA-Ⅱ．GSPA-Ⅱ算法利用Yang-Kieffer碼首

4、先對輸入序列進行編碼處理，找到序列之間的語法匹配模塊GMB，在GMB的基礎上再完成比對，該算法比對規(guī)模大，克服了以往基因組序列比對算法受輸入序列規(guī)模限制的弱點，用編碼方法大大降低了算法的復雜度的同時，方便了對比對結果的分析。GSPA-Ⅱ算法能夠很快處理長度在200M以上的基因組染色體序列，另外GSPA-Ⅱ算法能找到倒置，換位等大規(guī)?；蚪M突變。實驗結果表明，GSPA-Ⅱ算法與最流行的 BLASTZ算法相比，比對速度平均高100倍左右，但