基因识别的综合优化算法及精确性分析

姜 林，刘湘伟

(电子工程学院，合肥 230037)



基因识别的综合优化算法及精确性分析

姜 林，刘湘伟

(电子工程学院，合肥 230037)

针对现有算法难以精确地确定基因外显子的2个端点，结合 “基于固定长度滑动窗口上频谱曲线的基因识别方法”、“基于DNA序列上“移动序列“信噪比曲线的基因识别方法”、“小波算法”3种方法，采用综合优化算法对基因进行识别，最后通过误差评估验证了算法的精确性。

综合优化算法；基因识别；误差评估；精确性

1 背景研究

对给定的DNA序列，如何识别出其中的编码序列(即外显子)也称为基因预测，是一个尚未完全解决的问题，也是当前生物信息学的一个最基础、最首要的问题。现在已经有一些研究者提出了识别基因的算法。目前利用信噪比的基因识别算法通常有2种：一种是固定长度窗口滑动法[1-2]；另一种是移动信噪比曲线识别法[3]。但由于DNA序列随机噪声的影响等原因，还很难“精确地”确定基因外显子区间的2个端点。鉴于上述原因，本文以“基于固定长度滑动窗口上频谱曲线的基因识别方法”和“基于DNA序列上“移动序列“信噪比曲线的基因识别方法”为基础，进而可创造性地研究小波算法，尝试解决DNA序列随机噪声的影响，可以比较精确地确定基因外显子区间的2个端点，进而通过分析对比“基于固定长度滑动窗口上频谱曲线的基因识别方法”、“基于DNA序列上“移动序列“信噪比曲线的基因识别方法”、“小波算法”和“综合优化算法”，建立误差评估函数，并运用图表形象地展示评估算法的结果。

2 生物基因识别综合优化算法的分析和研究

本文首先在“基于固定长度滑动窗口上频谱曲线的基因识别方法”和“基于DNA序列上“移动序列“信噪比曲线的基因识别方法”,2种方法的基础上，对算法结果的充分性和准确性进行了进一步的改进；进而创造性地将信号处理方面的小波算法运用到基因识别中，有效地去除了DNA序列中随机噪声的影响，比较精确地确定了基因外显子区间的2个端点。下面以所查基因数据为例来说明此算法。

2.1 基于固定窗口滑动法得出外显子大致区域

(1) 在参考文献中有此种方法的阐述，对基于固定长度滑动窗口上频谱曲线的基因识别方法的滑动进行MATLAB编写程序，实现算法；

(2) 对窗口按照FFT算法进行快速傅里叶变换，进而求出基因的功率谱；

(3) 通过MATLAB程序中的循环语句，实现窗口自动移动，实现算法的软件自动化；

(4) 对所研究的基因的功率谱进行归一化处理；

(5) 运用MATLAB软件作出基因的功率谱图像(见图1)。

图1 人类的基因序列的功率谱(1)

2.2 移动信噪比曲线法对区域进一步细化

(1) 对基于DNA序列上“移动序列”信噪比曲线的基因识别方法的移动进行MATLAB程序编写，实现算法；

(2) 通过MATLAB程序中的循环语句，使区域进行步长为3的变化，实现算法的软件自动化；

(3) 对所研究的基因序列区域进行快速傅里叶变换(FFT)，得到基因序列的功率谱图像(见图2)。

图2 人类的基因序列的功率谱(2)

因为DNA序列的信噪比移动曲线的峰、谷与基因外显子区间的端点也具有较“明显的”的对应关系。所以运用基于DNA序列上“移动序列”信噪比曲线的基因识别方法，可以对区域进一步精化，从而使区域范围更加准确，得出外显子的大致范围为：(4 554，5 109)，(5 256，5 583)，(7 419，7 974)。

2.3 小波算法的精确化处理

小波分解是时间和频率的局域变换，因而能有效地从信号中提取信息，通过伸缩和平移等运算功能对信号进行多尺度分析。实际中使用的是离散小波变换、工程上常用二进制小波变换。与标准傅里叶变换相比, 小波分析中所用到的小波函数具有不唯一性，即小波函数具有多样性。目前主要是通过用小波分析方法处理信号的结果与理论结果的误差来判定小波基的好坏，并由此选定小波基。

(1) 小波理论简介

设x(t)是平方可积函数,ψ(t)是基本小波或母小波(MW)函数,且满足容许条件：

(1)

则：

(2)

式中：ωx(a,b)为x(t)的小波变换式；b为位移，其值可正可负；上标*代表共扼。

这就称为x(t)的小波变换。

