当前位置： >>
基因识别问题及其算法实现
基因识别问题及其算法实现一、背景介绍 DNA是生物遗传信息的载体，其化学名称为脱氧核糖核酸（Deoxyribonucleic acid，缩 写为DNA）DNA分子是一种长链聚合物， 。 DNA序列由腺嘌呤 （Adenine, A）鸟嘌呤 ， （Guanine, G） ，胞嘧啶（Cytosine, C） ，胸腺嘧啶（Thymine, T）这四种核苷酸（nucleotide）符号按一定 的顺序连接而成。其中带有遗传讯息的DNA片段称为基因（Gene） （见图1第一行） 。其他的 DNA序列片段，有些直接以自身构造发挥作用，有些则参与调控遗传讯息的表现。 在真核生物的DNA序列中，基因通常被划分为许多间隔的片段（见图1第二行） ，其中编 码蛋白质的部分，即编码序列（Coding Sequence）片段，称为外显子（Exon） ，不编码的部 分称为内含子（Intron） 。外显子在DNA序列剪接（Splicing）后仍然会被保存下来，并可在 基因（Gene） DNA 序列外显子(Exon) 内含子(Intron)图 1 真核生物 DNA 序列（基因序列）结构示意图蛋白质合成过程中被转录（transcription） 、复制（replication）而合成为蛋白质（见图 2） 。 DNA 序列通过遗传编码来储存信息，指导蛋白质的合成，把遗传信息准确无误地传递到蛋 白质（protein）上去并实现各种生命功能。 基因（Gene） DNA 序列 剪接、转录、 复制 蛋白质序列图 2 蛋白质结构示意图对大量、复杂的基因序列的分析，传统生物学解决问题的方式是基于分子实验的方法， 其代价高昂。诺贝尔奖获得者 W.吉尔伯特（Walter Gilbert，1932―；【美】，第一个制备 出混合脱氧核糖核酸的科学家）1991 年曾经指出：“现在，基于全部基因序列都将知晓，并 以电子可操作的方式驻留在数据库中， 新的生物学研究模式的出发点应是理论的。 一个科学 家将从理论推测出发，然后再回到实验中去，追踪或验证这些理论假设。” 随着世界人类基 因组工程计划的顺利完成，通过物理或数学的方法从大量的 DNA 序列中获取丰富的生物信1 息，对生物学、医学、药学等诸多方面都具有重要的理论意义和实际价值，也是目前生物信 息学领域的一个研究热点。 二、数字序列映射与频谱 3-周期性： 对给定的 DNA 序列，怎么去识别出其中的编码序列（即外显子） ，也称为基因预测，是 一个尚未完全解决的问题，也是当前生物信息学的一个最基础、最首要的问题。 基因预测问题的一类方法是基于统计学的[1]。 很多国际生物数据网站上也有 “基因识别” 的算法。比如知名的数据网站 http://genes.mit.edu/GENSCAN.html 提供的基因识别软件 GENSCAN（由斯坦福大学研究人员研发的、可免费使用的基因预测软件）,主要就是基于隐马 尔科夫链（HMM）方法。但是，它预测人的基因组中有 45000 个基因，相当于现在普遍认可 数目的两倍。另外，统计预测方法通常需要将编码序列信息已知的 DNA 序列作为训练数据 集来确定模型中的参数，从而提高模型的预测水平。但在对基因信息了解不多的情况下，基 因识别的准确率会明显下降。 因此在目前基因预测研究中， 采用信号处理与分析方法来发现基因编码序列也受到广泛 重视[4]。1. 数字序列映射 在 DNA 序列研究中，首先需要把 A、T、G、C 四种核苷酸的符号序列，根据一定的规 则映射成相应的数值序列，以便于对其作数字处理。 令 I ? { A , T , G , C } ，长度（即核苷酸符号个数，又称碱基对（Base Pair）长度，单位 记为 bp）为 N 的任意 DNA 序列，可表达为S ? { S [ n ] | S [ n ] ? I , n ? 0,1, 2, ? N ? 1 }即 A、T、G、C 的符号序列 S ： S [0], S [1], ? , S [ N ? 1] 。现对于任意确定的 b ? I ，令ub [n] ? ??1 , ?0, S [n] ? b S [n] ? b， n ? 0,1, 2, ? N ? 1称之为 Voss 映射[5]，于是生成相应的 0-1 序列（即二进制序列）{u b [ n ]} ：u b [0], u b [1], ? , ，u b [ N ? 1] ( b ? I )。例如，假设给定的一段 DNA 序列片段为 S = ATCGTACTG，则所生成的四个 0-1 序列分 别为：{u A [ n ]} ： {1, 0, 0, 0, 0,1, 0, 0, 0} ；2{u G [ n ]} ： {0, 0, 0,1, 0, 0, 0, 0,1} ； {u C [ n ]} ： {0, 0,1, 0, 0, 0,1, 0, 0} ；{u T [ n ]} ： {0,1, 0, 0,1, 0, 0,1, 0} 。这样产生的四个数字序列又称为 DNA 序列的指示序列(indicator Sequence)。 2. 频谱 3-周期性 为研究 DNA 编码序列（外显子）的特性，对指示序列分别做离散 Fourier 变换(DFT)N ?1U b [k ] ?? u b [ n ]en?0? j2? n k N,k ? 0,1, ? , N ? 1(1)以此可得到四个长度均为 N 的复数序列 {U b [ k ]} ，b ? I 。计算每个复序列 {U b [ k ]} 的平方 功率谱，并相加则得到整个 DNA 序列 S 的功率谱序列 { P [ k ]} ：P [ k ] ? U A [ k ] ? U T [ k ] ? U G [ k ] ? U C [ k ] , k ? 0,1, ? N ? 12 2 2 2(2)对于同一段 DNA 序列，其外显子与内含子序列片段的功率谱通常表现出不同的特性10000P(k)50000 0 100 200 300 k 0 600P(k)50000 0 100 200 300 k 400 500 600图 3 编号为 BK 的酵母基因 DNA 序列的功率谱（因为对称性，实际这里只给出了功率谱图 的一半） (a) 上图是基因上一段外显子(区间为[8]，长 1134bp) 对应的指示序列映射的功率 。 谱，它具有 3-周期性；(b) 下图是基因上一段内含子（区间为[]，长 1191bp）的指示序列的功 率谱，它不具有 3-周期性。可以看到：外显子序列的功率谱曲线在频率 k ?N 3处，具有较大的频谱峰值(PeakValue)，而内含子则没有类似的峰值。这种统计现象被称为碱基的 3-周期(3-base Periodicity)[2][3]。 记 DNA 序列 S 的总功率谱的平均值为?E ?N ?1P[k ]k ?0(3)N3 而将 DNA 序列在特定位置，即 k ?N 3处的功率谱值，与整个序列 S 的总功率谱的平均值的比率称为 DNA 序列的“信噪比” （Signal Noise Ratio，SNR） ，即P[ R ? N ]3 E(4)DNA 序列的信噪比值的大小，既表示频谱峰值(Peak Value)的相对高度，也反映编码或 非编码序列 3-周期性的强弱。 信噪比 R 大于某个适当选定的阈值 R 0（比如 R 0 ? 2 ） 是 DNA 序列上编码序列片段 ， （外 显子）通常满足的特性，而内含子则一般不具有该性质[6]。 在DNA序列 { S [ n ] , n ? 0,1, 2, ? N ? 1} 中，若N为3的倍数，将核苷酸符号b ? I ? { A , T , G , C } 出现在该序列的0,3,6,... N－3与1,4,7,…N－2以及2,5,8,…N－1等位置上的频数分别记为 x b , y b 和 z b ，则N 3处的总功率谱值即为[3][6]2? n? N 3 N 2P[N 3] ??b? IU b[N 32]?? ?b? IN ?1ub [n] ? e? j?n?0? ?b? IN ?1ub [n] ? e? j2? 32 nn?0??xb ? yb ? e? j2? 3? zb ? ej2? 32?b? I? (xb? I2 b? y b ? z b ? xb y b ? xb z b ? y b z b )2 2易见，当四种核苷酸符号 b （ b ? I ）在序列的上述第一、第二、第三个子序列上出现的频 数 x b , y b , z b 越接近相等时， 曲线，在N 3 N 3处的谱值也就越接近于零。所以，基因外显子序列的功率谱频率处具有较大的频谱峰值(Peak Value)，反映了在基因外显子片段上，四种核苷酸符号在序列的三个子序列上分布的“非均衡性” 。通常认为这种现象源于编码基因序列 “密码子” （coden）使用的偏向性（bias） 。虽然目前对此现象产生的“机理”还不是十分 地清楚，但是频谱的3-周期性被普遍认为是可用于识别基因编码序列（外显子）的一个重要 的特征信息。 3. 基因识别 频谱峰值特征的发现，或者频谱与信噪比概念的引入，其最终目的是要探测、预报一个 尚未被注释的完整的 DNA 序列的所有基因编码序列（外显子）片段。4 阈 值DNA序列 数值化 映射 DFT 变换 功率谱或 信噪比计算 外显子 判别分类 预测结果图 4 基于序列频谱 3―周期性的的基因预测方法流程图已经有一些研究者提出了识别基因的算法（如参见[6]及其后面的文献） 。目前利用信噪 比的基因识别算法通常有两种：一是固定长度窗口滑动法[2] [3]；另一是移动信噪比曲线识别 法[6]。 基于固定长度滑动窗口上频谱曲线的基因识别方法: 对一个 DNA 序列 S 和它的指示序列 {u b [ n ]} ， ? I ，n ? 0,1, 2, ? N ? 1 。 取长度 M （通 b 常取为 3 的倍数，例如 M=99, 129, 255, 513 等）作为固定窗口长度。 对任意 n 0 ? n ? N ? 1 ） 在以 n 为中心的长度为 M 的序列片段[n ? （ ，M ?1 2，? nM ?1 2]上（当 n 接近序列的两端时，窗口实际有效长度可能会小于 M） ，作四个指示序列的离散 Fourier 变换(DFT)i?n?M ?1 2U b [k ] ??i?n?u b [ i ]e2? j2 ? ik M,k ? 0,1, ? , M ? 1M ?1并求出它在M 3P[处总频谱 p (M 3 M 3M 32) ，即M 32] ? U A[] ? UT[] ? U G[M 32] ? UC[M 32?]? p (n;M 3)把这样得到的频谱值 p (m ax { p ( M 31 0.9 0.8 0.7M 3) ， n ? 0,1, 2, ? N ? 1 ，经过标准化处理（即除以最大频谱值0 ? n ? N ?1，并画出其频谱曲线 )} ）DNA spectrum p(n)0.6 0.5 0.4 0.3 0.2 0.1 0 30003500400000 nucleotide position n6000650070005 图 5 固定长度滑动窗口的频谱 p ? p (M 3) 曲线（人类线粒体基因，NC_.fasta） M 3 ) 曲线的图中红色水平细线条是 DNA 序列实际的基因外显子的区间。 滑动窗口频谱 p ( 峰与基因外显子区间具有“对应”关系。 基于 DNA 序列上“移动序列”信噪比曲线的基因识别方法：设已知 DNA 序列 S 和它的指示序列 {u b [ n ]} ， b ? I ， n ? 0,1, 2, ? N ? 1 。对任意 n （0 ? n ? N ?1 ） ，通常 n 取 3 的倍数并逐渐增大。 n 的左边一个长度为 n 的序列片段[0， 在 n-1]上，相应的子序列 S 0 ~ n ?1 称为 DNA 序列 S 的“移动子序列” ，作该移动子序列对应的四 个指示序列的离散 Fourier 变换(DFT)i ? n ?1U b [k ] ??i?0u b [ i ]e? j2 ? ik M,k ? 0,1, ? , n ? 1并求出移动子序列 S 0 ~ n ?1 ， n ? 0,1, ? , N ? 1 上的信噪比 R [ n ]n n n n n U A[ ] ? U T [ ] ? U G [ ] ? U C [ ] 3 3 3 3 E[n]2 2 2 2R[n ] ?P[ ] 3 ? E[n]，0 ? n ? N ?1?其中 E [ n ] 为移动子序列 S 0 ~ n ?1 的功率谱的平均值 E [ n ] ?n ?1P[k ]k ?0。在坐标系中画出移动序n列 S 0 ~ n ?1 的信噪比曲线 R [ n ] （称为信噪比移动曲线（SNR walk curve） ，见图 6）141210SNR R(n)86420 30003500400000 nucleotide position n600065007000图6DNA 移动序列其指示序列的信噪比曲线。 （人类线粒体基因，NC_.fasta）图中红色水平细线条是 DNA 序列实际的基因外显子的区间。DNA 序列的信噪比移动曲线6 的峰、谷与基因外显子区间的端点也具有较“明显的”的对应关系。 三、请研究的几个问题： 1. 功率谱与信噪比的快速算法 对于很长的 DNA 序列，在计算其功率谱或信噪比时，离散 Fourier 变换(DFT)的总体计 算量仍然很大，会影响到所设计的基因识别算法的效率。大家能否对 Voss 映射，探求功率 谱与信噪比的某种快速计算方法？ 在基因识别研究中，为了通过引入更好的数值映射而获取 DNA 序列更多的信息，除了 上面介绍的 Voss 映射外，实际上人们还研究过许多不同的数值映射方法。例如，著名的 Z-curve 映射（参见[5]或者附件 1） 。试探讨 Z-curve 映射的频谱与信噪比和 Voss 映射下的频 谱与信噪比之间的关系； 此外，能否对实数映射，如： A ? 0, C ? 1, G ? 2, T ? 3 ，也给出功率谱与信噪比 的快速计算公式？ 2.对不同物种类型基因的阈值确定 对特定的基因类型的 DNA 序列，将其信噪比 R 的判别阈值取为 R 0 ? 2 ，带有一定的主 观性、经验性。对不同的基因类型，所选取的判别阈值也许应该是不同的。附件中给出了来 自于著名的生物数据网站：http://www.ncbi.nlm.nih.gov/guide/ 的几个基因序列数据，另外也 给出了带有编码外显子信息的 100 个人和鼠类的， 以及 200 个哺乳动物类的基因序列的样本 数据集合。大家还可以从生物数据库下载更多的数据，找你们认为具有代表性的基因序列， 并对每类基因研究其阈值确定方法和阈值结果。 此外， 对按照频谱或信噪比特征将编码与非 编码区间分类的有效性，以及分类识别时所产生的分类错误作适当分析。 3. 基因识别算法的实现 我们的目的是要探测、预报尚未被注释的、完整的 DNA 序列的所有基因编码序列（外 显子） 。目前基因识别方面的多数算法结果还不是很充分。例如前面所列举的某些基因识别 算法，由于 DNA 序列随机噪声的影响等原因，还很难“精确地”确定基因外显子区间的两 个端点。 对此， 你的建模团队有没有更好的解决方法？请对你们所设计的基因识别算法的准确率 做出适当评估，并将算法用于对附件中给出的 6 个未被注释的 DNA 序列（gene6）的编码 区域的预测。7 4. 延展性研究 在基因识别研究中，还有很多问题有待深入探讨。比如 （1）采用频谱或信噪比这样单一的判别特征，也许是影响、限制基因识别正确率的一 个重要原因。 人们发现， 对某些 DNA 序列而言， 其部分编码序列 （外显子） 尤其是短的 ， （长 度小于 100bp）的编码序列，就可能不具有频谱或者信噪比显著性。你们团队能否总结，甚 至独自提出一些识别基因编码序列的其它特征指数，并对此做相关的分析？ （2） “基因突变”是生物医学等方面的一个关注热点。基因突变包括 DNA 序列中单个核 苷酸的替换，删除或者插入等。那么，能否利用频谱或信噪比方法去发现基因编码序列可能 存在的突变呢？ 上面提出的基于频谱 3-周期性的基因预测四个方面问题中， “快速算法”与“阈值确定” 是为设计基因预测算法做准备的。此外，在最后的延展性研究中，各队也可以对你们自己认 为有价值的其它相关问题展开探讨。参考文献： 【1】Burge, C., Karlin, S., 1997. Prediction of complete gene structures in human genomic DNA. J. Mol. Biol. 268, 78C94. 【2】Anastassiou, D., 2000. Frequency-domain analysis of biomolecular sequences. Bioinformatics 16, . 【3】Kotlar, D., Lavner, Y., 2003. Gene prediction by spectral rotation measure: a new method for identifying protein-coding regions. Genome Res. 13, . 【4】Berryman, M. J., Allison, A., 2005. Review of signal processing in genetics. Fluctuation and Noise Letters. 5(4), 13-35. 【5】Sharma, S. D., Shakya，K., Sharma，S. N., 2011. Evaluation of DNA Mapping Schemes for Exon Detection. International Conference on Computer, Communication and Electrical TechnologyC ICCCET. 2011, 18th & 19th 【6】Yin, C., Yau, S.S.-T. 2007. Prediction of protein coding regions by the 3-base periodicity analysis of a DNA sequence. Journal of Theoretical Biology. 247, 687C694.8
赞助商链接
Donor剪接位点识别算法与新基因的寻找_生物学_自然科学...问题是如何提高 一个识别算法的敏感性 Sn 和特异性...为实现这一目的,需要利用更 多信息科学中的理论和...关于遗传图谱的识别和有关基因型及概率推断和计算_高二理化生_理化生_高中教育_...请据图分析回答问题: 2 (1)该家族中决定身材矮小的基因是___性基因,最可能位...龙源期刊网 http://www.qikan.com.cn 基因组高通量测序数据结构变异识别算法 ...是生命的基本特征,遗传变异与表型差异之间的关系,是现代生物学的 一个基本问题...遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参 数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示) ,...遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参 数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示) ,...引的数学模型及算法,解决了基因序列数据索引的问题。...C=01,G=10,T=11) ,通过编写 Java 程 序读取...实现就是 HashMap)来缓存一些数据,从而提高系统的...进行蛋白质空间结构模拟和预测; 其本质是识别基因...“信息结构”和“复杂性”这三个重大科学问题 的有...二、发现新基因的两种方法是什么?算法的本质是? 大...1.2 重复基因问题 遗传算法在实现时,编码方案如果采用了实数编码,容易出现重复基因的问题。重复基因 主要是指在进行交叉操作的两个染色体中存在相同的基因,选择交叉...人工智能论文-遗传算法实现八皇后问题_计算机软件及应用_IT/计算机_专业资料。...因此,在一开始需要实 现从表现型到基因型的映射即编码工作。由于仿照基因编码的...DNA序列的k-mer index 问题-基于Hash算法快速检索_生物学_自然科学_专业资料。...(1)要求对给定 k, 给出并实现一种数据索引方法,可返回任意一个 k-mer 所 ...
All rights reserved Powered by
www.tceic.com
copyright ©right 。文档资料库内容来自网络，如有侵犯请联系客服。您的位置： >>
现代生物遗传学中描述的生物进化理论:
遗传物质的主要载体是染色体(chromsome),染色体主要由DNA和蛋白质组成。其中DNA为最主要的遗传物质。
基因(gene)是有遗传效应的片断,它存储着遗传信息,可以准确地复制,也能发生突变,并可通过控制蛋白质的合成而控制生物的状态.生物自身通过对基因的复制(reproduction)和交叉(crossover,即基因分离,基因组合和基因连锁互换)的操作时其性状的遗传得到选择和控制。生物的遗传特性,使生物界的物种能保持相对的稳定;生物的变异特性,使生物个体产生新的性状,以至于形成了新的物种(量变积累为质变),推动了生物的进化和发展。
遗传学算法和遗传学中的基础术语比较
染色体(chromosome)&&&
数据,数组,序列
基因(gene)
单个元素,位
等位基因(allele)
数据值,属性,值
基因座(locus)&
位置,iterator位置
表现型(phenotype)&
参数集,解码结构,候选解
遗传隐匿(epistasis)&
染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。各个个体对环境的适应程度叫做适应度(fitness)
遗传算法的准备工作:
1)数据转换操作,包括表现型到基因型的转换和基因型到表现型的转换。前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding),后者是它的逆操作(decoding)
2)确定适应度计算函数,可以将个体值经过该函数转换为该个体的适应度,该适应度的高低要能充分反映该个体对于解得优秀程度。非常重要的过程！
遗传算法的基本步骤
遗传算法是具有"生成+检测"(generate-and-test)的迭代过程的搜索算法。 基本过程为:
1)编码,创建初始集团
2)集团中个体适应度计算
3)评估适应度
4)根据适应度选择个体
5)被选择个体进行交叉繁殖,
6)在繁殖的过程中引入变异机制
7)繁殖出新的集团,回到第二步
一个简单的遗传算法的例子:求 [0,31]范围内的y=(x-10)^2的最小值
1)编码算法选择为"将x转化为2进制的串",串的长度为5位。(等位基因的值为0 or 1)
2)计算适应度的方法是:先将个体串进行解码,转化为int型的x值,然后使用y=(x-10)^2作为其适应度计算合适(由于是最小值,所以结果越小,适应度也越好)
3)正式开始,先设置群体大小为4,然后初始化群体 =& (在[0,31]范围内随机选取4个整数就可以,编码)
4)计算适应度Fi(由于是最小值,可以选取一个大的基准线1000,Fi = 1000 - (x-10)^2)
5)计算每个个体的选择概率.选择概率要能够反映个体的优秀程度.这里用一个很简单的方法来确定选择概率
P=Fi / TOTAL(Fi).
6)选择.
根据所有个体的选择概率进行淘汰选择.这里使用的是一个赌轮的方式进行淘汰选择.先按照每个个体的选择概率创建一个赌轮,然后选取4次,每次先产生一个0-1的随机小数,然后判断该随机数落在那个段内就选取相对应的个体.这个过程中,选取概率P高的个体将可能被多次选择,而概率低的就可能被淘汰.
下面是一个简单的赌轮的例子
&& 13%&&&&&&&&&&&&&& 35%&&&&&&&&&&&&&&&&&&& 15%&&&&&&&&&&&&&&&& 37%&&&&&&&
----------|----------------------------|------------|-*-------------------------|
&& 个体1&&&&&&&&&&&&& 个体2&&&&&&&&&&&&&&&&& 个体3&&& ^0.67&&& 个体4
随机数为0.67落在了个体4的端内.本次选择了个体4. 被选中的个体将进入配对库(mating pool,配对集团)准备开始繁殖.
7)简单交叉
先对配对库中的个体进行随机配对.然后在配对的2个个体中设置交叉点,交换2个个体的信息后产生下一代.
比如( | 代表简单串的交叉位置)
&( 00|0 ) --交叉--& ()
& ( 01|000, 11|011 ) --交叉--& ()
2个父代的个体在交叉后繁殖出了下一代的同样数量的个体.
复杂的交叉在交叉的位置,交叉的方法,双亲的数量上都可以选择.其目的都在于尽可能的培育出更优秀的后
8)变异
变异操作时按照基因座来的.比如说没计算2万个基因座就发生一个变异(我们现在的每个个体有5个基因座.也就是说要进化1000代后才会在其中的某个基因座发生一次变异.)变异的结果是基因座上的等位基因发生了变化.我们这里的例子就是把0变成1或则1变成0.
至此,我们已经产生了一个新的(下一代)集团.然后回到第4步,周而复始,生生不息下去:)
伪代码实例(适合爱看代码的朋友~):
//Init populationforeach individual in population{
individual = Encode(Random(0,31));}while (App.IsRun){
//计算个体适应度
int TotalF = 0;
foreach individual in population
individual.F = 1000 - (Decode(individual)-10)^2;
TotalF += individual.F;
//------选择过程,计算个体选择概率-----------
foreach individual in population
individual.P = individual.F / TotalF;
for(int i=0;i&4;i++)
//SelectIndividual(float p)是根据随机数落在段落计算选取哪个个体的函数
MatingPool[i] = population[SelectIndividual(Random(0,1))];
//-------简单交叉---------------------------
//由于只有4个个体,配对2次
for(int i=0;i&2;i++)
MatingPool.Parents[i].Mother = MatingPool.RandomPop();
MatingPool.Parents[i].Father = MatingPool.RandomPop();
//交叉后创建新的集团
population.Clean();
foreach Parent in MatingPool.Parents
//注意在copy 双亲的染色体时在某个基因座上发生的变异未表现.
child1 = Parent.Mother.DivHeader + Parent.Father.DivE
child2 = Parent.Father.DivHeader + Parent.Mother.DivE
population.push(child1);
population.push(child2);
&小结:
遗传算法中最重要的过程就是选择和交叉。
选择要能够合理的反映"适者生存"的自然法则，而交叉必须将由利的基因尽量遗传给下一代(这个算法很关键！)
还有就是编码的过程要能够使编码后的染色体能充分反映个体的特征并且能够方便计算。这篇文章是原来学习的一些回忆的整理,因为最近要实用了.不正确的地方还希望大家多多指出~
软件设计热门文章
软件设计最新文章您所在位置： &
 &  & 
大规模基因比对算法.pdf 99页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
大规模基因比对算法
你可能关注的文档：
··········
··········
随着擐4序技术的发展，越来越多的动植物、微生物的全基因组序列得以测定完
成，基因组数据和规模正在以前所未有的速度迅速增长．基因组在进化过程中常常会
有基因复制，基因缺失，易位，倒置等大规模突变发生．基因复制会产生旁系同源基
因；基因缺失会导致物种的直系同源性模糊；而易位或者倒置通常会引起遗传物质的
重排．长基因组的序列比对可以查找基因组突变，是基因组数据的比较分析，物种的
进化分析和基因功能研究的基础．
传统的动态规划算法[1】【2】的计算复杂度为0(矿)，其中n是输入序列的平均
长度．动态规划只能处理长度在500K以内的氨基酸序列或者基因组序列．基于统计
推断的SPA算法[3】的计算复杂度为0(凡)，可以准确的比较长度在2M之内的基因
组序列，但是随着长度的增加和输入序列同源性的降低，比对误差越来越大．
要比对长度规模更大的基因组序列，需要新的高效精确的算法．本文的结果就是
开发适合大规模基因组序列比对的算法．具体结果如下；
1．首次将数据压缩的思想用于序列比对，对SPA算法做了改进，拓展了SPA算法
的应用范围，开发出GSPA-I算法，该算法可用于大规模的微生物基因组和真核
生物基因组的序列比对，测试结果表明GSPA-I算法比传统的序列比对算法速度
大大提高，作长度大于2M的序列的比对结果的精确度高比SPA算法有明显提
2．首次将基于语法的编码Yang—Kieffer算法[4】用于序列比对，开发出基于语法的
处理，找到序列之间的语法匹配模块GMB，在GMB的基础上再完成比对，该算
法比对规模大，克服了以往基因组序列比对算法受输入序列规模限制的弱点，用
编码方法大大降低了算法的复杂度的同时，方便了对比对结果的分析．GSPA-II
算法能够很快处理长度在200M以上的基因组染色体序列，另外GSPA-II算法
能找到倒置，换位等大规模基因组突变．实验结果表明，GSPA-II算法与最流行
的BLASTz算法相比，比对速度平均高100倍左右，但是比对结果的相似度和
基因覆盖率大致相当．
3．开发了大规模基因组多重比对算法SMGA，该算法结合了“模结构”理论和GSPA-
I算法，比对的速度和其他的各项指标与SMA算法基本持平，但是SMGA能够
处理像细菌古细菌等长基因组序列的多重比对．SMGA是基因组序列同源保守
区的估计，基因预测和物种进化研究的有效工具．
关键词：大规模基因组比对，语法分析，Yang-Kieffer编码，数据压缩，语法匹
配模块，基因覆盖率与相似度
developmentsequencingtechniques，moregenomes
databaseincreasemore more
biological
sequenced．The
deletionsand
evolve，theyundergogeneduplication，andlarge-scale
inversionsortranslocations．Genewill
duplicationproduceparalogousgenes
losswillobscurethe
正在加载中，请稍后...
