一种用一维细胞神经网络检测DNA序列相似度的方法

摘要

本发明公开了一种用一维细胞神经网络检测DNA序列相似度的方法，首先设计出一维细胞神经网络基本模型，然后利用这种模型建构一个一维的对偶细胞神经网络；再用两个待检测的DNA序列信息对该网络进行初始化，网络运行过程中，记录各时刻网络中的细胞状态和输出，据此形成最优输出矩阵；再对最优输出矩阵中的元素进行遍历，从而确定最佳的对齐路径；最后根据对齐路径对两个序列进行空格插入操作以便将两个序列全局对齐；序列对齐后，再根据对齐的碱基数量和总的碱基数量来计算其全局相似度。经过测试对比表明，本发明在保证检测准确的基础上，对于长度较长的DNA序列，所需的计算时间比现有方法明显有较大幅度地减少。

主权项

1.一种用一维细胞神经网络检测DNA序列相似度的方法，包括以下步骤：（1）、设计一维细胞神经网络基本模型将单细胞进行链状排列，各细胞序号依次用“…、i-1、i、i+1、…”来表示，其中的字母i表示细胞的排列序号；该基本模型中细胞状态用微分方程组来表示：$\left\{\begin{array}{c}C\frac{{\partial x}_i\left(t\right)}{\partial t}=-\frac{x_i\left(t\right)}{R_x}+A\otimes Y_i\left(t\right)+B\otimes U_i\left(t\right)+I_i\\ y_i\left(t\right)=f\left(x_i\left(t\right)\right)\end{array}\right.---\left(1\right)$其中，方程组（1）中，t表示时间，x_i表示细胞i的状态，A是反馈模板，B是控制模板，I_i、R_x和C分别是三个常量，f(x_i(t))是细胞状态的输出调制函数；Y_i(t)表示细胞i包括自己的邻域输出矩阵，U_i(t)表示细胞i包括自己的邻域输入，分别表示为：$\begin{array}{cc}{Y}_i\left(t\right)=\left\{\begin{array}{c}{y}_{i-1}\left(t\right)\\ y_i\left(t\right)\\ y_i(t+1)\end{array}\right.& \end{array}{U}_i\left(t\right)=\left\{\begin{array}{c}{u}_{i-1}\left(t\right)\\ u_i\left(t\right)\\ u_{i+1}\left(t\right)\end{array}\right.;$细胞输出调制函数f(x_i(t))的具体形态为：$y_i\left(t\right)=f\left(x_i\left(t\right)\right)=\frac{1}{2}\left(\right|x_i\left(t\right)+1|-|x_i\left(t\right)-1\left|\right)---\left(2\right)$（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，则用以表示细胞状态的微分方程简化为：$x_i(t+1)=\underset{l\in L\left(i\right)}{\Sigma }A\otimes Y_l\left(t\right)+\underset{l\in L\left(i\right)}{\Sigma }B\otimes U_l\left(t\right)+I_i---\left(3\right);$时间T=t+1时，细胞i的输出y_i(t+1)相应被重新定义为：$\begin{array}{c}{y}_i(t+1)=f\left(x_i(t+1)\right)\\ =\frac{1}{2}\left(\right|x_i(t+1)+1|-|x_i(t+1)-1\left|\right)\end{array}---\left(4\right)$（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不存在，则不计算细胞最优状态的和最优输出值；所述的最优状态和最优输出分别按下列公式计算：$\overline{x_i}\left(t\right)=\max \{x_{i-1}(t-2)+{2I}_i,x_{i-1}(t-1)-I_i,x_i(t-1)-I_i\}---\left(7\right)$其中，函数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碱基序列的全局相似度按如下公式进行计算：$\mathrm{SC}(S_1,S_2)=\frac{2\times N_{\mathrm{match}}}{\mathrm{Len}\left(S_1\right)+\mathrm{Len}\left(S_2\right)}\times 100\%---\left(9\right)$其中，符号N_match表示两个DNA碱基序列S₂和S₂经全局序列对齐以后，匹配成功的碱基对数量，Len(S₁)和Len(S₂)分别表示序列S₁和S₂的实际长度。