[發明專利]一種用一維細胞神經網絡檢測DNA序列相似度的方法

有效

• 申請號: 201310552472.3
• 申請日: 2013-11-08
• 公開（公告）號: CN103544406A
• 公開（公告）日: 2014-01-29
• 發明（設計）人: 紀祿平;郝德水;周龍;黃青君;尹力;楊潔
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F19/22
• 分類號: G06F19/22;G06N3/02
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種用一維細胞神經網絡檢測DNA序列相似度的方法，包括以下步驟：

（1）、設計一維細胞神經網絡基本模型

將單細胞進行鏈狀排列，各細胞序號依次用“…、i-1、i、i+1、…”來表示，其中的字母i表示細胞的排列序號；

該基本模型中細胞狀態用微分方程組來表示：

C∂xi(t)∂t=-xi(t)Rx+A⊗Yi(t)+B⊗Ui(t)+Iiyi(t)=f(xi(t))---(1)]]>

其中，方程組（1）中，t表示時間，x_i表示細胞i的狀態，A是反饋模板，B是控制模板，I_i、R_x和C分別是三個常量，f(x_i(t))是細胞狀態的輸出調制函數；Y_i(t)表示細胞i包括自己的鄰域輸出矩陣，U_i(t)表示細胞i包括自己的鄰域輸入，分別表示為：

Yi(t)=yi-1(t)yi(t)yi(t+1)Ui(t)=ui-1(t)ui(t)ui+1(t);]]>

細胞輸出調制函數f(x_i(t))的具體形態為：

yi(t)=f(xi(t))=12(|xi(t)+1|-|xi(t)-1|)---(2)]]>

（2）、構建一維對稱細胞神經網絡

用步驟（1）設計的一維細胞神經網絡模型，先分別生成主子網CNN1和從子網CNN2，再由二者構建一個一維對偶細胞神經網絡：

在一維對偶細胞神經網絡中，主子網CNN1是固定不動的，而從子網CNN2則是可以沿主子網CNN1平行移動，時間t每增加1，從子網CNN2移動一步，且從子網CNN2每次移動的距離等于主子網CNN1中兩個相連細胞之間的距離；主子網CNN1由細胞0、1、2、…、m-1組成，從子網CNN2由細胞0、1、2、…、n組成；

在一維對偶細胞神經網絡中，令C=1、R_x=1，則用以表示細胞狀態的微分

方程簡化為：

xi(t+1)=Σl∈L(i)A⊗Yl(t)+Σl∈L(i)B⊗Ul(t)+Ii---(3);]]>

時間T=t+1時，細胞i的輸出y_i(t+1)相應被重新定義為：

yi(t+1)=f(xi(t+1))=12(|xi(t+1)+1|-|xi(t+1)-1|)---(4)]]>

（3）、利用步驟（2）構建的一維對偶細胞神經網絡，對兩個待檢測相似度的DNA序列進行全局的堿基對齊；

3.1）、對偶細胞網絡的初始化

待匹配的兩個DNA堿基序列S₁和S₂的堿基數量分別為K₁和K₂，堿基序列的堿基代碼分別表示為S₁(k₁)和S₂(k₂)，且0≤k₁≤K₁-1和0≤k₂≤K₂-1，則主子網CNN1和從子網CNN2的細胞數量分別被初始化為K₁+1和K₂+1，即細胞數量m=K₁+1和n=K₂+1；

用u¹(i)和u²(j)表示主子網CNN1的第i個細胞輸入和從子網CNN2的第j個細胞輸入，則滿足0≤i≤K₁且0≤j≤K₂，主子網CNN1和從子網CNN2中各細胞的細胞輸入分別按公式（5）和公式（6）進行賦值：

其中，符號“*”表示細胞的輸入u設置為空值；

主子網CNN1中的另一個常量參數初始化賦值為I_i=2；主子網CNN1中使用到的反饋模板Α和控制模板B分別初始化為下列兩個常數矩陣：

A=[0?1?0]和B=[0?1?-1]；

此外，還要將主子網CNN1中細胞i，i=0,1,..,K₁，的初始狀態即t=0時均分別設置為x_i(0)=0、y_i(0)=0；主子網CNN1的第0個細胞和從子網CNN2第K₂個細胞對齊；

3.2）、迭代地計算主子網CNN1中細胞在各時刻的狀態和輸出

時間t每增加1，從子網CNN2沿主子網CNN1的排列需要增加方向移動一步；

對主子網CNN1，如果細胞i的正下方的那個細胞j_L存在，則選取其3個鄰域細胞即細胞i-1,i以及從子網CNN2中正處于i正下方的那個細胞j_L；在時間t，t=1,2,…,m+n-1時，當時間t和細胞序號i同時滿足條件1≤t≤m+n-1和1≤i≤m+1時，分別計算各細胞的最優狀態和最優輸出而如果細胞i的正下方的那個細胞j_L不存在，則不計算細胞最優狀態的和最優輸出值；

所述的最優狀態和最優輸出分別按下列公式計算：

xi‾(t)=max{xi-1(t-2)+2Ii,xi-1(t-1)-Ii,xi(t-1)-Ii}---(7)]]>

其中，函數max(...)表示求取輸入參數中的最大值，x_i-1(t-2)、x_i-1(t-1)和x_i(t-1)均按公式(3)進行計算；

3.3）、形成細胞的最優輸出矩陣

根據步驟3.2）計算得到主子網CNN1的所有細胞在各時刻的最優狀態和最優輸出，然后按照第1列為細胞1從t=1到n時刻最優輸出、第2列為細胞2從t=2到1+n時刻最優輸出、…、第m列為細胞m從t=m到m+n時刻最優輸出得到主網絡CNN1的最終的細胞最優輸出矩陣S_y；

3.4）、對兩個DNA序列的堿基進行全局對齊

根據步驟3.3）得到的最優輸出矩陣S_y,從矩陣左上角的元素開始，從左至右、從上至下遍歷矩陣，確定最優輸出矩陣S_y中值為1的矩陣元素位置，并將確定好的各元素按順序連接以形成堿基的對齊路徑P；

根據已確定好的堿基對齊路徑P，分三種情況對DNA堿基序列S₁和S₂進行操作：從第一個元素1開始，如果下一個1位于其下，則在序列S₁的當前位置插入符號“*”；如果下一個元素1位于其右側，則在序列S₂的當前位置插入符號“*”；如果下一個1剛好位于其右下位置，則不對S₂和S₂的當前位置做任何操作。

處理完成S_y的第一個元素后，按前述的三種情況繼續處理第二個元素，直到輸出矩陣S_y的全部值為1的元素全部都已經被處理完畢，此時S₂和S₂已按堿基的排列順序完成了全局對齊；

（4）、計算兩個DNA堿基序列序列S₂和S₂的全局相似度

定義序列S₂和S₂的全局相似度為SC(S₁,S₂)，則這兩個DNA堿基序列的全局相似度按如下公式進行計算：

SC(S1,S2)=2×NmatchLen(S1)+Len(S2)×100%---(9)]]>

其中，符號N_match表示兩個DNA堿基序列S₂和S₂經全局序列對齊以后，匹配成功的堿基對數量，Len(S₁)和Len(S₂)分別表示序列S₁和S₂的實際長度。