没有合适的资源?快使用搜索试试~ 我知道了~
动态规划-DNA 序列表示及基因识别方法研究.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 98 浏览量
2022-05-02
07:06:25
上传
评论
收藏 1.57MB PDF 举报
温馨提示
试读
54页
动态规划-DNA 序列表示及基因识别方法研究.pdf
资源推荐
资源详情
资源评论
1
参赛密码
(由组委会填写)
第
第
九
九
届
届
“
“
华
华
为
为
杯
杯
”
”
全
全
国
国
研
研
究
究
生
生
数
数
学
学
建
建
模
模
竞
竞
赛
赛
题 目 DNA 序列表示及基因识别方法研究
摘 要:
本文就 DNA 序列表示及基因识别算法实现的相关问题进行了研究,取得
了以下几方面的成果。
1. 功率谱与信噪比的快速算法
针对 Voss 映射,给出了计算基因序列功率谱或信噪比的快速 Fourier
变换和 AR 模型,仿真实验结果表明,计算效率有所提升。经过理论
推导,建立了功率谱、信噪比与 DNA 序列中核苷酸出现的频次之间的
关系,即为 SNR-F 公式:
CG
AT
A C G T
NN
NN
R R R R R
N N N N
利用该公式,计算功率谱与信噪比将不再需要离散 Fourier 变换等计算
量较大的运算,只需要对 DNA 序列中核苷酸出现的频次进行统计,然
后进行简单的数值运算即可,有效提升了功率谱与信噪比的计算效率。
推导出了 Z-curve 映射的功率谱与信噪比和 Voss 映射下的功率谱与信
噪比之间的数值关系,即为:
4
z
EE
和
z
RR
并从理论基础、生物学意义和特征三个方面对 Z-curve 映射和 Voss 映
射进行了对比分析,刻画出了两种映射之间更深层次、更全面的关系。
经过理论推导,给出了一般的实数映射下功率谱、信噪比的快速计算
公式,将其功率谱、信噪比的计算简化为核苷酸出现频次的统计和简
单数值运算,极大简化了实数映射下功率谱与信噪比的计算。
2. 对不同物种类型基因的阈值确定
2
本文结合重采样技术,提出了最佳阈值确定算法,能为每一个特定种
类的生物推测其最佳阈值。模型能够针对不同生物基因的结构特征,
启发式地为其推断出一个最佳的预测阈值。仿真实验结果表明,附件
中所给的人和鼠类生物基因预测的最佳阈值为 1.7773,200 个哺乳动物
类的基因预测的最佳阈值为 2.18。在合理确定窗口大小的基础上,利
用该最佳阈值能显著提高基于功率谱分析方法的基因预测精度,同时
还可用来预测该生物目前尚未标注确认的其它基因。
3. 基因识别算法的实现
针对基因识别算法的设计与实现问题,本文首先利用基于 AR 模型重
采样的基因预测方法对附件中给出的 6个未被注释的 DNA序列的编码
区域进行了预测。然后,结合数字滤波器与信噪比快速计算公式,提
出了一种基于 SNR-F 的基因识别模型。该模型克服了现有 Fourier 方
法对 DNA 序列长度的限制,并且能够提高实现效率。最后,利用该模
型对未被注释的 DNA 序列的编码区域进行了预测。两种预测方法相结
合有助于提高基因预测的精度,同时使后期基因识别更具有针对性。
4. 延展性问题
针对目前常用的基因识别算法对特征选取的主观性,建立了基因识别
特征的动态筛选模型。该模型在训练中充分选取基因的多类特征作为
候选特征,构造编码区与非编码区的正负数据集,运用特征筛选方法
在数据集中提取主特征,以达到优化特征集、减少冗余度的目的。同
时,模型用组合向量的方式实现多类特征的融合,将序列转换成特征
空间中的向量,通过利用判别分析的方法达到识别的目的。特征的筛
选和组合提高了基因识别算法的合理性和信息利用率,预测精度达到
了 98%以上,高于已有算法的预测精度。
Z-曲线的提出表明利用几何工具可以有效地分析 DNA 序列,受此启
发,本文基于改进的基于 DNA 序列的“四线”图,提出了基于改进“四
线”图的 DNA 序列突变分析模型,为检测基因突变提供模型基础。
随着人类基因组计划的顺利完成,基因识别已成为生物信息学中最基础、
最首要的问题。本文就基因识别方法的相关问题进行了深入探讨,提出了一些
新的思路,期待有益于基因识别领域的后续研究。
关键词:基因识别,功率谱,信噪比,AR 模型,阈值,重采样
1
一、问题背景
DNA 是生物遗传信息的载体,DNA 序列由腺嘌呤(Adenine,A),鸟嘌呤
(Guanine,G),胞嘧啶(Cytosine,C),胸腺嘧啶(Thymine,T)这四种核
苷酸(nucleotide)符号按一定的顺序连接而成。其中带有遗传讯息的 DNA 片
段称为基因(Gene)。其他的 DNA 序列片段,有些直接以自身构造发挥作用,
有些则参与调控遗传讯息的表现。在真核生物的 DNA 序列中,基因通常被划
分为许多间隔的片段,其中编码蛋白质的部分,即 编码序列(Coding Sequence)
片段,称为外显子(Exon),不编码的部分称为内含子(Intron)。
对大量、复杂的基因序列的分析,传统生物学解决问题的方式是基于分子
实验的方法,其代价高昂。随着世界人类基因组工程计划的顺利完成,通过物
理或数学的方法从大量的 DNA 序列中获取丰富的生物信息,对生物学、医学、
药学等诸多方面都具有重要的理论意义和实际价值,也是目前生物信息学领域
的一个研究热点。
对给定的 DNA 序列,怎么去识别出其中的编码序列(即外显子),也称为
基因预测,是一个尚未完全解决的问题,也是当前生物信息学的一个最基础、
最首要的问题。在目前基因预测研究中,采用信号处理与分析方法来发现基因
编码序列受到广泛重视。通过对 DNA 序列进行 Voss 映射,可以发现,对于同
一段 DNA 序列,其外显子与内含子序列片段的功率谱通常表现出不同的特性:
外显子序列具有频谱 3-周期性而内含子没有。频谱峰值特征的发现,或者频谱
与信噪比概念的引入,有助于探测、预报一个尚未被注释的完整的 DNA 序列
的所有基因编码序列(外显子)片段。已经有一些研究者提出了识别基因的算
法,目前利用信噪比的基因识别算法通常有两种:固定长度窗口滑动法和移动
信噪比曲线识别法。
二、模型假设
1.题目中所列数据均真实可靠且具有较强的代表性;
2.在解决前三个问题的过程中不考虑基因突变问题;
3.不考虑软件工具在数据处理及图形绘制中的误差。
三、符号说明
DFT:离散 Fourier 变换
FFT:快速 Fourier 变换
[]
b
un
:DNA 指示序列
[ ]
b
U k
:Fourier 变换序列
()P
:功率谱函数
更多数学建模资料请关注微店店铺“数学建模学习交流”
https://k.weidian.com/RHO6PSpA
2
R:信噪比
2
:方差
*
a
:
a
的共轭
()Hz
:系统转移函数
:误差功率
四、问题一模型的建立与求解
问题一:
(1)对于很长的 DNA 序列,在计算其功率谱或信噪比时,离散 Fourier 变
换(DFT)的总体计算量仍然很大,会影响到所设计的基因识别算法的效率。能否
对 Voss 映射,探求功率谱与信噪比的某种快速计算方法?
(2)在基因识别研究中,为了通过引入更好的数值映射而获取 DNA 序列
更多的信息,除了上面介绍的 Voss 映射外,实际上人们还研究过许多不同的数
值映射方法。例如,著名的 Z-curve 映射。试探讨 Z-curve 映射的频谱与信噪比
和 Voss 映射下的频谱与信噪比之间的关系;
(3)此外,能否对实数映射,如:
0, 1, 2, 3A C G T
,也给出功
率谱与信噪比的快速计算公式?
问题分析:
对 Voss 映射,功率谱与信噪比的快速计算方法是多种多样的,从思路上,
我们先后尝试了两种方法,分别是引入快速 Fourier 变换和 AR 模型,算法效率
有了有效提升,但提升的效果并不显著,这引导我们从理论推导上简化功率谱与
信噪比的计算公式,建立功率谱、信噪比与 DNA 序列中核苷酸出现的频次之间
的关系,从而彻底简化功率谱与信噪比的计算。
4.1 和 4.2 小节将分别对快速 Fourier 变换和 AR 模型进行描述。在 4.3 小节,
本文将重点给出功率谱、信噪比与 DNA 序列中核苷酸出现的频次之间的关系。
基于此,4.4 和 4.5 小节将分别讨论 Z-curve 映射和 Voss 映射的关系及实数映射
下功率谱与信噪比的快速计算公式。
4.1 快速 Fourier 变换
依据材料所述,对于很长的 DNA 序列,在计算其功率谱或信噪比时,首先
要对 DNA 的指示序列做离散 Fourier 变换(DFT)
2
1
0
[[] ] , 0,1, , 1
nk
N
j
N
bb
n
U k u n e k N
(4.1)
但是,上述 DFT 的计算量太大,很难高效进行基因识别。因此,本文首先
采用快速 Fourier 变换(FFT)对功率谱或信噪比的计算方法进行改进,FFT 并不是
一种新的变换,而是 Cooley 和 Tukey 于 1965 年提出的计算 DFT 的一种快速算
法,此算法将 DFT 的运算量减少了几个数量级。
3
在利用 DFT 计算式(4.1)时,算出全部
N
点
[ ]
b
U k
共需次
2
N
复数乘法和
( 1)NN
次复数加法,即计算量是与
2
N
成正比的,DFT 直接变换的计算复杂度
是
2
()ON
。FFT 的基本思想是将大点数的 DFT 分解为若干个小点数 DFT 的组合,
从而减少运算量。FFT 可以计算出与 DFT 直接计算相同的结果,但只需要
( log )O N N
的计算复杂度。通常,FFT 要求
N
能被因数分解,但不是所有的快速
Fourier 变换都要求
N
是合数,对于所有的整数
N
,都存在复杂度为
( log )O N N
的
快速算法。因此,对于本题目中的能够被 3 整除的整数
N
,利用 FFT 可将式(4.1)
的计算复杂度降至
( log )O N N
,从而相应提高了功率谱与信噪比的计算效率。
本文不再对FFT的具体算法进行描述,MATLAB工具中也已经提供了进行
FFT计算的相关函数。利用MATLAB 2011a,本文对题目中的酵母基因DNA序列
频谱3-周期性进行了验证,在剔除
0k
处(实际上,此处的数值在信号处理与
分析系统中的意义为时域数据的直流分量,对于研究DNA编码序列而言为噪声
信号)的数据后,所得结果与题目中图3所示一致。
然而,功率谱及信噪比的计算方式并不仅局限于利用Fourier变换一种方法来
实现,本文接下来主要讨论不利用Fourier变换进行功率谱及信噪比的计算方法。
4.2 AR 模型
在用DFT算法计算功率谱及信噪比时,其存在固有的缺陷,比如存在泄漏误
差和混迭误差,分辨率低,不适于处理短数据,谱线不平滑,起伏剧烈,难以拟
合出光滑曲线等。针对经典谱估计的分辨率低和方差性能不好等问题,为此人们
提出参数谱方法(现代功率谱估计)。参数谱估计方法是通过观测数据估计参数
模型再按照求参数模型输出功率的方法估计信号功率谱。
参数谱估计的主要方法有最大熵谱分析法(AR模型法)、Pisarenko谐波分解
法、Prony提取极点法、Prony谱线分解法以及Capon最大似然法等。其中AR模型
应用较多,具有代表性。
4.2.1 AR 模型的公式表达
我们首先介绍 AR 模型的一般模型——ARMA 模型。
ARMA 模型
[1]
功率谱的数学表达式为:
2 2 2
11
( ) |1 | |1 |
pp
j j k j k
k k k
kk
P e b e a e
(4.2)
其中
2
是白噪声的方差,
()
j
k
Pe
为功率谱密度,
k
a
和
k
b
为模型参数。
如果 ARMA 模型的参数
12
, , ,
p
b b b
全为 0,就演化为 AR 模型:
22
1
( ) |1 |
p
j j k
kk
k
P e a e
(4.3)
如果 ARMA 模型的参数
12
, , ,
p
a a a
全为 0,就演化为 MA 模型:
剩余53页未读,继续阅读
资源评论
普通网友
- 粉丝: 12w+
- 资源: 9337
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功