一種基於單比特化的基因比對處理方法
2023-06-14 11:41:31
專利名稱：一種基於單比特化的基因比對處理方法
技術領域：
本發明涉及基因比對方法，具體講涉及一種基於單比特化的基因比對處理方法。
背景技術：
1條DNA序列是由A，T，C，G等4種鹼基組成。簡單地說，作親子鑑定，就要對「親」、 「子」2條DNA序列進行比對(alignment)。比對時，從2條DNA序列各取第1個鹼基開始進 行比對，然後各取第2個鹼基進行比對，以此類推，從頭至尾全部逐拍進行比對。當然，對親 子鑑定，絕大多數比對都是相同的(A-A，T-T，C-C，G-G)。如果有不同(A_T，A_C，A-G， )， 就說明有突變。雙序列比對(Pairwise alignment)通常有3種算法動態規劃法(Dynamic programming)、點矩陣法(dot matrix method)禾口詞法(Word method)。現有的基因比對計算，大都採用普通的計算機或集群計算機系統，按照動態規劃 算法編程，然後通過程序進行計算。其計算時間隨基因長度非線性增長，計算速度較慢。動態規劃法主要有3種算法Smith-Waterman算法，Needleman-ffunsch算法和 Gotoh 算法。其中，Smith-Waterman 算法是 Temple Smith 和 Michael Waterman 在 1981 年 提出的，得到廣泛應用。近年國內外對於基於硬體的序列比對的研究主要集中在Smith-Waterman (簡稱 S-W)算法的實現技術。與本發明最接近的成果，如國防科學技術大學計算機學院張陽等在 「計算機科學與探索」 2008年05期上發表的「生物信息學雙序列比對算法加速器設計與實 現」，該文簡介「在FPGA上實現大規模脈動式陣列對雙序列比對算法進行加速能夠大幅度 提高比對的效率。以Smith-Waterman算法為例進行了實現驗證，結果表明本設計在性能上 優於傳統設計。與Pentium42. 60GHz通用微處理器計算機相比，使用加速器對長度為65536 的序列進行比對可獲得1555倍的加速比」。可見，其特點主要是用大規模脈動式陣列實現 了加速。[1]Zhang Yang etc. ,pair-wise genetic alignment has been implemented by large-scale systolic array on a FPGA chip, Computer Science and Exploration, 2008，No.5，
發明內容
本發明的目的是提供一種基於單比特化的基因比對處理方法，該方法包括兩條基 因序列，其改進之處在於包括如下步驟將需要比對的基因序列輸入到FPGA器件中後用單比特表示鹼基；用布爾邏輯表 示基因的突變規則，用包括門電路和寄存器的FPGA器件實現比對計算；用位置計數器和突 變計數器記錄突變的類型和數量，結束時將記錄發送給上層軟體；上層軟體計算處理後將 結果顯示在屏幕上。本發明提供的優選基因比對處理方法中，所說單比特表示鹼基為4位表示，鹼基 A、T、C和G分別用0001,0010,0100和1000表示，4位中只有1位是「 1」，稱為單比特表示法。本發明提供的再一優選基因比對處理方法中，所說FPGA器件通過2條3級流水線 來實現比對計算，所說2條流水線指正常流水線和突變流水線，所說3級流水線指用以確定 突變類型的三個寄存器比對過程。本發明提供的再一優選基因比對處理方法中，所說用布爾邏輯表示基因的突變規 則包含步驟將輸入的基因序列進行邏輯與運算；若與運算後輸出為1，則說明鹼基序列匹 配，進行下一鹼基比對運算；若與運算後輸出結果為0，則說明鹼基序列不匹配，比對流入 突變流水線，通過3級寄存器流水線判斷基因突變類型。本發明提供的再一優選基因比對處理方法中，所說流水線中均包含兩個用於存放 鹼基的寄存器。本發明提供的再一優選基因比對處理方法中，所說位置計數器有1個，用來保存 突變基因的位置和數量；突變計數器有4個，分別為轉換計數器、顛換計數器、插入計數器 和缺失計數器，用來記錄4種突變類型的位置和數量。本發明提供的再一優選基因比對處理方法中，所說的4種突變類型為插入I、刪除 D、轉換TRS和顛換TRV。本發明中的DNA序列比對過程中，鹼基可能的互配方式只有4種情況(1)匹配 (即A-A，T-T, C-C, G-G)。(2)插入I (Insertion)在序列X的某個位置插入了一個鹼基。 (3)缺失D (Deletion)在序列X的某個位置缺失了一個鹼基。(4)錯配(即:A-C, C-A, A-T, T-A, A-G, G-A, C-T, T-C, C-G, G-C, T-G, G-T)；錯配又分為 2 種情況A_G，C-T, G-A, T-C 稱為 轉換(TRanSition)；其餘，A_C，A_T，G_C，G_T，C_A，T_A，C_G，T-G 稱為顛換(TRansVersion)。 前者簡稱TRS，後者簡稱TRV。匹配表示比對的序列位點沒有發生突變。不匹配的都表示有了突變。由上可見， 有I、D、TRS、TRV等4種突變。本發明中單比特化表示方法為用一組2進位數表示基因的鹼基，其中，只有一位 是『1』。基因鹼基的這種表示方法在本發明中稱為單比特化表示法。有A，T，C，G等4種基 因鹼基，在計算機中用ASCII碼表示，每個鹼基用1個字節，8位，來表示。而本發明提出用 4位來表示=A用「0001，，表示，T用「0010」表示，C用「0100」表示，G用「 1000」表示。4位 中只有1位是『1』，故稱為單比特化表示法。下面可以看到，它對簡化比對邏輯有重要作用。單比特化可在FPGA中實現，下面是用VHDL硬體描述語言完成的一個設計Process (RST, elk)beginif RST=' 0' thenSEQ_X < = 「 0000 「；elsif elk' event and elk =' 1' thenif START =' 1' thenif SEQ_X = A thenQX< = 〃 0001〃 ；elsif SEQ_X = T thenQX < = " 0010〃 ；
elsif SEQ_X = C thenQX< = 〃 0100〃 ；elsif SEQ_X = G thenQX< = 〃 1000〃 ；end if ；end if ；end if ；end process ；其中，START是啟動信號；SEQ_X是以ASCII碼表示的鹼基變量；QX是以「單比特 化」表示的鹼基變量。每個clk(時鐘周期)可完成1個鹼基的轉換。本發明提出了基於硬體比對算法的基因比對處理方法。雖然也是基於FPGA實現， 但採用的比對算法不同於傳統的比對算法。本發明的硬體比對算法，是直接採用布爾邏輯 精確地表示各種基因突變規則，來識別各種基因突變，與現有的基因比對算法有本質區別。 而且在本發明中，硬體電路不是單純用於比對，也用於加快比對運算速度。
具體實施例方式本發明的具體結構是一塊PCB板，除了有一塊ALTERA公司的FPGA器件之外，還有 電源，晶振，配置器件，USB接口，安裝在一個機箱內。在機箱面板上有開關、RST按鈕和指 示燈等。USB接口用於和微機(或PC機)相連。在微機上有人機界面，也就是用戶的軟體 操作平臺。用戶通過「動態聯編庫DLL (dynamic linking library) 」提供的函數來實現本 「基因比對處理方法」。本發明提供的處理方法的比對過程為第一步，將要比對的基因序列輸入FPGA器 件；第二步，FPGA器件收到基因序列之後，用單比特表示鹼基；用布爾邏輯表示基因的突變 規則，用包括門電路和寄存器的FPGA器件實現比對計算；第三步，用位置計數器和突變計 數器記錄突變的類型和數量，結束時將記錄發送給上層軟體；上層軟體計算處理後將結果 顯示在屏幕上。另外，還可顯示彩色的基因圖譜等信息。第二步比對算法具體描述為1)基因比對算法邏輯設計2條經過「單比特化」轉換後的基因序列QX和QY，分別保存在2個FIFO (先進先 出)存儲器中。當比對時，每個時鐘周期(我們的實驗環境時鐘頻率為100MHz，時鐘周期為 10ns)，從2個FIFO存儲器中各讀出一個鹼基，又逐個時鐘地分別而同時地流入2條n級流 水線寄存器中。大多數的時間裡，2個鹼基匹配，1個時鐘即可完成識別。如不匹配就說明 基因有了突變，需要上述的2條流水線寄存器來處理。按照基因突變規則設計的布爾邏輯 可以識別基因突變的類型。有了流水線，識別基因突變類型的操作不會中斷讀入鹼基的工 作。因此，基因比對和讀入鹼基同時在工作，一旦序列從頭到尾讀完鹼基後，比對也就同時 完成了。計算時間與序列長度成線性關係。(a) 「匹配」的比對算法設有2條基因序列依次為SEQ_X和SEQ_Y，首先要轉換為單比特化表示，分別為QX 和QY，由4位表示。例如，QX的4位依次為QX (0)，QX (1)，QX (2)，QX (3)。4位中，只有1位 是1。如果QX(0)為1，QX就表示A ；如果QX(1)為1，QX就表示T ；如果QX(2)為1，QX就表示C;如果QX(3)為1，QX就表示G。比對「匹配」邏輯可以用1個「與門」來實現。「匹配」 的英文詞為(Match)，如果QX和QY都是A，可表示如下M0-AA = QX (O)AND QY (0)；其實，同是T，同是C，同是G都可表示匹配。故有M0-TT = QX(1)AND QY(1)；M0-CC = QX(2)AND QY(2)；MO-GG = QX(3)AND QY(3)；因此，QX和QY完整的比對匹配算法是MO = MO-AA OR MO-TT OR MO-CC OR MO-GG ；以3級流水線為例，流水線可表示為REG_X 1、REG_X2、REG_X3，以及 REG_Y 1、REG_Y2、REG_Y3，同理，REG_X1 and REG_Y1完整的比對匹配算法是Ml = Ml-AA OR Ml-TT OR Ml-CC OR Ml-GG ；同理，REG_X2 and REG_Y2完整的比對匹配算法是M2 = M2-AA OR M2-TT OR M2-CC OR M2-GG ；同理，REG_X3 and REG_Y3完整的比對匹配算法是M3 = M3-AA OR M3-TT OR M3-CC OR M3-GG ；(b) 「突變」的比對算法①插入(Insertion)如下表 2條基因序列基本相同，只是上面一條QX的第4位點插入了 1個G，後面的各位依 次後移。2條基因序列逐位比對時，前3位相同，沒有「突變」。第4位開始，其QX和QY不 同，就是遇到了「突變」QX:GATGCACGTIII / / / / /QY:GATCACGT可見，QX的第4位的G與QY的第4位C不同，但是，其第5位C與QY的第4位的 C卻相同。而且，以後的各位也如此。這也是識別「插入」必需的條件。可是，QX和QY經常 在變化，故需要流水寄存器來幫助。在REG_X1、REG_X2、RG_X3,以及REG_Y1、REG_Y2、REG_ Y3中，保留著不同時刻的鹼基狀態。有了這些鹼基狀態，才能確定是遇到了什麼類型的「突變」。以「插入」為例，表示如下 根據上述「匹配」的比對算法MO = MO-AA OR MO-TT OR MO-CC OR MO-GG其不同 時刻的邏輯運算值可由QX與QY的值生成M0。如表中第4行，在時刻1，2，3，由於QX與QY 相同，M0 = 『1，。在時刻4，由於QX與QY不同，MO = 『0，。(MO = 『0，)就成為突變的時間
標誌o為了確定這個突變是「插入」，還要看QX在時刻4與QY在時刻5是否相同，這要等 下一拍才行。到了下一拍，QX在時刻4的C已經移到REG_Y1。而且，(M0 = 『0』)也移了一 拍，突變的時間標誌變成了(M1 = 『0』)。故確定這個突變是「插入」的條件有2個。(Ml = 『0，)上面已介紹；QX和REG_Y1都是C的條件是:QX(2)and REG_Y1 (2)。同理，還應考慮都 是A，T和G的情況。最後，在(Ml = 0)的時刻，判別「插入」的比對算法為M01 < = (QX (0) AND REG_Y1(0)) OR (QX(1) AND REG_Y1(1)) OR (QX (2) ANDREG_Y1(2))OR(QX(3)AND REG_Y1(3))；以此類推，逐拍還可生成突變的時間標誌(M2 = 0)和突變的時間標誌(M3 = 0)。根據插入的特點是Y序列的鹼基和X序列的後1位相同，故其比對算法還可以有 在(M2 = 0)的時刻，用M12<= (REG_X1(0) AND REG_Y2 (0)) OR (REG_X1 (1) AND REG_Y2(1)) 0R(REG_ XI(2) AND REG_Y2(2)) OR (REG_X1(3) AND REG_Y2(3))；
7
在(M3= 0)的時亥IJ，用M23 <= (REG_X2 (0) AND REG_Y3(0)) 0R(REG_X2(1) AND REG_Y3(1)) 0R(REG_ X2(2) AND REG_Y3(2)) OR (REG_X2 (3)AND REG_Y3(3))；以上可見，有3種可選的方案。由於出現突變的位置具有隨機性，在具體實現中可 靈活性地使用這3種方案。流水線級數可變，供複雜情況的應用。關於複雜情況的處理，是 屬於進一步優化的問題，尚待以後研究解決。②缺失(Deletion)如下表 2條基因序列基本相同，只是原來QX的第4位C缺失了，後面的依次前移1位。QX :G A T A C G TI I \ \ \ \QY :G ATCACGT根據缺失的特點是Y序列的鹼基和X序列的前1位相同，故比對算法為在(Ml= 0)的時刻，MlO < = (REG_X1 (0) AND QY(O)) OR (REG_X1 (1) AND QY(I)) 0R(REG_X1(2) ANDQY (2)) 0R(REG_X1(3)AND QY (3))；在(M2= 0)的時刻，M21 <= (REG_X2 (O)AND REG_Y1(0)) 0R(REG_X2(1) AND REG_Y1 (1))0R (REG_ X2(2) AND REG_Y1(2)) OR (REG_X2 (3) AND REG_Y1(3))；在(M3= 0)的時刻，M32 < = (REG_X3(0) AND REG_Y2(0)) OR (REG_X3(1) AND REG_Y2(1))0R (REG_ X3(2) AND REG_Y2(2)) OR (REG_X3(3) AND REG_Y2(3))；值得注意的是，雖然經過2-3級流水寄存器才能完成了比對，但這並不幹擾「讀鹼 基」的工作。實際上，只有遇到基因有突變時，流水寄存器才工作，不會影響總的比對時間。③轉換(TRS)如下表 兩條序列基本相同，只有第4位不同，C轉換成T 了。這與上述的I或D—樣。故 只判第4位還不能識別是什麼類型的突變。要等下一拍，如果沒有識別到I或D，才能確定 其為「轉換」。如上所說，還是在(Ml = 0)的時刻來識別判C和T均為『 1，的算法是，M-CT <= REG_X1(2)AND REG_Y1 (1)；類似地，還有TC，AG, GA等TRS的3種情況
QX:GATTACGTC GATAACGTC GATGACGTCQY:GATCACGTC GATGACGTC GATAACGTC它們對應的算法是，M-TC <= REG_X1 (I)AND REG_Y1 (2)；M-AG < = REG_X1 (O)AND REG_Y1 (3)；M-GA < = REG_X1 (3) AND REG_Y1 (0)；4項組合起來，M-TRS <= M-CT ORM-TC ORM-AG ORM—GA。④顛換(TRV)顛換與轉換的不同之處就在於組合不同。其8項的組合(即A-C，A-T, G-C, G-T, C-A, T-A, C-G, T-G)可按同樣的方法設計，故從簡。3)硬體實現以上邏輯有的用寄存器表示，有的用門電路表示，都可用VHDL語言描述，便於用 FPGA器件實現。用布爾邏輯精確表示各種序列比對規則，既包括匹配也包括突變，總的執 行過程也是一種流水形式。使得1對基因序列從頭到尾依次經過該比對邏輯，即可完成比 對。在比對過程中，有一個位置計數器，每比對1對鹼基時，計數器加1，用於給出位置信息。 還有4個計數器，分別記錄突變類型的信息。當發生突變時，信息都要記錄下來。比對結束 時，記錄發回上層軟體。上層軟體進行適當的處理後，把處理結果在屏幕上顯示，以滿足用 戶的需要。.技術人員從本發明提供的實施例可以，確認匹配的基因對1個時鐘周期即可給出 結果。突變的基因對的「轉換(TRS) 」和「顛換(TRV) 」需要3個時鐘周期給出結果。上述 事實說明，由於比對邏輯不影響「讀鹼基」的過程，所以也就不影響總的比對速度。「插入」 和「缺失」由於要調整2條基因恢復對齊，較快的序列要停止「讀鹼基」 1個時鐘周期。實際 上，突變的基因對數量是很少的，對總體影響不大。比對時間主要是「讀鹼基」的時間，用於 比對額外的時間只佔總時間很少的一部分。人類基因長度若按10億計，「讀鹼基」時間需 10億拍。每拍10ns，總計比對時間為100億ns. = 1000萬微秒=1萬毫秒=10秒。就 是說，人類基因比對的基本時間是10秒。用於比對額外的時間決定於「突變」的數量。即 使有10%的「突變」，實際比對時間也只有11秒。本發明提供的方法中全部比對電路佔用FPGA的硬體資源較少，只佔用Cyclone器 件總資源的5%，故一塊FPGA器件足夠支持多對基因序列的並行處理。最後應當說明的是，以上實施例僅用以說明本發明的技術方案，技術人員閱讀本 發明提供的技術方案後可以參照本發明實施例進行種種變更或修改，但這些變更或修改均 在申請待批的權利要求保護範圍之內。
權利要求
一種基於單比特化基因比對處理方法，包括兩條基因序列，其特徵在於比對步驟如下A、將需要比對的基因序列輸入到FPGA器件中；B、FPGA器件收到基因序列之後依次執行如下步驟B1、用單比特表示鹼基；B2、用布爾邏輯表示基因的突變規則，用包括門電路和寄存器的FPGA器件實現比對計算；C、位置計數器和突變計數器記錄突變的類型和數量，結束時將記錄發送給上層軟體；D、上層軟體計算處理後將結果顯示在屏幕上。
2.按照權利要求1所述的基因比對處理方法，其特徵在於所說單比特表示鹼基為4 位表示,鹼基A、T、C和G分別用0001,0010,0100和1000表示。
3.按照權利要求1所述的基因比對處理方法，其特徵在於所說FPGA器件通過2條3 級流水線來實現比對計算，所說2條流水線指正常流水線和突變流水線，所說3級流水線指 用以確定突變類型的三個寄存器比對過程。
4.按照權利要求1所述的基因比對處理方法，其特徵在於所說用布爾邏輯表示基因 的突變規則包含如下步驟B21、將輸入的基因序列進行邏輯與運算；B22、若與運算後輸出為1，則說明鹼基序列匹配，進行下一鹼基比對運算； B23、若與運算後輸出結果為0，則說明鹼基序列不匹配，比對流入突變流水線，通過3 級寄存器流水線判斷基因突變類型。
5.按照權利要求1所述的基因比對處理方法，其特徵在於所說流水線中均包含兩個 用於存放鹼基的寄存器。
6.按照權利要求1所述的基因比對處理方法，其特徵在於所說位置計數器有1個，用 來保存突變基因的位置；突變計數器有4個，分別為轉換計數器、顛換計數器、插入計數器 和缺失計數器，用來記錄4種突變類型的數量。
7.按照權利要求6所述的基因比對處理方法，其特徵在於所說的4種突變類型為插 入I、刪除D、轉換TRS和顛換TRV。
全文摘要
本發明提供了一種基於單比特化基因比對處理方法，該方法包括兩條基因序列，其比對步驟為將需要比對的基因序列輸入到FPGA器件中後用單比特表示鹼基，用布爾邏輯表示基因的突變規則，用FPGA器件實現比對計算，用位置計數器和突變計數器記錄突變的類型和數量，結束時將記錄發送給上層軟體，上層軟體計算處理後將結果顯示在屏幕上。利用本發明提供的方法，比對邏輯與「讀鹼基」同時工作，比對邏輯無需佔用額外的時間，比對計算的時間與序列的長度成線性關係，顯著提高了比對計算速度。
文檔編號G06F19/00GK101887493SQ20101024601
公開日2010年11月17日 申請日期2010年8月5日 優先權日2010年8月5日
發明者康繼昌, 徐烽濤 申請人:湖州瑞萬思信息技術有限公司