【毕业学位论文】（Word原稿）基于禁忌差分进化算法的生物网络模型参数搜索研究-软件工程

硕士学位论文 （专业学位） 基于禁忌差分进化算法的生物网络模型参数搜索研究 姓 名：陈飞 学 号： 1134722 所在院系： 软件学院 职业类型： 教育类 专业领域： 教学管理 指导教师： 贾金原 副 指导教师 ： 蔡文涛 二 一 四年三 月 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年 月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年 月 日同济大学 硕士学位论文 摘要 I 摘要 自从 20 世纪 50 年代 现 双螺旋结构 以来， 生命体行使功能的 各种 机制 不断地 被揭示出来。 从那个时候起开始形成的分子生物学发现 了大量 由生物分子相互作用 而 形成的 生物网络 ，而且证明 了 正是这些 网络驱动了所有的生命行为。 随着 生物学 实验技术的进步 ， 研究人员 可以同时 对网络中大量分子进行测量，从而发现网络 中各元素之间的相互作用以及动态变化规律，并试图以此来揭开生命的奥秘。 然而，由于生物网络本身 的高 复杂性，加之 目前的 实验技术无法测量 建模 所需的全部信息，因此单纯应用生物实验方法很难彻底揭开生命现象背后所隐藏的奥秘。 鉴于此，各种新的方法被引入到生物学研究之中，其中计算生物学就是近几十年来逐渐发展起来被广泛应用 的一种新的研究 手段。计算生物学 是一门 融合了 生物学、数学、信息 科学 与计算机科学 等领域 的交叉学科 。 计算生物学的一种重要研究方法就是建模分析，通过 构建 生物网络模型， 来模拟 无法从生物学实验中 直接观测的现象 ，从而进一 步揭示生命过程的机制 。但是，目前的生物学实验技术 还无法测量出构建模型所需的全部 信息 ，因此一些重要信息需要通过计算技术得到，这就需要设计出精妙的算法来准确地估计出必需的信息。 本文在对生物网络建模 过程 中经常用到的经典参数搜索算法进行研究的基础上开发出了一种综合禁忌搜索技术与差分进化算法的新的参数搜索算法，并通过 现有 模型 对此算法的性能进行了 测试 。结果表明，新算法在搜索能力上较传统算法有明显提高，可以在比较短的时间内找到模型的最优参数。 另外 ，我们利用这个算法，结合真实的生物网络 胎发育过程中调控体节发生的信 号转导通路，进行了建模研究。在给定模型结构后，我们的算法根据一组基因芯片数据为模型搜索到一组 最优 参数。模型模拟结果显示，模型在该组参数值下可以真实再现多种生物学实验的结果，表明模型 在参数和结构上都 是 准确 的 。这些结果 说明我们的算法可以应用于实际的生物网络建模研究， 进而发现新的生物学知识。 关键词 ： 生物网络 ， 禁忌 搜索 算法 ， 差分进化算法 ， 参数 搜索NA 950s, by a of by of it of of in in On to of by of is to of to is a is in is a An in is In to be in of to So be to In I in On a We of of is of In we s II a of of to a NA of of be to to 硕士学位论文 目录 目录 第 1 章 引言 . 1 物网络简介 . 1 物系统建模研究概述 . 2 物网络模型参数搜索研究现状 . 4 于梯度的方法 . 4 机搜索方法 . 5 因芯片技术简介 . 7 文研究内容 . 8 第 2 章 生物网络模型参数搜索算法概述 . 11 部搜索算法介绍 . 11 局搜索算法介绍 . 12 传算法 . 12 拟 退火算法 . 13 子群优化算法 . 14 算法融合介绍 . 16 章小结 . 17 第 3 章 基于禁忌差分进化的参数搜索算法 . 19 忌搜索技术 . 19 分进化算法 . 21 忌差分进化算法 . 22 章小结 . 25 第 4 章 基于人工数据的实验结果 . 27 验数据构建 . 27 验结果分析 . 31 果比较 . 32 章小结 . 34 第 5 章 真实生物网络模型构建实验 . 35 型结构描述 . 35 型方程构建与参数搜索 . 36 型准确性验证 . 39 章小结 . 41 第 6 章 结论与展望 . 43 论 . 43 一步工作的方向 . 43 同济大学 硕士学位论文 目录 V 致谢 . 44 参考文献 . 45 附录 A 络模型的参数 . 50 个人简历、在读期间发表的学术论文与研究成果 . 52 第 1 章 引言 1 第 1 章 引言 物网络 简介 在生物系统中 ，各种基因、 蛋白质以及其它 多种 生物分子相互调控形成了各种各样的网络。这些网络处于 不同层面 而且具有 不同 的 组织形式。目前，基因转录调控网络、生物代谢 网络、 信号 转 导网络 与 蛋白质相互作用网络是最常见 也是研究最多 的生物分子网络。 （ 1） 基因调控网络 。 生物在生长 、 发育 和 分化 以及 与 外部环境 交互的过程中， 多种 基因有条不紊 地 表达起着 十分关键 的作用。 相对于 原核生物 ，真核生物的 基因表达调控 要 复杂 得多 ，真核生物 的 基因表达 调控主要是指 转录因子调控 编码蛋白质的 产生 以及对 使生物功能过程中的调节与控制。从理论上 来 讲，基因表达调控可 以发生在遗传信息传递过程的 每一个环节中 ，其中转录调控是基因表达调控中最重要 最复杂的一个环节，也是当前研究的 一个热点问题 。基因调控网络 的研究 包括：基因调控 的 检测、基因转录调控数据库 的创建以及 基因转录调控网络 的推导 (2008)。 （ 2）生物 代谢网络 。 在生物化学领域 中 ，代谢通路 一般 是指细胞 内 代谢物质在酶的 催化 作用 下转化为新代谢物过程中所发生的一系列生 化 反应 (2011)。而代谢网络则是指由代谢反应以及调 节 这些反应的 调控 机制所 形 成的 表示 细胞内代谢和生理过程的网络。 生物代谢网络是细胞获得营养与维持生命所必不可少的，因此对该网络机制的研究也是当今网络生物学的热点之一 (2003)。 （ 3） 信号 转 导网络 。 细胞 中的信号 转 导 是指细胞将 胞外 信号或刺激转换为胞内 信号最终激活细胞 内各种 反应的过程。 与 代谢通路一样，信号 转导 过程中多种 生物分子在酶的 催化 作用 下按 照 固定 的顺序发生一系列 的 生化反应，由此 便 得到了信号 转 导通路 (2000)。信号 转 导网络 就 是指参与信号 转 导通路的分子 及其 由于相互作用而 发生的生化反应所构成的网络。 生物 代谢网络和信号 转 导网络是研究 细胞 代谢过程和信号 转 导过程的重要工具，随着 越来越多 物种基因测序 工作 的 完成以及新的生物检测技术的 发展 ， 人们对 细胞内生化反应 机制的了解也正以极快的速度增加，这就使 得 构 建 完整的生物代谢网络和信号传导网络成为可能 (2012)。目前 生物 代谢 与 信号 转 导通路信息被 收集并 整理到一些重要的通路数据库中，这些信息是构建 生物代谢 网络和信号 转 导网络的基础。 同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 2 （ 4） 蛋白质 相互 作 用 网络 。 蛋白质是构成生物体的重要物质，也是 行使 生物功能的重要生物大分子。蛋白 质分子 通过彼此之间的相互作用构成蛋白质相互作用网络 ，从而 参与生物信号 的 传递、基因表达 的 调节、能量和物质 的 代谢 以 及细胞周期 的 调控等生命过程 中 的 重要 环节。系统 地 分析大量蛋白 质 在生物系统中的相互作用关系，对了解生物系统中蛋白质的工作 机制 ，了解疾病等特殊生理状态下生物信号 转导 和能量物质代谢的反应机制，以及 了解蛋白 质 之间的功能联系都 具 有重要意义。蛋白质相互作用通常可以分为物理 相互作用与 遗传 相互作用 。物理 相互作用 是指蛋白质 之 间通过空间构象或化学键 发生的结合或化学反应，是蛋白质互作的主要研究 内容之一 。而遗传 相互作用 则是指在特殊环境下，蛋白质或基因 受 其 它 蛋白质或基因的影响，常常表现为表型变化之间的相互关系。蛋白质 相互作用 网络 的研究内容主要 包括：蛋白质 相互作用的 检测技术（免疫共沉淀技术、酵母双杂交技术、质谱分析技术、蛋白质 相互作用 预测技术 以及 遗传 相互作用 检测技术 等 ） 、 蛋白质 相互作用 数据库 的构建 、蛋白质 相互作用 网络 的推 导等 (2002; 2009)。 以上介绍的这些生物网络在调节生物的生命活动方面起关键作用 ，因此要彻底揭开生命的最终奥秘就必须识别出这些相互作用网络 并对他们的工作机制进行研究 。然而，由于受目前生物实验技术的限制，单纯通过实验方法很难识别出全部的生物网络。因此，许多新的技术被引进用来进行生物网络的研究， 生物 系统 建模就是一种目前被广泛应用的重要技术。 物 网络 建模研究概述 生物 网络 建模 是生物学研究中被广泛采用的研究方法。 生物学家经常使用现实世界模型来模拟生物系统。 可以使用简单模型 ，如分子 的 球棒模型，也可以 使用复杂模型 ，如模式生物或动物疾病模型 等 。 此外， 生物学家也使用概念模型来研究生物系统，这 些模型通常采用自然语言来描述，并使用图表来表示系统中相互作用的组分以及它们之间的作用方式。这些相互作用图表，或称为“卡通”模型，在表示细胞内生化反应过程中经常被用到。这 种 卡通模型 有一个 十分 明显 的缺点 ，那就是 它会给系统行为带来显著的不确定性，特别是相互作用网络中包含反馈回路时。如果使用数学 公式 描述一个系统，我们就可以消除这 些 不确定性。这样做的代价是必须定量地表示卡通模型中的每一个相互作用。 在为生物网络中的生化反应指定数学公式时， 在有些情况下，为反应提供平衡常数就够了。而在另外一些情况下，绑定速率和解离速率都 是必须的。对于大多是细胞内的 生化 反应过程，以我们现在的知识水平没有办法提供一个定量的描第 1 章 引言 3 述，即我们只能定性地理解相关的分子相互作用。尽管如此，由于越来越多的生化反应过程被生物学家详细研究，目前已经积累了足够的数据来保证这种定量的描述可以进行。当获得了必须的定量数据之后，相互作用图表就能用动态数学模型表示。构建出来的数学模型包含一组用来描述系统动态行为的方程。分子相互作用的定量描述通常是根据相关物理和化学定律做出来的，由此产生的模型是机械式的，也就是说他们描述了产生观测行为的机制。机械模型的每一组分代表了所研究 系统的某一方面特征，因此对模型组分的修改就模拟了对真实系统的修改。研究机械模型有两条互补的途径。一种最直接的方法是模型模拟。模型模拟是指用构建的模型来预测在给定条件下的系统行为。模拟有时也被称为计算机实验，因为是在计算机中模拟生物系统的行为。模拟是使用数值软件包来进行的，目前有多种软件可供使用 。另一种方法是直接研究构建的模型，从而获得一般性的潜在的系统行为，这被称为模型分析。这些模型分析方法有时候需要复杂的数学技术。掌握了这些技术会观测到无法从模型模拟直接得到的系统行为。模型模拟会指明系统产生何种行为，而模 型分析会揭示产生这些行为的原因。这种分析能揭示系统结构和其相应行为之间的非直观的联系。 建模工作的最终目标是对生物系统 网络 建立起可以描述其全部行为的数学模型，从而保证模拟结果代表的是系统的真实行为。目前所建立起的生物网络模型还无法达到这一目标，但是在其它学科，如工程学中已经有这样的例子了。工程学家利用具有准确预测性能的模型进行基于模型的设计，从而给工程产品的研发带来更快更高效的发展。波音 777 喷气式飞机的研发是一个十分具有说服力的例子，在实际建造飞机之前工程师通过计算机模拟对它进行了全面的设计和测试。尽管目 前描述生物学网络的数学模型的预测能力很有限，但它们可以用来指导组分的选择，也可以指导生物学家选择可以测试系统性能的最有效的实验。 综上所述， 生物 网络 建模已经 成为生物学研究中不可或缺的重要手段，通过这种方法可以对各种生物 网络建立模型，进而进行模型模拟，预测系统行为；也可以通过模型分析来探索产生相应行为的生物学机制。在收集足够的生物数据的基础上，使用系统生物学建模方法对相关生物学问题进行研究，不仅能节约大量时间和成本，还能获得 无 法从生物实验中直接获取的生物学知识，因此，这种方法已经成为当前生物学研究中的一个 新的 热点，在细胞信号转导通路， 生物代谢网络 ，基因表达 调控 网络等相关生物学领域取得了大量的研究成果。当然，由于实验技术和 条件 的限制， 生物网络 建模 研究中 还存在大量急需解决的问题， 比如模型关键参数值的 获取 。本文将对针对 模型参数 搜索 问题对 生物网络 建模展开研究， 提出一种新的参数搜索 算法， 并 通过 人工 实验数据 对算法性能进行 测试 ，实验结果表明该算法具有良好的搜索性能，可以在较短的时间内搜索到较优秀的模同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 4 型参数值。最后，我们 将该算法 应用于 大鼠 胚胎发育初期体节发生这一具体生物学问题， 在提出模型结构之后 通过 真 实 的基因芯片数据 进行参数 搜 索 ， 建立 了一个通路信号转导 模型 ，模型模拟结果表明该模型能准确模拟生物实验结果从而证明 该 模型是 准确的 ，进一步证明我们提出的算法在 解决 生物网络建模研究 的参数搜索 问题 是 有效的 。 物网络 模型参数搜索研究 现状 模型 参数搜索 问题 传统上被 表示为 一个最小化目标函数的优化问题。目标函数是实验数据与模型预测值之间广义距离的度量。最常使用的目标函数是欧氏距离而且经常使用最小均方差准则。其它适应度评估方法包括基于信息论的准则(2003, 2006)。 在生物网络模型的参数搜索 问题中 通常使用两 种 目标函数：基于浓度误差的目标函数和基于斜率误差的目标函数 (2005)。基于浓度误差的目标函数直接度量训练数据（基因芯片数据、代谢物浓度数据等）与预测值之间距离的平方和。预测值通常是通过数值积分方法求解微 分方程获得的。积分过程需要大量计算量，尤其是当系统是刚性的时候。基于斜率的目标函数采用解耦技术并且使用斜率信息评估函数的适应度。也就是说，它计算的是从训练数据测得的斜率与预测斜率之间误差的平方和。最著名的基于时间序列数据的参数搜索方法分为基于梯度的方法 和 随机搜索方法。 于梯度的方法 搜索参数值 最常用的方法 是基于梯度的回归 方法 。许多这类商业化的算法被应用于生物网络模型，其中包括高斯牛顿法和列文伯格 这些算法被这个领域 内 所有主要的软件包 所应用 ，在这里我们不再赘述 (1996; 1987; 1999)。 出了一种基于梯度的算法，该算法用于搜索 型的参数 (2006)。 首先，基于解耦和有限 连 通规则 逐个 产生合理的初始模型；然后，每个微分方程都使用列文伯格 第三阶段， 新生成 的 模型与早期简单的模型进行比较，并且使用一种统计检验根据残留误差决定是否提高模型结构的复杂度。如果 改善是显著的，那么新的更复杂的模型就会产生，这个过程一直迭代 直到 进一步的改善不再显著。 人提出了一种新 的牛顿流优化方法估计 S 系统的参数 (2007)。该方法首先进行微分方程解耦并且为每一个方程建立一个目标函数。接下来为参数选择合适的起始点和边界 条件 并且运行牛顿法获得参数空间中的若干点作为合理的粗糙解。作者发现这组粗糙解包含一个一维吸引子并且可以使用第 1 章 引言 5 标准回归来估 计这个吸引子的参数。然后，使 用根据估计出的吸引子设置的初始值再一次运行牛顿法就会找到参数值 的 最优解。 因为 生物网络 通常是非线性的，参数搜索问题可以被视为一种服从微分 2003)。由于它非线性与约束性的特征，这个问题通常是非凸的。因此，大多数传统的涉及梯度方法的非线性算法都 有 陷入局部极小的风险，这种风险 的大小依赖于系统非线性的程度以及初始点的选择(1998)。 机搜索方法 多种类 型 的随机方法可以应用于 模型参数的 全局优化，包括进化计算、模拟退火、自适应随机算法、聚类方法和其它与启发式算法，例如蚁群优化和粒子群优化 等 。这些方法已经应用于寻找全局最优解的参数搜索问题，尤其是在基因调控网络结构识别领域 (2003)。 进化计算技术包括遗传算法、进化规划、遗传规划和其它的改进形式。这些方法被广泛应用是因为它们具有找到全局最优解的潜力。遗传算法已经在 生物网络 参数估计问题上表现出很高的实用性 (1996; 2003; 1997; 2003)。 通过应用 简单遗传算法， 人推断出了一个仅 有几个参数的小网络的参数值，但是收敛速度很低 (2000)。简单遗传算法 有两个明显的缺点 ：在快速搜索阶段会早熟；在最后阶段会出现进化停滞。 人通过使用更鲁邦的实数编码遗传算法改进了简单遗传算法，并且通过引入罚分项删除所研究的基因网络中不可能的连接改进了传统的代价函数。还有一些其它的改进用来提高简单遗传算法在 参数估计 上的 效率，包括：简单遗传算法与改进的鲍威尔算法的混合算法 (1998)；一种用来优化 S 系统参数的具有单峰正态分布交叉操作的实数编码遗传算法与最小代沟方法的组合算法 (2003; 2001; 2002)。 出一种 具有 “自由尺度 ”特性的分布式遗传算法 来 优化 S 系统 (2006)。 人提出一种智能的两阶段遗传算法，用于进行常微分方程参数的优化。 同事提出了一种包含两部分的文化基 因算法 (2004a; 2004b)。该算法使用带有遗传策略的局部搜索进行参数搜索，使用全局遗传算法进行结构推导。算法的前一部分是嵌入到后一部分的。他们使用 S 系统模型对法进行了测试，结果表明在推导遗传网络方面文化基因算法的性能优于标准的遗传算法。在后续的研究中，他们发现从局部搜索到遗传算法的反馈可以进一步提高文化基因算法的性 能 (2005)。人提出一种被称为带有距离独立多样性控制的遗传局部搜索的遗传算法，并结合一种分解策略估计基因调控网络的 S 系统模型 (2004)。该算同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 6 法包括一种对初始基因表达水平的估计技术，它可以使用带有噪音的数据重构出中等规模的遗传网络。他们也指出该算法结合一种协 作遗传算法能进一步提高预测的准确性 (2005)。 团队也提出了一些进化搜索技术，例如 网络结构搜索进化算法 及其变形和 基于网格的遗传算法框架 。他们使用 S 系统表示数学模型并且使用遗传算法作为搜索引擎推导基因调控网络 (2005; 2003; 2004)。 同事最近把他们早期开发的技术结合到一种改进的文化基因算法来推导基因调控网络 (2005a, b, 2006, 2007; 1997)。 出了一种新的参数搜索算法 (2005)。该算法首先使用混合差分进化技术估计一个尽管不是最优但满足预定要求的初始解，然后把这个解作为基于梯度优化的初始点来获得精确解。在他们最近的研究中，他们实现了混合差分进化技术同多目标优化方法的结合并用该算法推导 S 系统表示 的 生化反应网络 (2008)。 模拟退火、蚁群优化和粒子群优化也都是随机优化方法。模拟退火是一种基于物理现象的方法，最初用来模拟金属或玻璃的加热与冷 却过程 (2002)。模拟退火既可以进行全局搜索也可以进行局部搜索并且在温度下降的过程中可以自动地在这两者之间转换。 人把模拟退火应用于从时间序列数据估计 S 系统的参数。他们通过三组人工数据集和一个真实的 生物网络 对算法进行了测试，表现出了良好的效果。 蚁群优化算法的灵感来源于蚂蚁在寻找食物过程中发现路径的行为 (1999)。蚁群算法是一种用来在图中寻找优化路径的概率型算法。 人把蚁群算法应用于 S 系统模型，他们把每一种代谢物 当作 图中的一个节点并且推导出其它节点 如何连接到这个节点 (2008)。 他们把该算法称为识别网络结构的 “离散 性 蚁群算法 ”。作为蚁群算法的一种扩展，他们进一步提出一种增强型信息素聚集系统的变形来估计 S 系统的参数，被称为 “ 连续性蚁群算法 ” 。 粒子群优化是一种随机的基于群体的进化计算技术。粒子群算法的最初形式是基于如鸟群和鱼群的社会心理原则，它最早是被 出的(1995)。在粒子群算法中，每一个候选解被 表示成一个粒子。一组候选解被称为一个群， 群 由在多维搜索空间 中 飞行的粒子组成。在飞行期间，每一个粒子根据它自己的经历调整位置也通过交流与它的邻居粒子相互合作。当一个粒子遇到一个有 较优秀 的解，这个解周围的区域会由群体进一步探索。因此，粒子群算法把局部搜索和全局搜索相结合。 2006 年， 人 成功 把粒子群算法应用于 型的参数搜索 (2006)。 以上提到的这些算法在进行生物网络模型的参数 搜索问题都取得了一定的成果，但是，由于生物网络本身所具有的复杂性，还不存在一种算法可以解决所第 1 章 引言 7 有参数搜索问题。因此，还需要开发新的算法来继续解决建模中的参数搜索和参数优化问题。 因芯片技术简介 在进行 生物网络 建模研究过程中，经常需要利用训练集学习一些无法通过生物实验直接进行测量的关键信息，如网络结构、模型参数以及系统初始状态等等。训练集数据通常需要同时包含多种分子在不同条件下或不同时间点上的浓度，这些数据的获取需要特殊的实验手段，基因芯片技术是目前被广泛应用的高通量实验技术 (1983; 1992)，可以同时测量成千上万分子的浓度，这些信息为生物网络模型学习提供了大量可用的数据，下面我们将对这种技术进行介绍。 随着人类基因组 计划 的 完成， 多种模式生物和病原体 的 基因组 序列被测量出来 ,基因序列数据以 指数级 速度 增长。传统 的 实验方法已无法系统地 解释 日益庞大的基因序列信息 ,研究者们迫切需要一种新的 实验 手段 ,以便高通量地 同时 研究众多基因在 不同 生理、病理状态下的表达变化 ,从而揭示 出它们的功能、相互作用与 调控关系。在 这种 背景下 , 20 世纪 80 年代末基因芯片技术应运而生 ,它综合 利用微电子 与机械 、生物化学、分子生物学、新 材料以及 计算机和统计学等多学科的先进技术 ,实现了在 生物学研究中样品处理、检测与 分析过程的 自动 化、集成化和微型化 (2007)。近 些 年 来 ,基因芯片技术在疾病 基因发现、疾病分子水平 的诊断、基因功能注释 、多靶位超高通量药物筛选以及 生物 网络推导 等医学与生物学领域得到广泛应用 (1995)。 基因芯片又称 片或 阵列。其原理 是采用光导原位合成或显微印刷等方法将大量特定序列的探针 分子密集有序地固定在经过特殊处理的硅片、玻片或 硝酸纤维素膜等载体上 ,然后加入标记 好 的待测样品 ,进行 杂交 ,通过杂交信号的强弱及分布 ,来分析待测分子的 数量 ,从而获得待 检样品的遗传信息。其工作原理与经典的核酸分子杂交 实验 （ 如 迹杂交 ） 一致 ,都是应用已知核酸序列与互补的靶序列杂交 ,通过检测 杂交信号进行定性与定量分析。经典杂交方法 是将靶序列 固定 ,而基因芯片技术固定的 则 是已知探针 ,因此基因芯片属于 一种反向杂交。基因芯片能够同时分析数万个基因 ,进行高通量筛选与检测分析 ,解决了传统核酸印迹 杂交技术操作复杂、自动化程度低 与 检测 待测分子数量少等不足。根据所 使 用探针 的 类型 ,基因芯片可分为 片和寡核苷酸芯片 ； 根据检测目的又可分为表达谱芯片和单核苷酸多态性 芯片。随着微阵列技术在生命科学 其他 领域的延伸 ,基因芯片概念已 被 泛化到生物芯片 ,包括基因同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 8 芯片、蛋白质芯片、糖芯片、细胞芯片、流式芯片、组织芯片和芯片实验室等。 目前被广泛应用的 基因芯片数据一共分为两大类：一类是扰动实验(因芯片数据，通常是敲除某个特定基因，研究其下游基因表达的变化效应， 从而 确定与 该基因存在调控关系的基因 (2000)；另一类是时间序列 (因芯片数据，可以反映一组基因在生命活动周期的时间序列条件下的表达水平的动态变化，其表达水平动态变化的时间延迟 关系可反映基因调控关系 (2002)。 目前，这两类芯片数据在生物系统建模中都经常被用到，并且已经针对它们开发出了很多专门进行芯片数据处理的软件。 文研究内容 本文主要针对 生物网络 建模过程中模型参数 搜索 算法进行研究，在对经典参数学习算法进行研究的基础上，分析各种算法的优点与不足， 然后提出了一种基于禁忌搜索和差分进化算法的参数搜索 算法。我们首先使用人工数据对该算法进行试验，结果表明该算法具有良好的搜索性能，可以快速地搜索到 模型的近似最优参数 ，相较于经典算法，寻得最优解的概率更高。 紧接 着，我们针对 大鼠 体节发生这一具体生物学问题，对调控这一过程的信号转导通路建立数学模型，根据一组基因芯片数据应用我们的算法搜索模型参数。 利用搜索到的参数进行模型模拟，结果显示新建立的模型可以准确模拟生物学实验结果。这说明，我们建立的模型是真实的生物网络的准确模拟，进一步证明我们所提出的算法在解决生物网络建模中参数 搜索 问题的有效性。 全文共分五章，主要内容概述如下： 第 1 章 引言。 本章首先 对 生 物网络 相关的 生物学 背景 和 生物网络 建模的研究背景进行了介绍，然后 对生物网络建模过程中的参数搜索算法的研究现状进行介绍。接下来，对参数搜索算法中产生训练集时用到的关键技术 后对本文的结构进行介绍。 第 2 章 生物网络模型参数搜索算法概述。 本章对生物网络建模中经 常使用的算法进行详细研究，指出各种算法的流程、应用背景和优缺点 及改进 策略 。 第 3 章 基于禁忌差分进化的参数搜索算法 。本章对禁忌搜索和差分进化算法进行 介绍，分析各自的优点与不足，然后提出了一种 综合 这两种算法 优点 的混合算法 法。对算法的流程进行 了 详细描述。 第 4 章 基于人工数据的实验结果 。 本章我们通过已经创建好的模型构建一组人工训练集，对本文所提出的参数搜索算法进行了实验且对实验结果进行了分第 1 章 引言 9 析。同时，我们把本文提出的算法与经典算法进行了性能比较，发现我们的算法搜索能力更强，收敛速度更快。 第 5 章 真实生物网络模型构建实验 。本章我们针对大鼠体节发生这一真实生物学过程，利用我们提出的算法构建出调控这一过程的信号转导网络模型，通过模拟实验对模型的准确性进行了验证，进一步说明算法在进行模型参数搜索方面的优秀性能 第 6 章 总结与展望 。 对本文的主要研究内容进行了总结，并提出了下一步的研究方向。 同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 10 第 2 章 模型参数学习算法概述 11 第 2 章 生物网络 模型参数 搜索 算法概述 在创建生物网络的数学模型过程中，由于生物学实验无法直接测量建模所需的 全部 信息，如基因调控网络的结构、基因间的调控强度 以及 生化反应 的各种 速率等。但是 利用 生物 学实验可以测得度量这些信息的各种数据，如基因芯片数据等，根据这些数据，研究人员可以推测出所需要的其它信息，这就需要设计相应的算法，目前，已经有一些算法应用于 生物网络模型的参数 搜索 ，我们在本章将对这些算法进行一一介绍，理清算法流程，找出优点与不足，为下一章 提出新算法奠定理论基础。 部搜索算法 介绍 在参数搜索问题中，局部搜索是在局部范围内搜索最优解的一种元启发式算法 (2008)。局部搜索从一个初始解出发，然后反复搜索解的邻域，如果搜索到更优秀的解则移动到该解 ， 并从该解出发继续执行搜索，否则就返回当前解。局部搜索的优点是简单、灵活、易于实现且搜索速度快。缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。 因此，局部搜索只适用于 搜索空间是 单峰 的情况下，对于 多峰 问题需要设计搜索能力更强的算法来解决。 局部搜索广泛应用于人工智能、数学、运筹学、工程学和 生物信息学 等领域中各种很难找到全局最优解的计算问题。 该算法的流程如下。 局部搜索算法从一个候选 解开始， 该解一般采用随机方法产生，构建出初始解之后在其邻域中进行反复探索， 每当搜索到比 当前解更优秀的解就把当前解移动到更优的解，直到在邻域中找不到更优解为止，此时的当前解即为最优解。 所以要使用局部搜索算法必须首先在搜索空间中定义邻域。比如，在最小顶点覆盖问题中，一个覆盖的邻域可以是只改变一个顶点 所能够到达的所有 覆盖；在布尔可满足性问题中，一个变量赋值的邻域可以是只改变一个变量的值 便 能到达的所有赋值。对于同一个问题可以有 多种邻域的定义 方式。如果一个局部优化算法将邻域定义为 改变 k 个成分能够到达的 所有解，那么 这个算法就被 称为 通常， 候选解的邻域包含 很 多个解。所谓局部搜索，就是只根据邻域中的信息来决定移动方向。如果 每次都 选择最大化目标函数的解， 那么这种局部搜索算法又可以叫做爬山算法。当邻域中已经没有比当前更 优的解的时候，局部搜索就困在了局部最优解。为了 跳出局部最优解，可以使用很多种策略，包括从不同的初始解开始多次运行 算法，或者使用更 加 复杂的策略如模拟退火。 局部搜索可以设计成在运行一定步数 后终同济大学 硕士学位论文 基于禁忌差分进化算法的生物网络模型参数搜索研究 12 止，或者连续 步没有寻找到更优解时终止。 因此， 局部搜索属于 一种任一时间算法：即便它 在运行中被强制 中止，也能 够 返回正 确的解。局部搜索是典型的近似寻优 算法，因为它找到的解不一定是最优的。即便没有中断算法执行，也可能因为陷入局部最优而无法找到更好的解。对于某些 特定 问题，可以定义一个非常大