多核環(huán)境下的生物信息序列比對并行優(yōu)化方法的研究.pdf

1、隨著大數(shù)據(jù)時代的到來，如何提高計算效率已經(jīng)成為焦點問題。隨著生物數(shù)據(jù)庫信息的日益增多，需要對原有的串行計算模式進(jìn)行改變。同時提高主頻和淘汰單核心的多核心結(jié)構(gòu)成為并行計算的主流。不同于GPU特殊的硬件要求，多核結(jié)構(gòu)在數(shù)據(jù)傳輸、可移植性能上和發(fā)展前景上都具有優(yōu)勢，所以本文選擇在多核平臺上使用OpenMP語言對廣泛使用的BLASTN進(jìn)行并行計算的研究，同時使用基于Trie樹的預(yù)處理機制和調(diào)度分配算法更好的減少時間花銷。
　　首先，本文提

2、出基于Trie樹的預(yù)處理算法，主要思想是利用Trie樹過濾完全相同的字組，對數(shù)據(jù)庫進(jìn)行簡化處理，減少BLASTN算法中匹配的次數(shù)。預(yù)處理機制包括將原數(shù)據(jù)庫分割成多個小數(shù)據(jù)庫，將數(shù)據(jù)庫中的目標(biāo)序列劃分成長度為W的字組哈希表，建立Trie樹存儲相同的字組。實驗表明，建立Trie樹的預(yù)處理機制在數(shù)據(jù)庫規(guī)模較小時反而不如數(shù)據(jù)庫規(guī)模較大時高效，但是對于優(yōu)化BLASTN的并行算法有一定的作用。
　　其次，本文研究了BLASTN算法的串行程序，

3、分析其并行化可行性，使用Perf對BLASTN進(jìn)行熱點函數(shù)分析，對BLASTN進(jìn)行并行化改造。其并行BLASTN的思想主要在種子階段和延伸匹配階段，前者將查詢序列的字組劃分階段和查詢序列的字組與目標(biāo)序列字組比對得到高分字組(HSP)階段同時并行化，同時，利用多個核心同時計算任務(wù)量;后者對延伸匹配階段實行左右同時進(jìn)行延伸匹配和合并HSP的位置搜索樹上連續(xù)相鄰的字組，減少重復(fù)匹配次數(shù)，使并行改造后的BLASTN進(jìn)行加速。實驗表明，最好的情況