[發明專利]一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法

在審

• 申請號: 201810794180.3
• 申請日: 2018-08-30
• 公開（公告）號: CN108897987A
• 公開（公告）日: 2018-11-27
• 發明（設計）人: 王憶文;王剛
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F19/22
• 分類號: G06F19/22
• 代理公司: 暫無信息
• 代理人: 暫無信息

該發明公開了一種將Needleman?Wunsch(以下簡稱N?W)算法在FPGA平臺實現并優化的新方法。本發明是圍繞N?W算法的打分與回溯兩方面進行優化。N?W算法打分方面，本發明提出優化的刪減策略和優化的動態規劃(Dynamic Programming)分塊方案來減少FPGA實現的時間消耗和資源消耗；N?W算法回溯方面，本發明采用簡化的回溯方向，更加便于FPGA實現，本發明采用兩組回溯模塊，與打分系統構成流水線處理，大大提高打分系統硬件利用效率，減少序列比對的整體時間。

技術領域

本發明涉及生物信息學領域，特別涉及一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法。

背景技術

生物信息學是生物學、醫學、數學、計算機科學等多個學科的前沿交叉學科，具有重要的理論和應用價值。生物信息序列通常指的是通過基因測序技術得到的DNA、RNA序列，這些序列包含了該物種的遺傳信息，通過對生物信息序列的分析處理得到的信息在醫學疾病研究、生物進化研究等領域都具有重要的意義。

生物信息序列的處理流程中最為重要的步驟是序列比對，同時它也是耗時較久的一個步驟，這是因為通常待比對物種基因堿基數量龐大，比如人類全基因組的總堿基個數大約是30億，采用存儲介質存儲后，目標序列和參考序列所占用空間將達到數百GB，另一方面對這數量級別的數據進行計算處理將會耗費大量的計算資源和時間。

生物信息序列比對最基本的是雙序列比對，兩條由A，C，G，T四種基本堿基構成的DNA序列通過序列比對算法得到待比對序列相對于參考序列的比對結果。其中雙序列比對算法一般有三種：動態規劃算法(Dynamic Programming)、和詞法以及點矩陣法，本發明使用動態規劃算法。

用于生物序列比對的動態規劃算法主要為兩種：適用于全局序列比對的Needleman-Wunsch算法和適用于局部序列比對的Smith-Waterman算法。本發明基于Needleman-Wunsch算法提出一種針對短序列比對在FPGA平臺實現并優化的新方法。

當前國內外對于利用硬件平臺實現全局序列比對主要集中在N-W算法的實現技術上。主要的硬件計算平臺有ASIC(Application Specific Integrated Circuits)，FPGA(Field Programmable Gate Arrays)，GPU(Graphics Processors Units)，和CPU(CentralProcessing Unit)等。相比于ASIC的最優性能，制約ASIC實現的更是它投入研發的高額費用、研發周期過長帶來的時間成本以及比對算法的更新速度，很有可能芯片研制出來之后，算法已經得到了更新，導致ASIC較難在算法實現方面立住腳跟。GPU平臺雖有高吞吐量，但是其存儲資源受限。CPU較為常規，并且現有的生物序列比對多利用計算機集群搭配業界序列比對軟件來處理，實現起來最為簡單，但是由于其串行執行命令導致效率也是最低。相比于前面的平臺，雖然FPGA時鐘頻率一般在兆赫茲級別，但是FPGA擁有大量的可編程邏輯資源，非常適合并行計算，并且集成了FPGA芯片的開發板外圍設備齊全，特別是存儲外設。這些特點使得FPGA非常適合做為N-W算法的硬件加速器。

基于N-W算法的特點，現有的在FPGA上實現的方法都是基于一種脈動式陣列，但規模有大有小，實現的方法也各有差異，但在各自支持的目標序列都得到了加速效果。本發明在公認的脈動式陣列基礎上采用了優化的刪減策略和優化的分塊動態規劃策略。

發明內容

本發明提供一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法。該方法改進之處在于：包括以下步驟：