基因识别问题及其算法实现.doc

基因识别问题及其算法实现 一、背景介绍 DNA是生物遗传信息的载体脱氧核糖核酸（Deoxyribonucleic acid缩写为）DNA分子是一种长链聚合物DNA序列由腺嘌呤（Adenine, A），鸟嘌呤（Guanine, G），胞嘧啶（Cytosine, C），胸腺嘧啶（Thymine, T）这四种核苷酸nucleotide）符号按一定的顺序连接而成。带有遗传讯息的DNA片段称为基因（Gene）其他的DNA序列，有些直接以自身构造发挥作用，有些则参与调控遗传讯息的表现。在真核生物的DNA序列中，基因被划分为许多间隔的片段（），其中编码蛋白质的部分编码序列（Coding Sequence）称为外显子（Exon），不编码的部分称为内含子（Intron）。外显子在DNA序列剪接（Splicing）后仍会被保存下来，并可在 图1真核生物DNA序列（基因序列）结构示意图 蛋白质合成过程中被转录transcription）、复制replication）而合成为蛋白质（图）。DNA序列通过遗传编码来储存信息，指导蛋白质的合成，把遗传信息准确无误地传递到蛋白质（protein）上并实现各种生命功能。 图2蛋白质结构示意图 对复杂的基因序列的分析，传统生物学解决问题的方式是实验的。诺贝尔奖获得者W.吉尔伯特（Walter Gilbert，1932美，第一制备出混合脱氧核糖核酸1991年曾经指出：“现在，基于全部基因都将知晓，并以电子可操作的方式驻留在数据库中，新的生物学研究模式的出发点应是理论的。一个科学家将从理论推测出发，然后再回到实验中去，追踪或验证这些理论假设。” 随着人类基因组计划的顺利完成，通过物理或数学的方法从大量的DNA序列中获丰富的生物信息，对生物学、医学、药学等诸多具有重要的理论意义和实际价值，目前生物信息学领域的一个研究热点对给定的DNA序列，怎么去识别出其中的编码序列（即外显子），也称为基因预测，是一个尚未完全解决的问题，也是当前生物信息学的一个最基础、最首要的问题。 基因预测问题的一类方法是统计的/GENSCAN.html提供的基因识别软件GENSCAN（由斯坦福大学研究人员研发的、可免费使用的基因预测软件）,主要就是基于隐马尔科夫链（HMM）方法。但是，它预测人的基因组中有45000个基因，相当于现在普遍认可数目的两倍。另外，统计预测方法通常需要将已知DNA序列作为训练数据集确定模型中的参数，从而提高模型的预测水平，长度（即核苷酸符号个数，又称碱基对（Base Pair）长度，bp）为N的任意DNA序列，可表达为 即A、T、G、C的符号序列：。现对于任意确定的，令 ， 称之为Voss映射[5]，于是生成相应的0-1序列（即二进制序列）：， ()。 例如，假设给定的一段DNA序列片段为S = ATCGTACTG，则所生成的四个0-1序列分别为： ：； ：； ：； ：。 这样产生的四个数字序列又称为DNA序列的指示序列(indicator Sequence)。 2. 频谱3-周期性 为研究DNA编码序列（外显子）的特性，对指示序列分别做离散Fourier变换(DFT) (1) 以此可得到四个长度均为N的复数序列，。计算每个复序列的平方功率谱，并相加则得到整个DNA序列的功率谱序列： (2) 对于同一段DNA序列，其外显子与内含子序列片段的功率谱通常表现出不同的特性 图3 编号为BK006948.2的酵母基因DNA序列的功率谱（因为对称性，实际这里只给出了功率谱图的一半）。 (a) 上图是基因上一段外显子(区间为[81787，82920]，长1134bp) 对应的指示序列映射的功率谱，它具有3-周期性；(b) 下图是基因上一段内含子（区间为[96361,97551]，长1191bp）的指示序列的功率谱，它不具有3-周期性。 可以看到：外显子序列的功率谱曲线在频率处，具有较大的频谱峰值(Peak Value)，而内含子则没有类似的峰值。这种统计现象被称为碱基的3-周期(3-base Periodicity) [2][3]。 记DNA序列的总功率谱的平均值为 (3) 而将DNA序列在特定位置，即处的功率谱值，与整个序列的总功率谱的平均值的比率称为DNA序列的“信噪比”（Signal Noise Ratio，， (4) DNA序列的信噪比值的大小，既表示频谱峰值(Peak Value)的相对高度，也反映编码或非编码序列3-周期性的强弱。 信噪比大于某个适当选定的阈值（比如），是DNA