如果x(t)为信号函数，则小波变换是信号与小波函数的内积，是对信号满足一定附加条件的滤波，这种附加条件反映在小波函数及小波因子选择上。高频时使用小尺度a值，时轴上观察范围小，而频域上相当于用高频小波作细致观察；低频时使用大尺度a，时轴上考察范围大，而频域上相当于用低频小波作概貌观察[4]。利用小波变换所具有的这种数学显微镜特点和频域带通特性，把所有的信号分离出来，再进行分析研究。

(2) 基因小波变换模型的建立

在实际运用中，尤其在计算机实现时，一般采用离散小波变换。最常用的是二进小波变换，b=k×2-j，a=2-j，j,k∈Z，其小波序列为：

(3)

对任意平方可积函数y(t)来说，其离散小波变换(DWT)为：

(4)

对任意y(t)∈Vj，若yk为信号的离散采样数据，令cj,k=yk(应用中常以c0,k=yk作为计算的初始信号序列)，则有信号的多分辨率分析公式为：

(5)

(6)

式中：cj,k为信号的逼近信号；dj,k为信号的细节。

相应地，有基因小波变换模型为：

(7)

可见，一个信号可以由小波进行系数重构。本文使用小波算法进行信号重构，以消除DNA序列随机噪声的影响，较精确地确定了基因外显子区间的2个端点。

(3) 利用基因小波变换模型进行基因识别(如图3)

图3 小波基因识别流程

对DNA序列数值化映射后得到{uA[n]}、{uG[n]}、{uC[n]}、{uT[n]}，使用MATLABTOOLBOXES中的WAVELET，对数据进行相关的小波变换处理，并与FFT结果比较，得到外显子的相应区间：(4 562，5 047)，(5 253，5 427)，(7 445，7 983)。

3 生物基因识别算法的精确性分析

在基因的识别算法中可能存在一定的误差，为此对上述建立的基因识别综合算法模型进行了逐步深入的研究，并建立误差评估函数，用数据形象证明了算法逐步优化的过程，最终确定算法的高效性。

3.1 基因识别算法的误差评估函数

误差评估函数如下：

；i=0,1,2

(8)

所得到的函数值hi越大，表明在确定外显子区域时的误差越大。

对于一段DNA序列，可能有N段外显子，则对于这段DNA序列来讲，对外显子的识别误差为：

(9)

3.2 精确性分析

(1) 在所查数据中可以得到人类基因序列中外显子的准确位置：(4 577，4 996)，(5 251，5 398)，(7 458，7 996)。

(2) 对单独使用“基于固定长度滑动窗口上频谱曲线的基因识别方法”、 “基于DNA序列上“移动序列“信噪比曲线的基因识别方法”、“小波算法”对外显子的识别与使用“综合优化算法”的结果比较，得到数据如表1所示。

表1 4种算法对外显子识别结果与准确值的对比

表1中，算法1为“基于固定长度滑动窗口上频谱曲线的基因识别方法”；算法2为“基于DNA序列上“移动序列“信噪比曲线的基因识别方法”；算法3为“小波算法”；算法4为“综合优化算法”。

(3) 运用误差评估函数得到每种算法对单个外显子以及整个DNA序列的误差如表2所示。

表2 误差评估分析表

4 结束语

(1) 数值越大，说明该种算法的误差越大。

(2) 从表中可以看出，对每一列进行对比时，通过新算法的逐步优化，得到的结果也层层推进，逐步接近正确值，误差越来越小，说明精确度越来越高，通过新算法可以使误差保持在0.1 左右。

(3) 对每一行进行对比时，发现区域越小(尤其100左右时)，误差越大，说明仅通过信噪比对区域过小的外显子序列进行区分是不精确的。

[1] 王玉.基于傅里叶技术快速预测DNA序列编码区[J].电子科技大学学报,2006,35(5):837-840.

[2]BerrymanMJ,AlisonA.Reviewofsignalprocessingingenetics[J].FluctuationandNoiseLetters,2005,5(4):13-35.

[3]YinC,YauS.Predictionofproteincodingregionsbythe3-baseperiodicityanalysisofaDNAsequence[J].JournalofTheoreticalBiology，2007，2(47):687-694.

[4] 王正林.精通MATLAB[M].北京：电子工业出版社,2009.

Analysis of Integrated Optimized Algorithm and Accuracy of Gene Identification

JIANG Lin,LIU Xiang-wei

(Electronic Engineering Institute，Hefei 230037，China)

Because existing algorithms can not accurately judge the two points of expressed region of gene,this paper combines three methods:gene identification method based on spectrum curve of slip window with fixed length,gene identification method based on mobile sequence signal-to-noise ratio (SNR) curve of DNA sequence,wavelet algorithm,uses integrated optimized algorithm to identify the gene,finally validates the accuracy of the algorithm through error estimation.

integrated optimized algorithm;gene identification;error estimation;accuracy

2014-09-09

TP391.9

A

CN32-1413(2015)01-0080-04

10.16426/j.cnki.jcdzdk.2015.01.019