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

在審

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

1.一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法，該方法包括優化的動態規劃刪減策略、優化的動態規劃分塊策略和優化的Needleman-Wunsch回溯方法。

2.如權利要求1所述的一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法，其特征在于如何對動態規劃元素進行刪減；Needleman-Wunsch算法本質是給相似矩陣中元素進行打分，實際上并不需要對矩陣的全部元素進行動態規劃，本發明基于帶寬(WIDTH)的概念，以矩陣主對角線的延長直線為主軸基準，向上移動WIDTH個元素單位確定上邊界，同理向下移動WIDTH個元素單位可以確定下邊界。上邊界覆蓋的元素所采用E值指定為0，下邊界覆蓋的元素所采用F值指定為0。被發明只對上下邊界內部區域包含的元素進行動態規劃，其他元素不進行計算。

3.如權力要求1所述的一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法，其特征在于Needleman-Wunsch算法的相似矩陣如何進行分塊。

4.如權力要求2所述的一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法，在基于優化的刪減策略基礎上，采用較少數量的PE對100-150bp長度的目標序列進行動態規劃。

本發明PE數量采用20，帶寬采用10，分塊界定標志為PE20開始進入計算，當PE20完成計算后，PE1-PE10開始新一輪動態規劃，如此類推直到完成整個需要動態規劃的矩陣區域。

5.如權力要求1所述的一種將Needleman-Wunsch算法在FPGA平臺實現并優化的新方法，其特征在于優化的Needleman-Wunsch回溯方法。

6.本發明對傳統的7種回溯方向采用簡化處理，只保留3種基本的回溯方向。在結果矩陣打分和回溯兩個流程中采用流水線處理，提高硬件電路資源利用率。