[發明專利]一種將Smith?Waterman算法在FPGA平臺實現的新方法

在審

• 申請號: 201611025162.6
• 申請日: 2016-11-10
• 公開（公告）號: CN106778077A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 陳觀君;王憶文;黃柯
• 申請（專利權）人: 電子科技大學;四川云合創智科技有限公司
• 主分類號: G06F19/22
• 分類號: G06F19/22
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種將S-W算法在FPGA上實現的新方法。該方法包括優化的動態規劃刪減策略、優化的動態規劃分塊策略和優化的S-W回溯方法。

2.如權利要求1所述的一種將S-W算法在FPGA上實現的新方法，其特征在于動態規劃元素如何進行刪減。

S-W算法本質是給相似矩陣中元素進行打分，實際上并不需要對矩陣的全部元素進行動態規劃，本發明基于帶寬(WIDTH)的概念，以矩陣主對角線的延長直線為主軸基準，向上移動WIDTH個元素單位確定上邊界，同理向下移動同樣多的元素單位可以確定下邊界。上邊界覆蓋的元素所采用E值指定為0，下邊界覆蓋的元素所采用F值指定為0。被發明只對上下邊界包含的元素進行動態規劃，其他元素被刪減。

3.如權利要求1所述的一種將S-W算法在FPGA上實現的新方法，其特征在于S-W算法相似矩陣如何分塊。

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

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

5.如權利要求1所述的一種將S-W算法在FPGA上實現的新方法，其特征在于優化的S-W回溯方法。

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