生物基因序列比對算法的并行優(yōu)化研究.pdf

1、該文在介紹了不同基因序列比對算法及其各自優(yōu)缺點的基礎(chǔ)上,針對Smith-Waterman算法著重分析了一些并行化方法,并結(jié)合集群式(Clustering)計算機系統(tǒng)提出了一種全新的并行優(yōu)化算法.該算法引入了哈希(hash)函數(shù),在將原算法串行優(yōu)化的同時,減弱了其原有的強數(shù)據(jù)相關(guān)性,并進行了合理的并行優(yōu)化.該優(yōu)化算法更快,更具平臺適應(yīng)性,真正充分利用到了近期蓬勃發(fā)展的高性能集群式計算機系統(tǒng),符合當今科技發(fā)展趨勢.該算法的主要思想是:利用h

2、ash函數(shù)對欲比較序列進行采樣,抽取部分樣本進行初期比較.初期比較完畢后得到若干可能相似的序列,此時才進行完整的比較,得到符合用戶要求的相似序列.該算法不僅減少了總比較次數(shù),加強了比對效果,縮減了比對時間,而且將原來數(shù)據(jù)相關(guān)性很強、不適合并行化的動態(tài)規(guī)劃算法改變成為可并行化且易于并行化的新的優(yōu)化算法,使其能夠自如地運行在各種高性能并行計算機系統(tǒng)上.該算法是通過消息傳遞接口(MPI)嵌入C/C++編程實現(xiàn)的,運行在Linux系統(tǒng)平臺上.各