1. 國防科學技術大學 計算機學院，湖南 長沙 410073
摘 要：面向蛋白質二級結構預測領域，基于FPGA平臺設計了一種細粒度的GOR算法加速器，采用多端口并行查詢策略同時獲取當前中心殘基計算窗口中的所有信息值；使用流水線的計算方式有效提高了并行效率。在單片FPGA上的實驗結果表明，與運行在Intel E7400雙核處理器上的GOR IV程序相比，可獲得超過284倍以上的加速效果和超過240倍的系統性能功耗比。
關鍵詞：生物信息學；蛋白質二級結構；GOR算法；細粒度并行；硬件加速器；FPGA
A GOR Algorithm Accelerator for Protein Secondary Structure Prediction on FPGA
LEI Guoqing1+, DOU Yong1, GUO Song1
1. School of Computer Science, National University of Defense Technology, Changsha 410073, China
Abstract: This paper presents a fine-grained parallel FPGA accelerator for protein secondary structure prediction based on GOR algorithm. Firstly, all the information values within a window of 17 amino acid residues are available simultaneously by querying parameter memory with multiple ports. Secondly, we use the pipelining method to exploit parallelism effectively. The experimental results on one FPGA chip show a factor of more than 284x in speedup and that of more than 240x in system power consumption performance ratio respectively, over the GOR IV software running on a PC platform with Intel Core 2 Duo E7400 2.80GHz CPU.
Keywords：Bioinformatics; protein secondary structure; GOR algorithm; fine-grained parallelism; hardware accelerator; FPGA
文獻標識碼: A 中圖法分類號: TP302
1引言
蛋白質是生物體最重要的組成物質之一，是生命活動的主要承擔者。蛋白質的功能由其結構決定，蛋白質的結構可分為一級結構、二級結構、超二級結構和三級、四級結構[1]。由于依靠實驗測定蛋白質的空間結構成本高，速度慢，對蛋白質的空間結構進行預測成為研究蛋白質結構的主要途徑之一。20世紀60年代初Anfinsen提出蛋白質的一級結構決定其空間結構的理論，從理論上為預測蛋白質的各級結構奠定了基礎[2]。通過研究發現，盡管蛋白質序列中的構象數目相當大，但是由二級結構組裝形成一定的空間結構的方式有限，從蛋白質一級序列出發先預測出二級結構，再由二級結構預測其三級結構成為了一個有效途徑 [1]。從20世紀60年代中期至今，蛋白質二級結構預測發展了近50年的時間，出現了很多種預測方法。例如基于統計分析的Chou-Fasman方法[3]、GOR方法[4]、神經網絡方法[5]等；基于知識的Lim方法[6]等；將多種預測算法進行混合使用的方法等。隨著測序技術的發展，蛋白質序列數據庫膨脹的速率遠遠超過蛋白質結構增長的速率[7]，如何利用計算機的手段在已有算法條件下提高蛋白質二級結構預測的速率也越來越成為值得研究的問題。在現有的預測算法中，基于統計分析的GOR方法物理意義明確，數學推導嚴格，是一種經典的蛋白質二級結構預測算法。GOR算法復雜度不高，但是在處理規模龐大的數據庫序列時性能受到限制，對其進行加速成為了一項值得研究的課題。
近年來，FPGA (Field Programmable Gate Array) 器件以其可編程特性、細粒度并行能力、豐富的計算資源、靈活的算法適應性和較低的功耗及硬件代價成為理想的可編程系統平臺，CPU與FPGA相結合的生物信息學算法加速器成為近年來研究的熱點。目前還沒有基于FPGA平臺對GOR算法進行加速研究的報道。本文設計了一種基于FPGA平臺的細粒度GOR算法加速器，在分析程序運行特點的基礎上，采用多端口參數并行查詢策略獲取當前中心殘基計算窗口中的所有信息值；對所有殘基構象的預測實現了流水操作。在單片XC5VLX330 FPGA上成功集成了算法加速器，試驗結果表明，當蛋白質序列總長度超過12億時，與運行在Intel E7400雙核CPU上的GOR IV軟件相比，可獲得超過284倍以上的加速效果，并且系統性能功耗比達到240倍以上。
２GOR IV程序分析
GOR是一種基于信息論和貝葉斯統計學的方法。它的基本思想是將蛋白質序列當作一串信息值處理，不僅考慮被預測位置本身氨基酸殘基種類的影響，同時還考慮相鄰殘基種類對該位置構象的影響。GOR將信息函數分為多項加和形式，其信息值構成了20種氨基酸出現在不同位置時的直接信息量表，根據該表和相關計算公式，就可以對一條肽鏈中任一位置殘基的構象進行預測。
GOR IV程序是GOR方法實現的最新版本[8]，其針對長度為17的殘基窗口進行二級結構預測，對于序列中的每一個殘基，將與該殘基左右緊鄰的8個殘基與它放在一起考慮。GOR IV根據已知蛋白質二級結構的267條數據庫序列進行分析，計算出中心殘基的二級結構分別為螺旋（H）、折疊（E）和轉角（C）時每種氨基酸出現在窗口中各個位置的概率，產生一個17x20的信息矩陣。對于輸入序列中的每一個殘基，GOR IV計算出當前殘基構象分別為H、E、C的概率ph、pe、pc，從中選取概率最大的作為當前殘基的構象。
GOR IV的核心處理過程如圖1所示，Predic階段對每個殘基的構象進行初步預測，First_pass和Second_pass分別對前一階段產生的結果進行校正。其中預測階段（Predic）是整個核心處理過程的瓶頸，測試發現，預測階段的執行時間占到整個核心處理過程執行時間的99%以上，是進行加速的主要對象。預測階段分為三個處理過程：讀取infopair信息表（Read infopair），讀取infodir信息表（Read infodir）和根據歸一化原則計算構象概率（Normalize）。其中讀取信息表是預測階段的主要工作，其規律如圖2所示。
在圖2中，最上面一行表示當前預測的蛋白質序列，三角符號指向的字符為當前要預測的中心殘基，對于每個中心殘基的預測需要考慮其左右8個殘基的局部信息。橫坐標dis1和縱坐標dis2分別表示當前窗口中其他殘基與中心殘基的相對位置，坐標系中的陰影方格對應infopair表查詢操作，查詢操作的順序為“按列從左至右，列內從上至下”，每次查詢操作讀回一個信息值并進行累加。infopair是一個四維參數表，其定義為：infopair[konf][np][aa1][aa2]，其中konf變化范圍為1~2，np變化范圍為1~136，aa1和aa2分別表示陰影方格橫坐標dis1和縱坐標dis2對應字符的編碼。對于每個陰影方格，需要根據dis1和dis2的值得到對應字符編碼和np值（圖中陰影方格里面的數字表示np值，按列從左至右，列內從上至下各個陰影方格對應的np值依次為1~136），然后查詢konf分別為1和2兩種情況下的表值a和b，對a和b分別進行累加。查詢完infopair表后得到兩個累加值a和b。infodir為一個三維表，其定義為：infodir[konf][dis1+9][aa1]，其中konf=1~2，aa1表示dis1對應的字符編碼。infodir表查詢的次數為17次，對應圖2中最后一行虛線方格所示，查詢方向為dis1的變化方向。對于每個虛線方格，根據dis1確定aa1，然后查詢得到konf分別為1和2兩種情況的表值a和b，并在之前的基礎上累加，查詢完infodir表后得到最終的兩個累加值a和b。在此基礎上，使用公式（1）、（2）、（3）分別得到當前殘基構象為H、E、C的概率ph、pe、pc，比較概率大小即可確定當前殘基最可能的構象。
當中心殘基預測完畢后，計算窗口向右移動一個位置，計算下一個中心殘基的構象。反復執行上述過程，最后得到蛋白質序列的二級結構。
通過以上分析發現：（1）序列結構預測過程簡單，重復性強，字符構象的預測結果依賴于參數值，計算每個中心殘基構象所需的查表次數相同（infopair為136x2次，infodir為17x2次），且最終結果與查表的順序無關；（2）由于每次查表只得到一個參數值，串行查表是軟件效率不高的主要原因，因此提高參數表查詢效率是對GOR算法進行加速的關鍵。
３GOR算法加速器
3.1系統結構
如圖3所示，GOR算法加速系統由一臺主機和一個可重構算法加速器構成。主機通過PCI-E接口將輸入的蛋白質序列加載至算法加速器，加速器完成所有序列殘基構象的預測并將結果送回主機，主機完成后續的工作，將結果提交給用戶。加速器主要包括一片大容量FPGA（由算法核心邏輯、DDR II存儲控制器和PCI-E接口控制器三部分構成）和兩個總容量為4GB DDR II存儲器（SODIMMs）。存儲器直接與FPGA相連，用于存儲蛋白質序列數據和預測結果，DDR II存儲控制器實現對片外存儲器的訪存操作。PCI-E接口控制器實現加速器與主機間的數據交互（輸入蛋白質序列，輸出預測結果）。
算法核心邏輯由GOR控制模塊，Predict模塊，First_pass模塊，Second_pass模塊和結果寫回控制器組成。其中GOR控制模塊負責啟動DDR II存儲控制器從外存載入蛋白質序列，啟動Predic、First_pass、Second_pass模塊的執行等。Predic模塊從infopair和infodir存儲器中讀取所需計算參數，對當前載入的序列的每個殘基進行二級結構預測，并將結果寫到緩存中。First_pass模塊從Predic模塊的結果緩存中讀取結果并進行修正，修正后的結果寫入到緩存中。Second_pass模塊從First_pass模塊的結果緩存中讀取數據并進行第二次修正，修正后的結果寫到緩存中。結果寫回控制器從Second_pass模塊的結果緩存中讀取數據，并通過DDR II存儲控制器將結果寫回DDR II存儲器。
3.2加速策略
l 多端口并行參數查詢
對于單個殘基構象的預測，查詢infopair表需要272（136x2）次，根據np值的不同（np變化范圍為1~136）將infopair參數表拆分為136塊存儲（infopair1~infopair136），每個存儲塊為雙端口，分別用于獲取konf為1和2時的參數值。這樣，對于infopair表的查詢可以同時進行。將infodir表的存儲塊復制17份（infodir1~infodir17），每個存儲塊同樣為雙端口，則對infodir表的34（17x2）次查詢可以同時進行。
如圖4所示，灰色部分表示存儲器，每個存儲器都是雙端口，以便同時讀取conf值為1和2的兩個參數值。對于序列中的每個殘基，首先根據殘基窗口中的17個殘基編碼同時計算得到查找各個參數表存儲器的地址，并將地址送入153（136個infopair加上17個infodir）個存儲器地址線上，則經過兩拍（使用Block Memory存儲）后得到konf分別為1和2的各153個參數（為方便起見，圖4中只畫出了konf為1或者2的153個值）。對于153個同時得到的參數值，我們將其一起執行多級加法（加法級數為8級，每級加法器的個數為該級加數個數的一半，如果加數為奇數個則最后一個加數直接送入到下一級）。圖4的最右邊的箭頭表示時鐘周期，由圖4可知，只需經過8個時鐘周期，送入的153個待累加數就完成了累加。
l 數據驅動的計算流水線
我們針對GOR算法的全部計算過程（包括Predic、First_pass和Second_pass）進行加速，并對整個過程實現了流水化。如圖5所示，我們將Predic劃分為如下四個子模塊：Get_seq（獲取序列元素編碼），Get_para（獲取參數值），Acc_add（分級累加），Normalize（將結果歸一化得到三種結構對應的概率）。其中Normalize模塊又分為如下5個子模塊：Cordic（實現指數計算）、Add（32位浮點加法）、Div（32位浮點除法）、Mul（32位浮點乘法）、Compare（32位浮點比較）。經過劃分之后，預測階段（Predic模塊）由109個流水段組成。對于長度為N的單條蛋白質序列，預測階段完全結束需要的時鐘周期數為109+N。而校正階段（First_pass和Second_pass）的計算開銷是不確定的，與預測階段的結果相關，最小為0，最大為2N。當N大于109時，校正階段的開銷可能大于預測階段，校正過程將成為處理過程的瓶頸，在某些情況下將導致處理過程停頓。為了避免處理過程停頓，我們將兩個校正階段進行了復制，將預測階段產生的結果輪流分發給處于空閑狀態的編號最小的校正模塊。在宏觀上，Predic、First_pass、Second_pass三個階段構成一條任務級流水線，三個階段的處理速度大體平衡，并且可以實現多條序列的并行處理。
4實驗結果
４.１實驗環境
我們在測試平臺上實現了GOR算法加速器。測試平臺由一臺通用計算機和一個算法加速器構成。算法加速器主要包括1片Xilinx Virtex5系列FPGA（XC5VLX330），兩條總容量為4GB的DDRII SODIMM存儲條（Kingston KVR 667D2S5/2G），加速器通過PCI-E×8數據通道與主機相連，有效數據傳輸帶寬為1.0GB/s。GOR軟件版本為GOR IV[9]，軟硬件對比測試主要在Intel E7400雙核CPU平臺上進行，試驗結果表明硬件加速器的計算結果與軟件結果完全一致。
４.２FPGA資源利用
我們在Xilinx商用FPGA器件
XC5VLX330平臺上實現了GOR算法加速器。綜合結果表明，算法加速器使用了40157個Slice LUT（占全部邏輯資源的17%），159個Block RAM（占總存儲資源的55%），可見存儲資源是FPGA實現的瓶頸。這使得在單片XC5VLX330上最多只能集成一個GOR加速引擎。綜合實驗表明，在目前最大規模的XC6VSX475T上可以集成6個加速器引擎，可以實現對6條蛋白質序列的并行處理。
4.3與現有的GOR軟件版本對比
我們從NCBI（National Center Biotechnology Information, 美國國立生物技術信息中心）提供的ftp服務器[10]上下載了4個不同規模的蛋白質序列庫，將其作為GOR IV的輸入，分別統計了GOR核心處理過程在Intel通用微處理上的執行時間，并與FPGA算法加速器進行了比較。由表1可以看出，FPGA算法加速器性能明顯超過了Intel通用微處理器。
硬件環境：
[2] FPGA accelerator (XC5VLX330), 166MHz, 4.0GB memory.
當蛋白質序列總長度超過12億時，使用算法加速器可獲得超過284倍的加速效果。并且，使用電流計（型號HIOKI3290）測試表明，算法加速器功耗不超過15W，而Intel雙核處理器平均功耗為65W[11]。與Intel微處理器相比，FPGA算法加速器的系統性能功耗比達到240倍以上。所以就綜合性能而言，基于可重構FPGA的細粒度并行計算平臺方案明顯優于傳統的基于通用微處理器的解決方案。
５結束語
GOR是蛋白質二級結構預測領域比較經典的算法之一，其對于大規模序列數據的處理性能有待提高。本文基于FPGA平臺對GOR IV程序實現了加速，采用多端口并行查詢策略一次獲取計算窗口內的所有信息值；采用全流水的設計提高了并行效率。試驗結果表明，當蛋白質序列總長度超過12億時，與運行在Intel E7400 雙核CPU上的GOR IV軟件相比，可獲得超過284倍的加速效果，并且系統性能功耗比達到240倍以上。
References
[1] Zhang Haixia. Research of Protein Secondary Structure Prediction Methods. [D].2004
[2] Anfinsen CB, Principples that Govern the Folding of Protein Chains, Science, 1973, 181: 223-230.
[3] Chou PY, Fasman GD. Prediction of protein conformation. Biochemistry 1974;13:211–215.
[4] Carnier J, Osguthorpe DJ, Robson B: Analysis of the accuracy and implication of simple methods for predicting the seconderys tructurco f globular proleins.I Mol Biol 1978, 12O:97-120.
[5] Zhu Wei, et al. Application of Artificial Neural Network in Protein Secondary Structure Prediction [J]. CHINESE JOURNAL OF NATURE, 2003, 25(3)
[6] Lim VI. Structural principles of the globular organization of protein chains: a stereochemical theory of globular protein secondary structure. J Mol Biol 1974;88:857–872.
[7] Gu Junfeng. Several Key problems in Protein Structure Prediction. [D].2009
[8] Gamier J, et a1. GOR secondary structure prediction method IV．Meth Enzymol, 1996, 266: 540. 553.
[11] General Purpose Micro-processor Power Dissipation Statistic Report. [DB/OL] [2010-6-13]. http://en.wikipedia.org/wiki/List of CPU_power_dissipation
附中文參考文獻：
[1] 張海霞.蛋白質二級結構預測方法研究[D].2004
[5] 朱偉,史定華,王翼飛.神經網絡在蛋白質二級結構預測中的應用[J].自然雜志,2003,25(3)
[7] 谷俊峰.蛋白質結構預測中幾個關鍵問題的研究[D].2009
附作者簡介：
雷國慶，男，1986年生，本科畢業于華中科技大學計算機學院，現為國防科技大學計算機學院系統結構專業研究生，主要研究方向為生物信息學與可重構計算。
