学位论文 > 优秀研究生学位论文题录展示

模体发现模型设计与研究

作　者: 邵琳琳
导　师: 陈月辉
学　校: 济南大学
专　业: 计算机软件与理论
关键词: 模体发现细菌群优化禁忌搜索差分/分布估计算法
分类号: TP18
类　型: 硕士论文
年　份: 2010年
下　载: 19次
引　用: 0次
阅　读: 论文下载

内容摘要

在脱氧核糖核酸的调控区域存在着一些对基因表达,转录,翻译具有特殊生物意义的基因段,即转录基因结合位点(TFBSs),它们具有保守性,重现性,并且相对较短.我们称为:motif。从而我们可将模体发现问题描述为:从一组相关DNA序列中找出具有某种特定功能的未知序列片段。它主要有3大难点:(1)由于突变,交叉,删除基因段的存在,motif出现形式不确定。(2)motif长度不确定。(3)某条序列中存在motif的条数不确定。通过我们的研究,构建了基于细菌群搜寻优化(BFO)的模体发现算法。基本建立了一种高效的模体发现模型,并对其进行了初步的完善。首先,将原BFO算法与Tabu Search(禁忌搜索)算法相整合成TS-BFO,通过建立self-control multi-length chemotactic step mechanism(自控趋向步调整机制)和引入Rao metric(Rao测度)来解决模体发现问题。即在趋向步阶段,利用搜索禁忌表,不再或有选择地搜索一些点。对禁忌表中的优秀结果的邻居进行彻底的,仔细的搜索。增加优秀个体的趋向步搜索次数。此方法优点:(1)可避免搜索进入循环状态。(2)不断增大搜索空间,避免陷入极值。(3)避免重复解,保持了种群的多样性。对于自控趋向步调整机制来说,新的自控趋向步调整机制,每个个体自动确定趋向步长,随迭代次数变化,依照准则(对某一个个体而言):准则一:初始设置较大趋向步长。准则二:如果K步未搜索到更优解,缩小其趋向步长。准则三:每代必设置一定比例的大趋向步搜索。另外我们还设置大趋向步随机检测个体,如新产生的个体的适应度值大于特赦准则,则搜索禁忌表且进行相应处理。其次,我们构建了一种混合初始种群,引入了新的操作算子(例如移位操作),使新算法达到更高的效果。最后,在之前算法的基础上,将DE/EDA算子引入,代替原BFO算法中的Reproduction环节,提高算法的搜索能力。在原BFO算法中,在Reproduction环节只是将优秀的半数种群复制成新的个体,并没有更优的个体产生,影响收敛速度的同时产生重复解使算法易陷入极值。我们引入DE/EDA算子代替原来方法,DE(Differential Evolution)通过从当前优秀种群个体中提取距离和方向信息,加入随机差分保持多样性来产生新的个体。再与我们所熟知的分布估计算法相结合,达到了很好的效果。从实验结果我们发现:将TS与BFO结合解决实际问题,实验结果表明引进禁忌搜索后的TSBFOMD算法的对于解决模体发现问题的有效性,在理想的时间内达到了满意的效果,所以她可以作为一种提取模体的方法。而对于TS-BF-DE/EDA算法,它的的搜索能力优于原始BFO算法和原始DE/EDA算法,可以作为一种全新的优化算法予以应用。在以后我们会并不断地在更多的实验中发现其优缺点并加以改正。对于Motif的长度自动确定;算法参数的确定问题;更多生物知识的引入等扩展领域,我们也进行了一些设想。

全文目录

摘要  6-8
ABSTRACT  8-10
第一章绪论  10-15
  1.1 研究背景  10
  1.2 问题描述  10-12
  1.3 国内外研究动态  12
  1.4 论文内容安排  12-15
第二章智能计算基础  15-25
  2.1 概述  15-18
  2.2 进化算法  18-20
    2.2.1 编码与解码  18
    2.2.2 适应度函数  18-19
    2.2.3 遗传操作  19
    2.2.4 遗传算法的步骤  19-20
    2.2.5 遗传算法的特点  20
  2.3 群体智能理论  20-25
    2.3.1 粒子群优化算法  21-22
    2.3.2 细菌生存优化算法  22-25
第三章基于改进的BFO 算法的模体发现方法IBFO  25-37
  3.1 创新点  25-30
    3.1.1 混合初始种群  25-27
    3.1.2 引入Rao 测度的适应值函数  27-29
    3.1.3 新操作算子的引入  29-30
  3.2 IBFO 算法描述  30-32
    3.2.1 流程图  30-31
    3.2.2 算法详细步骤  31-32
  3.3 算法性能及实验结果  32-37
第四章禁忌细菌群优化算法TS-BFO 用于模体发现  37-47
  4.1 禁忌搜索  37-42
    4.1.1 禁忌搜索思想  37-38
    4.1.2 禁忌搜索算法流程  38-39
    4.1.3 禁忌搜索特点  39-41
    4.1.4 禁忌搜索用于模体发现  41-42
  4.2 自控趋向步调整机制  42
  4.3 TS-BFO 算法描述  42-43
  4.4 TS-BFO 实验结果分析  43-47
第五章一种新的优化算法TSBFD  47-59
  5.1 差分/分布估计算法DE/EDA  47-52
    5.1.1 差分进化算法DE  47-49
    5.1.2 分布估计算法EDA  49-51
    5.1.3 差分/分布估计算法DE/EDA  51-52
  5.2 TSBFD 算法描述  52-53
  5.3 TSBFD 优化基准函数结果分析  53-59
第六章总结和展望  59-61
参考文献  61-66
致谢  66-67
攻读硕士期间发表论文目录  67

模体发现模型设计与研究

内容摘要

全文目录

相似论文