（计算机应用技术专业论文）基于免疫遗传算法的基序识别方法的研究.pdf

幕r f 免疫遗传算法的堆序识别方法的研究 摘要 从生物序列中识别基序是生物信息学中的一个热点问题，也是生物学中研究 基因调控机制的基础计算问题之一。由于基序长度较短、非百分百保守以及生物 数据复杂性高等原因，通过计算方法识别基序仍旧是人们研究基因转录调控过程 的一大难点。遗传算法由于其鲁棒性强、随机性、全局性以及适于并行处理等优 点，近年来被越来越广泛地应用到基序识别问题的求解中，并成为重要的发展方 向。 虽然遗传算法已形成一套较为完善的算法体系，但早熟收敛、随机漫游等不 足限制了其应用。生物学领域的研究发现，生物免疫系统可以很好地保持种群多 样性，抑制早熟收敛和限制随机漫游。因此，利用免疫原理可以有效地改进和提 高遗传算法的性能。 针对遗传算法缺少种群多样性保持策略的不足，考虑生物免疫系统的优点， 本文将浓度调节机制引入到遗传算法中，提出了一种基于浓度机制的免疫遗传算 法，并将其应用于基序识别。根据基序识别问题定义和基序的表示方式，设计了 新的抗体亲和力和抗体浓度计算公式，模拟生物体免疫行为，在遗传算法比例选 择算子的基础上，添加了浓度调节因子来抑制高浓度抗体的繁殖，使提出的算法 能够有效地保持种群多样性，避免早熟收敛现象的发生。实验结果表明该算法有 较好的基序识别效果，能够在较长序列中识别基序，在一次运行中识别多基序。 为了克服算法在遗传过程中随机搜索造成的种群退化现象，本文模拟人工免 疫系统，引入疫苗的调控作用，提出了一种基于疫苗机制的基序识别算法，通过 疫苗提取、疫苗接种和免疫选择来抑制种群的退化现象，加快算法收敛速度。通 过在模拟生物数据和真实生物数据上的实验，说明该算法进一步提高了基序识别 效果。 关键词：基序识别；遗传算法；免疫机制：浓度调节；免疫疫苗 a b s t r a c t m o t i fd i s c o v e r yi nb i o l o g i c a ls e q u e n c e si s ah o ti s s u ei nb i o i n f o r m a t i c sa n da f u n d a m e t a lc o m p u t a t i o n a lp r o b l e mw i t hi m p o r t a n ta p p l i c a i t o n si nu n d e r s t a n d i n gg e n e r e g u l a t l o n a st h em o t i fw i t hv e r ys h o r t1 e n g t h ，n o n h u n d r e dp e r c e n tc o n s e r v a t i v e 。 a n dt h e c o m p l e x i t yo fb i o l o g i c a ld a t a ， t h ei d e n t i f i c a t i o no fm o t i f s t h r o u g h c o m p u t a t i o n a lm e t h o d si ss t i l lam a j o rc h a l l e n g e b e c a u s eo fi t sr e l a t i v es u p e r i o r i t vt o t h et r a d i t i o n a io p t i m i z a t i o na l g o r i t h m ，e v 0 1 u t i o n a r ya l g o r i t h mh a sr e c e n t l yb e e nm o r e w i d e l ya p p l i e dt ot h em o t i f d i s c o v e r yp r o b l e m ，a n db e c o m e sa ni m p o r t a n td i r e c t i o no f d e v e l o p m e n t t h el a c ko fp r e m a t u r ec o n v e r g e n c ea n dr a n d o mr o a m i n g l i m i t sg a ，sa p p l i c a t i o n p e o p l e6 n dt h a tb i o l o g i c a li m m u n es y s t e mc a nk e e pt h ed i v e r s i t yw e l l ，a n di n h i b i t p r e m a t u r ec o n v e r g e n c ea n dr a n d o mr o a m i n g t h e r e f o r e ，w ec a ne f k c t i v e l yi m p r o v e a n de n h a n c et h ep e r f o r m a n c eo f g e n e t i ca l g o r i t h mb yu s i n gt h ei m m u n et h e o r v c o n s i d e r i n gt h el a c ko fp o p u l a t i o nd i v e r s i t ym a i n l a i nw i t hg e n e t i ca l g o r i t h ma n d t h ea d v a n t a g e so f b i 0 1 0 9 i c a li m m u n es y s t e m ，w ei n t r o d u c ec o n c e n t r a t i o nr e g u l a t i o n i n t o g e n e t l ca 】g o r l t h ma n d p r o p o s e a ni m m u n e g e n e t i ca l g o r i t h mb a s e do n c o n c e n t r a t l o nm e c h a n i s ma n da p p l yt om o t i f d i s c o v e r y w ed e 6 n en e wf o r m u a l so f a n t i b o d ya 艏n i t ya n da n t i b o d yc o n c e n t r a t i o na c c o r d i n gt ot h ed e f i n i t i o no fm o t i f d l s c o v e r yp r o b l e ma n dt h er e p r e s e n t a t i o no fm o t i f s b a s e do nt h ee l e c t i o no p e r a t o ro f ( j a ，w ei n t r o d u c eac o n c e n t r a t i o nr e g u l a t i o no p e r a t o rt oi n h i b i tt h er e p r o d u c eo f h ig h c o n c e n t r a t i o n a n t i b o d y s t h e p r o p o s e dm e t h o dc a n e f 恐c t i v e l y m a i n t a i nt h e p o p u l a t l o nd i v e r s i t ya n di n h i b i tp r e m a t u r ec o n v e r g e n c ep h e n o m e n o n e x p e r i m e n t a l r e s u l t ss h o wt h a tt h em e t h o dc o u l d6 n dm o t i f si nr e l a t i v el o n gs e q u e n c e s a n dm u l t i p l e m o t i f si nas i n g l em n i no r d e rt oi n h i b i tt h ed e g r a d a t i o nd u r i n ge v o l u t i o n ，w e i n t r o d c et h er e g u l a t i o no f v a c c l n ea n dp r o p o s ea nm o t i fd i s c o v e r ym e t h o db a s e do n i n l m u n ev a c c i n e t h e p o p u l a t i o nd e g r a d a t i o nc o u l db ew e l li n h i b i t e db ye x t r a c t i n gt h ev a c c i n e ，v a c c i n a t i o n a n dl m m u n l z a t l o nc h 0 1 c e ，s ot h ec o n v e r g e n c ec o u l db e s p e e du p e x p e r i m e n t a lr e s u l t s s h o wt h a tt h em o t i f d i s c o v e r ya b i l i t yh a sb e e nf u r t h e ri n l p r o v e d k e y w o r d s ： m o t i f d i s c o v e r y ，g e n e t i ca l g o r i t h m ，i m m u n e m e c h a n j s m ， c o n c e n t r a t i o nr e g u i a t i o n ，i m m u n ev a c c i n e i i i 基于免疫遗传算法的堆序识别方法的研究 插图索引 图2 1 已知基序g c r l 的真实用例，及其矩阵表示和一致串表示8 图2 2 基序g c r l 的序列l o g o 表示8 图3 1 基于浓度机制的i g a 流程图2 1 图3 2 基于疫苗机制的i g a 流程图2 2 图4 1i g a m d c 的流程图2 5 图4 2 最佳匹配抗体的平均匹配值变化趋势3 2 图4 3 抗体平均适应度的变化趋势3 2 图4 4 最佳匹配值和最佳匹配抗体适应度的变化趋势3 3 图5 1i g a m d v 疫苗机制流程图3 6 图5 2 最佳匹配抗体的平均匹配值变化趋势4 0 图5 3 抗体平均适应度的变化趋势4 l 图5 4 最佳匹配值和最佳匹配抗体适应度的变化趋势4 2 v i 湖南大学硕 ：学位论文 附表索引 表2 1 基序识别算法一览表1 6 表4 1 单基序模拟生物数据中植入的j a s p a r 基序3 0 表4 2 多基序模拟数据中植入的j a s p a r 基序3 0 表4 3 单基序实验结果31 表4 4 算法可识别出基序的序列长度3 2 表4 5 多基序识别结果3 3 表4 6 真实肌肉数据实验结果3 4 表5 1 单基序实验结果3 9 表5 2 算法收敛代数一4 0 表5 3 多基序实验结果一4 1 表5 4 真实肌肉数据实验结果一4 2 v i i 湖南入学硕l ：学位论文 1 1 研究背景和意义 第1 章绪论 在人类基因组计划取得根本性进展，特别是全部序列图绘制完成的今天，人 类基因组的研究己全面进入信息提取和数据分析的全新阶段。从海量的生物数据 中揭示生物内涵，得出对人类有用的信息是生物学、数学家和计算科学家所面临 的一个严峻挑战。生物信息学就是为迎接这一挑战而发展起来的一门新兴学科， 是当今生命科学和自然科学的重大前沿领域之一，也是2 l 世纪自然科学的核心领 域之一。它通过对生物学实验数据的加工、注释、存储、检索与分析等过程，进 而达到提取生物数据所蕴含的生物学意义的目的。 生物进化中最重要的过程就是基因表达，它是d n a 利用基因信息进行转录的 过程。转录因子在这一过程中起到很重要的作用，在基因表达时通过绑定到d n a 链来控制蛋白质的合成。因此识别转录因子是研究基因表达的关键步骤，但因为 生物序列的复杂性，转录因子的识别非常困难。在基因转录表达起始，转录因子 会绑定到基因转录起始位点( t s s ) 处的转录因子绑定位点( t f b s ) 上，通过激活或者 抑制基因的转录机制来调控基因的表达，转录起始决定着是否转录某一蛋白质【2 】， 而转录因子绑定位点决定着何时哪一个基因被表达。转录因子绑定位点，又称为 基序，是d n a 序列中重复出现的具有特定保守功能的信号位点，通过研究基序可 以帮助人们达到研究转录因子的目的。但识别基序也并不简单：首先，基序的长 度都很短，一般是几到几十个核苷酸，并且有一定的可变性，而不是百分百保守 的；其次，它们所处的序列的长度从几百个核苷酸( 如酵母菌基因) 到几千个核 苷酸( 如人类基因调控区域) ，而空间分布变化较大，没有固定位置，一般出现在 基因转录起始位点的上游区域，但也有可能出现在下游甚至编码序列中1 3 】；最后， d n a 序列是复杂的，核苷酸可能有插入、删除或变异等现象，这对基序识别产生 了很强的噪音污染【4 】 现代生物学的一大挑战就是研究基因表达的复杂机制，而基序识别是研究基 因表达复杂机制的重要任务之一。从生物序列中发现基序，对研究共表达基因和 共调控基因中的绑定位点、理解转录调控机制、建立转录调控网络等问题具有重 要意义，同时有助于确定基因功能和阐明生物序列间的进化关系，有助于从生物 物理学和病理学上研究基因和蛋白质之间的交互关系、细胞发育和细胞反应等方 基于免疫遗传算法的基序识别方法的研究 面【”，有助于确定潜在的药物靶点、解决人类各种疾病6 1 。 近年来，随着大规模d n a 测序成果的积累和生物芯片等高通量生物技术的 发展，通过生物实验手段识别基序的技术越来越多，如d n a s ei 足迹法、s e l e x 、 c h i p 、凝胶迁移阻滞法、g e l s h i f t 等【7 1 ，但这些技术大多非常昂贵和耗时，同时 对序列中的噪声不敏感，分辨率( 实验所识别的d n a 片段长度) 不高。例如 c h i p - c h i p 技术，其分辨率在1 0 0 0 b p 左右，远远长于基序的长度，需要用其他技 术进一步分析结果。因此可以借助计算方法识别基序，以弥补生物实验技术的不 足。虽然计算方法做不到非常准确，但在生物实验条件无法做到的情况下，识别 结果可以作为一盏明灯，指导生物学家开展生物实验。 遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种 自适应全局概率搜索算法，可以直接对序列进行操作，具有鲁棒性强、随机性、 全局性以及适于并行处理的优点。近几年的研究发现，将遗传算法应用到基序识 别中，利用遗传算法的优势，可以更好的识别基序。但传统的遗传算法依然有许 多不足，例如对局部空问的搜索问题不是很有效，随机漫游，个体的多样性减少 得很快易造成早熟收敛等，这些不足的存在限制了遗传算法的应用。 生物学领域的研究发现免疫原理对改进和提高遗传算法的性能具有重要的启 迪作用【8 ：自然界中生物体的免疫系统具备很高的智能级，免疫行为可以很好地保 持多样性，有效地限制随机漫游，抑制种群退化。因此，研究免疫优化理论以及 模拟免疫优化行为改进遗传算法成为相当有意义的科研课题。 1 2 国内外的研究现状 1 2 1 基序识别算法 从g a l a s 【9 】等第一次采用计算方法解决基序识别问题以来的二十多年里，基 序识别一直是生物信息学中重要的研究课题，人们将各种计算方法和搜索策略应 用到该课题上，提出了很多求解基序识别问题的模型和算法。 过去由于计算机计算能力和生物实验技术的限制，大部分算法都是针对简单 的基序识别问题提出的，也就是在原核生物较短序列中识别较短基序，并且忽略 基序的变异、插入或间隔等生物现象。近期，随着生物学中各项技术的迅速发展， 生物信息数据的急剧膨胀，计算能力的日新月异，人们对求解基序识别问题的算 法要求也越来越高，为了更真实地反映真实生物序列中实际基序的识别问题，提 出了一些更复杂的基序识别模型 1 0 _ 2 1 ，随之产生了大量识别算法。根据使用的基 序表示方式的不同，基序识别算法可以分为精确算法和非精确算法两类。 2 湖南大学硕 ! 学位论文 精确算法又称为单词计数法( w o r d c o u n t ) ，是基于基因上游序列中的低聚核 苷酸串的频率分析，将一个串出现的次数与其期望次数进行比较来衡量显著代表 性，然后将具有显著代表性的一些相似串( 基序用例) 比对组合成基序。、o r d u p 【”】 算法是比较早的精确算法，通过计算输入序列中所有子串的统计意义来识别基序， 算法搜索空间较大、执行效率低。y m f 【1 4 】算法能够识别包含字符的基序( 表 示四种核苷酸具有相同的分布概率) ，但只适合查找长度为8 的基序。g e m o d a 【 算法将基序识别问题转化为在图中搜索最大团的问题，能够识别更长的基序，但 执行效率很低。c c m f 【l5 】算法采用彩色编码技术降低了搜索最大团的空问，有效 提高了算法运行效率。p r o j e c t i o n 【1 6 】算法采用随机投影技术识别基序，初试参数的 选择对算法识别结果的影响很大。u p n t 【1 7 】算法采用统一投影策略，缩小了投影 空间，优化了算法整体性能。 非精确算法是基于矩阵模型的近似算法，对基序的信息进行某种近似描述， 然后通过不断迭代优化调整基序信息，直至迭代终止。g i b b ss a m p l i n 毋】算法通 过随机采样不断优化基序模型直到识别出具有显著统计性的基序，执行效率高， 但不能保证全局最优解。i n f o g i b b s 【1 9 】算法采用位点移动策略来解决随机采样容易 陷入局部最优解的问题，提高了识别的效果。m e m e 【2 0 】算法采用期望最大化方法 迭代优化来识别基序，搜索起始点的选择对识别结果的影响较大，算法容易陷入 局部最优解。m c e m d a 】算法使用蒙特卡洛方法来解决期望最大化的局部搜索 现象，较m e m e 算法有着更好的识别效果。e c 【2 2 】算法使用遗传算法识别基序， 首先随机产生一定数量的初始个体，然后通过遗传过程中交叉和变异操作不断迭 代优化个体，直到算法收敛输出种群中适应度最高个体作为识别出的基序。 p c e a 【2 3 】算法先采用聚类方法对种群进行聚类再进行遗传操作，算法能够在较长 序列中识别出基序。g a l f p 【2 4 】算法在遗传过程中添加了局部过滤和自适应后处 理技术，可以有效减少假阳性结果的产生，并能识别出保守度较低的基序。 由于基序识别问题的复杂性，目前没有一种算法能够识别出所有正确的已知 或未知基序，精确算法虽然能够保证搜索到最优解，但算法复杂度高，不适应大 数据量长基序识别问题，而非精确算法虽然执行效率较高，但由于基于局部搜索 技术，很难保证算法结果的全局最优。同时还有一些更加难以处理的问题需要解 决：基序长度是可变的，而大多数算法只能识别定长的基序，需要预先设定待识 别基序的长度或者长度范围：由于计算复杂性，在长序列集中识别长基序依旧困 难；输入序列中可能某一条序列没有基序用例，或者有多条基序用例，加大了基 序所处环境的噪音；大多数算法只能解决单基序问题，而一些能够识别多基序的 幕于免疫遗传算泫的基序识别方法的研究 算法也是采用标记识别结果多次运行算法的方法，不能有效的反映基序的关联关 系；目前提出的算法普遍存在假阳性率偏高的问题，引起假阳性的主要原因是基 序很短，而生物序列中存在很多与基序核苷酸分布相同但没有转录因子绑定功能 的串；基序识别算法依赖于预先构建的共调控的基因集合，而这些集合通常来自 于基因功能的分析( 如c h i p c h i p 实验) ，不易获得，从而导致算法局限于对单物 种的分析。 1 2 2 免疫遗传算法 生命科学与工程科学的相互交叉，相互渗透和相互促进是近代科学技术发展 的一个显著特点，受生物界进化过程的启发，进化算法在科研和实际工程中的应 用越来越广泛，并取得了较好的效果。1 9 8 3 年，g o l d b e r g 在其博士论文中第一次 将遗传算法应用于实际优化设计中，从此遗传算法得到了广泛的应用。虽然遗传 算法有着其他传统优化算法无可比拟的优点，但在应用过程中，人们也发现其存 在很多局限性，例如对局部空间的搜索问题不是很有效，随机漫游导致进化种群 退化，个体的多样性减少得很快易造成早熟收敛等，于是很多学者提出了相应的 解决办法。 生物学领域的研究发现免疫原理对改进和提高遗传算法的性能具有重要的启 迪作用，自然界中生物体的免疫行为可以很好地保持多样性，有效地限制随机漫 游，抑制种群退化。1 9 9 5 年，美国新墨西哥大学的s f o r r e s t 和洛斯阿拉莫斯实 验室的a p e r e l s o n 首先提出了免疫系统遗传建模的方法 25 1 ，此后针对免疫遗传 算法的研究不断发展，人们模拟免疫行为中的抗体记忆、抗体的抑制、促进、抗 原识别和疫苗等免疫行为相继提出新的免疫操作，逐渐完善了免疫遗传算法。 1 9 9 7 年，c h u n l 2 6 】等基于体细胞理论和免疫网络理论提出了一种免疫算法， 定义抗原为目标函数，抗体会问题的解，抗原和抗体之间的亲和力作为解答的联 合强度。t a z a w a 【2 。7 】等利用小生境技术提出了一种遗传特性与免疫系统相结合的免 疫遗传算法。j a n g s u n g c h u n 【2 8 】等基于信息熵理论设计了一种免疫优化算法，模 拟免疫记忆现象设计了最优保持技术，利用几类特别的测试函数，将设计的免疫 优化算法与遗传算法、进化规划进行优化能力的比较测试，验证了免疫优化算法 具有更好的寻优能力。s h y h j i e r 【2 9 】利用平均信息熵来计算抗体问亲和力，再利用 简单遗传算法的交叉变异算子设计了免疫算法优化燃料调配和热量生成问题。在 国内，王磊、焦李成【3o 】等人模拟自我免疫机制设计了一种免疫遗传算法应用于 t s p 问题的优化求解，并证明了算法的全局收敛性，其算法核心就是加入了最优 保持操作。之后很多学者提出了改进的方法并应用到各种领域。文 31 借鉴生物 4 湖南人学硕i j 学位论文 医学工程中的人工免疫概念对免疫遗传算法进行改进，使用两种疫苗对种群进行 疫苗接种，并在进化过程中不断进行疫苗修正。文 3 2 模拟一类抗体可结合多个 抗原并逐步达到亲和度成熟的机制，设计了一种多模态免疫进化算法，提出了正 选择、超变异等算子。文 3 3 】提出了一种自适应的免疫遗传算法，交叉概率和变 异概率根据种群中的多样性自适应调节，并利用疫苗接种提升个体的存活能力， 算法应用到多序列比对中，取得了较好的效果。文 3 4 】提出的免疫遗传算法利用 免疫系统中的小生境技术保持种群的多样性，利用免疫记忆策略加快优良个体的 产生，利用共享机制和克隆抑制策略避免早熟收敛，并将算法应用到实际应用中 解决了硅钢片优化排样问题。文【3 5 提出了一种求解柔性作业车间调度问题的自 适应免疫遗传算法，引入了免疫算予和种群的自适应调节策略来保持群体的多样 性。 从生物处理信息的角度看，免疫系统具有多样性，免疫自我调节，免疫记忆， 分布式系统，动态适应，多时间尺度进化系统等特性，能有效地改进和提高遗传 算法的性能。目前免疫遗传算法已被广泛应用于优化问题、计算机安全、控制工 程、数据挖掘、机器人控制和欺诈检测等领域，研究免疫优化理论以及模拟生物 免疫行为改进传统进化算法具有重要的理论和实践意义，并已成为进化算法研究 的热点。 1 3 本文的主要工作及章节安排 遗传算法已经被广泛应用到基序识别问题的求解中，但遗传算法固有的早熟 收敛、种群退化等问题限制了其在基序识别问题中的应用。本文在总结国内外学 者研究成果的基础上，对基于遗传算法的基序识别方法进行了讨论，并提出了基 于免疫遗传算法的基序识别方法，以期对基序识别技术的发展起到积极作用。主 要工作有： ( 1 ) 介绍了基序识别算法的研究现状以及基序识别问题的基本理论，包括基 序的表示方式、基序识别问题的定义和常用的打分函数；根据采用的基本方法的 不同，将基序识别算法分为基于穷举思想、基于启发式思想和基于机器学习方法 三类进行阐述，并分析了一些经典的基序识别算法的基本思想以及局限性；阐述 了遗传算法的原理及存在的不足、免疫遗传算法的优点及其在基序识别问题中应 用的可行性； ( 2 ) 提出基于免疫遗传算法的基序识别方法，将抗原作为目标函数，抗体作 为问题的解，模拟免疫系统的浓度调节机制，利用浓度调节遗传过程中的选择策 基于免疫遗传算法的基序识别方法的研究 略，保持抗体种群多样性，避免算法搜索过程中的早熟收敛现象，采用多点交叉 和多点变异算子，更快地改变解空间以扩大进化过程的搜索空间，采用精英保留 策略，保留进化中每一代的最优个体的性状，促进算法的收敛速度； ( 3 ) 在提出的算法基础上，为修正进化过程中交叉和变异算子的盲目性，模 拟人工免疫中的疫苗作业，在遗传过程中引入疫苗机制，通过疫苗提取、疫苗接 种和免疫选择三步抑制遗传算法中的种群退化现象，并采用记忆库保留记忆细胞， 进一步加快算法收敛速度。 本论文主要包括5 章，各章内容安排如下： 第l 章绪论。主要介绍论文研究的背景和意义，基序识别问题的国内外研究 现状，免疫遗传算法的发展及前景，以及本文的主要工作。 第2 章基序识别算法研究与分析。首先介绍了基序识别问题的基本内容，包 括基序表示方式、基序识别问题的定义以及常用的打分函数。然后介绍了基序识 别算法的基本策略，并分三类分析了各种基序识别方法的基本思想和优缺点。 第3 章免疫遗传算法。首先介绍遗传算法的原理和局限性，分析引入免疫机 制改进遗传算法的必要性，然后按引入的免疫机制的不同，将免疫遗传算法分为 基于浓度机制的和基于疫苗机制的两种，并分别进行阐述。 第4 章基于浓度i g a 的基序识别算法。提出了一种基于免疫浓度机制的基序 识别算法，利用免疫系统的浓度调节机制保持抗体种群的多样性，避免早熟收敛。 通过在模拟生物数据和真实生物数据上的实验显示了算法的有效性。 第5 章基于疫苗i g a 的基序识别算法。在第4 章提出的算法的基础上，引入 人工免疫中的疫苗机制，通过疫苗提取、疫苗接种和免疫选择来提高种群整体适 应度，修正交叉和变异算子的盲目性，抑制退化现象，提高算法收敛速度。通过 实验验证了算法识别基序的效果。 最后，总结论文的研究工作并对进一步的研究工作做了展望。 6 湖南人学硕i j 学位论文 2 1 引言 第2 章基序识别方法概述 基序识别是破译基因调控机制的关键环节之一，目前虽已产生许多利用生物 实验识别基序的方法，但由于价格昂贵、耗时久等原因限制了其应用，因此利用 计算方法识别基序成为该领域的趋势。 随着生物数据的海量产生以及计算方法的不断改进，越来越复杂的基序表示 方式、基序识别问题模型和打分函数被提出，同时产生了大量基序识别算法。根 据算法使用的基本方法的不同，本章将基序识别算法分为三类进行介绍，分别是 基于穷举思想的、基于启发式思想的和基于机器学习的，并选择一些经典的算法 对其思想和优缺点进行了阐述。其中，基于穷举思想的算法能够保证全局最优解， 但运行效率不高；基于启发式思想的算法有较高的运行效率，但难以保证识别的 精度；基于机器学习的算法虽不能保证识别出全局最优解，但能在识别精度和执 行效率之问的谋求较好平衡。 2 2 基序的表示方式 利用计算方法进行基序识别，首先需要解决的问题就是采用什么方式表示基 序。目前虽然有大量的基序识别算法，但普遍采用的基序表示方式基本上是两种： 一致串表示【3 6 】和矩阵表示 37 1 。 一致串( c o n s e n s u ss t r i n g ) 表示方式也就是简单的字符串表示，即对每个位置 选择一个最可能出现的碱基组成一个序列表示基序，这里的字符对于d n a 序列 取a 、c 、g 、t ，对于蛋白质序列用i u p a c 氨基酸代码表示。 矩阵( m a t r i x ) 表示方式，也称简图( p r o f i l e ) ，采用基序用例中对应位点碱基出 现的频率来描述基序。如位置频率矩阵p f m ( p o s i t i o nf r e q u e n c ym a t r i x ) 表示方式， 它是一个4 ，的矩阵，矩阵中每行对应着一种核苷酸，每列对应着基序中的一个 位置，第f 行，列的元素是基序中第，位出现核苷酸f 的概率，每列元素的和为1 。 其他常见矩阵还有p s s m ( p o s i t i o ns p e c m cs c o r i n gm a t r i x ) 和p s p m ( p o s i t i o n s p e c i f i cp r o b a b i l i t ym a t r i x ) 等。 7 基于免疫遗传算法的基序识别方法的研究 y a l 0 3 8 wa t f c c ) y a i 。n 3 纠v ( 1 t ( ： y a l 0 3 8 w ( 1 t e c y 【r o l 2 w 1 t c c y f r 0 l2 wf 叮t c c y ( r o i2 wc t t o c y d r 0 5 0 ( ：( a t c c y d r 0 5 0 cc a 丁c c y d r 0 5 0 ( c l 1 c c y d r f 蓐0 fc r r c c y h r i7 4 wc a t c c y o l 抑8 6 cc r r c c g c r l 矗t ，驴雠y e u l x 确矗搿矬哪 l 2345 ao 0 80 2 5o oo o0 o co 。9 2n oo o1 oi o go 0o oo 0o o0 o to o l 7 5i oo 0o o c 口玎s c n 翻l 1 5c1tcc 图2 1 已知基序g c r l 的真实用例，及其矩阵表示和一致串表示 图2 1 使用来自s c p d 数据库【3 8 】的酵母菌转录因子绑定位点来举例说明基序 的一致串表示法和矩阵表示法。图上方是已知基序g c r l 在生物序列中的1 2 条 真实用例，下方分别是g c r l 的p f m 表示方式和一致串表示方式。 一致串表示方式仅选择当前位置的最大保守核苷酸，牺牲了特异性也丢失了 敏感性，而矩阵表示方式假设基序中不同位置间是相互独立的，每个核苷酸对转 录因子与d n a 序列的结合能的贡献是独立的，忽略了碱基之间的相互作用，即 所谓的可加性假设。b e n o s ”】等分析后表明，虽然可加性假设并不总是成立的， 矩阵并不完美，但它仍是对基序集合能力的一个较好近似。 序列l o g o 【4 0 】是一种对比对序列的图形化表示方式，图2 2 是已知基序g c r l 的基序l o g o ，每位的总高度表示该位的核苷酸保守程度，而每个核苷酸的高度表 示其在该位出现的频率。 t c c 图2 2 基序g c r l 的序列l o g o 表示 2 3 基序识别问题的定义 基于基序的表示方式，基序识别问题可分为两种，其输入数据都是n 条长度 为，的d n a 序列组成的集合s = 墨，曼，& ) ，每条序列都由有限字符集 z = 弘，c ，g ，r ) 构成，两种识别问题可简单定义如下： 定义一 基于一致串表示的基序识别问题是在s 中找到长度为彩的一致串& 和一组基序实例m = 确，朋：，m 。) ( 刀 = ) ，是序列l 的长度为国的子串，使 qi刊一， 善 湖南大学硕f ：学位论文 得海明距离和最小： “( & ，他) ( 2 1 ) 定义二基于矩阵表示的基序识别问题是在s 中找到一组基序实例 m = m 。，m 。) ( 以 = ) ，是序列s ，的长度为缈的子串，使得i c 得分最大： 圮= 芸莩删。g 警 亿2 ， 其中，以( ) 是刀条基序实例比对得到的位置频率矩阵第列碱基6 的频率值， p 。是碱基6 的背景频率( 一般来自s ) 。 l i 【4 1 1 对基序识别问题有着等价的定义，并证明了该问题是n p 难题。 2 4 常用的打分函数 基序识别算法一般都使用打分函数来评估基序模型的统计意义，评估结果能 够反映基序模型的生物相关性并区分真实基序模型与假阳性结果，从而输出具有 显著统计意义的基序模型作为识别的结果。 基于一致串表示的基序识别算法的打分函数一般都与海明距离相关，如海明 总距离、失配计数等。 基于矩阵表示的基序识别算法的打分函数比较多，包括信息内容( i c ) ，极大 先验对数似然率( m a p ) ，p - 玩m e ，乙d ，e 和，玩胁p 等【3 引。 ( 1 ) ，c 与枷p 圮基于s h a n n o n 信息理论，考虑了基序各位的保守性，对于长为脚的基序， 其，c 得分可计算为： 庀：至芝l 。g 孚 ( 2 3 ) 其中，m ，为4 聊基序矩阵模型中的元素，6 为碱基i 的期望频率，即碱基f 在 背景数据中出现的频率( 背景数据可以是整个输入序列集，也可以是除去待评估基 序模型外的剩余序列) ，即y 岛= l 。公式中的m ；i 考虑了每一位上碱基的保守性， 而1 0 9 ( 朋，6 ) 考虑了基序与序列中任一长度为m 的串( m m e ，) 的差异性。当基序每个 位置上只出现固定碱基时可以得到最大彤值，当基序每个位置上各个碱基出现的 频率相同( 均为2 5 ) 时得到最小，c 值。 ， ，c 只适合比较那些长度相同的基序，为了比较不同长度的，将，c 乘以基序 长度，就可以得到川尸： 9 基于免疫遗传算法的幕序识别方法的研究 脚2 喜芸伽啪g 等 亿4 ， 扭l 卢i坼 j c 和删p 都默认基序实例和背景数据的位置是独立的。 ( 2 ) 尸一玩胁p ： 假设基序问是相互独立的，那么某个给定的碱基出现在序列的任何位置只与 它在序列中出现的频率相关，所以在一条序列的任何位置发现一条给定串 缈= q 的概率可以计算为p ( 缈) = 兀p ( 哆) ，p ( q ) 为碱基哆在序列中出现的频 率。给定了p ) ，在长为以的序列中发现z 次串缈的概率可定义为： p ( x ：石，缈) ：f 以1 p ( 缈) x ( 1 一p ( 缈) ) 一一x ( 2 5 ) 、工 使用泊松近似后p ( x = x ，国) = 五。p 2 五! ，其中五= 印( 缈) ，则在长为珂的序列中 发现x 次或大于石次某，一m e ，的概率为p ( x 国) = j p ( x = f ，缈) ，这就是p 一玩胁p ， 它代表模型中出现分值超过随机基序的伪基序的概率。 ( 3 ) z - s c d 肥： 给定p ( 缈) ，可以计算串国在长为刀的序列中的期望出现次数，即e ( 缈) = 印( 缈) ， 以及它的方差砌，( 国) = 印( 彩) ( 1 一p ( 国) ) ，在此基础上，可以定义 z ( 咖警 ( 2 6 ) 其中锨( 国) 是串在序列中实际出现的次数。z - d 陀代表序列中候选基序分 值超过随机基序期望值的标准离差数，它考虑到了基序的保守性。 ( 4 ) ，一玩觑p ： 玩z “e 与z s c d 陀类似，但是不需要计算给定串缈的出现次数和期望出现次 数以及方差，而是定义如下： 椰) = 型铲 ( 2 7 ) ，一玩，“p 越大说明串彩出现的次数越多。 2 5 基序识别方法 2 5 1 基序识别方法的策略 自从g a l a s 【9 1 等第一次提出基序识别算法以来，产生了大量的应用于基序识 别问题的方法，根据不同的标准，它们可以被分为不同的类别，一般根据算法搜 索策略和基序表示方式的不同，可以将基序识别算法分为两大类：精确算法和非 精确算法。 l o 湖南人学硕f j 学位论文 精确算法大多使用穷举方法，在允许的最大错配数目内，试图列出所有可能 满足某一打分函数的长为，的子串( ，一m p ，) ，然后对这些，一m p 厂按照某些统计度量排 序，输出统计度量结果最高的作为识别出的基序。因为有4 7 个候选串要被评估， 所以这种方法一般运行速度很慢，适合于短基序的识别问题。利用优化的数据结 构如后缀树【4 2 1 ，精确算法的运行速度可以得到提高，能够很好的发现高保守度的 基序。但是由于基序都是非完全保守的，精确算法的识别效果不是很理想，较容 易识别出假阳性结果，其识别结果经常需要一些聚类系统的再处理【43 1 。精确算法 的最大优点是是能够保证识别全局最优解，同时，打分函数和搜索算法是分开的， 因而在打分函数的选择上较为灵活，大多数算法可以使用其他合理的打分函数。 比起精确算法，非精确算法需要更少的搜索参数，一般能识别更长的或者保 守度较低的基序。但精确算法依赖于调控区域的概率模型，对输入数据的微小变 化非常敏感，并且由于它们一般都利用了本地搜索技术，如吉布斯抽样、期望最 大化或者贪婪算法，所以不能保证发现全局最优解。非精确算法大多利用最大似然 方法或贝叶斯推理来评估基序模型，需要背景模型，目f ；i 马尔科夫模型成为建立 背景模型的标准【4 4 1 。 2 5 2 基序识别算法 在本章，根据算法使用的方法的不同，将基序识别算法分为三类：基于穷举 思想的、基于启发式思想的和基于机器学习方法的基序识别算法，并挑选了一些 经典的算法来分析它们的基本思想。表2 1 给出了这些算法所采用的基序表示方 式、打分函数和基本方法。 2 5 2 1 基于穷举思想的基序识别算法 基于穷举思想的基序识别算法，一般列举所有可能满足限制条件的z m p 厂为 候选基序，计算每个候选基序在序列集中出现的次数，在此基础上计算统计显著 性，然后输出具有最高显著性或者显著性超过某一阈值的作为识别出来的基序。 因为运行时间随着基序长度的增长成指数增加，基于穷举思想的方法适合于识别 较短的高度保守的基序，另一方面，又由于运行时间随输入序列长度的增长呈线 性增加，因而适合在大量数据中发现较短基序。 基于穷举思想的识别算法又可分为模式驱动算法和样本驱动算法两类。模式 驱动算法将由a ，c ，g ，t 组成的所有的，一m e ，作为候选基序，在输入序列集s 中找到 这些候选基序的用例，并用打分函数计算候选基序用例的统计特性，将分值较高 的候选基序作为最佳基序，特点是敏感性好，能保证得到最优解。样本驱动算法 基于免疫遗传算法的基序识别方法的研究 将序列集s 中出现的所有，珑p ，作为候选基序，然后使用打分函数计算统计特性， 特点是搜索效率高，当基序在序列集s 中没出现时，只能得到局部次优结果。 w o r d u p 【1 3 1 算法是比较早的穷举算法，其基本思想是从输入序列中找出具有显 著统计特性的，m p ，使用，玩觑e 来计算统计意义，采用了基于一级马尔科夫链 的分析方法，可以对一组已知在功能上有联系且没有进行过比对的序列进行分析， 算法在计算，m e ，出现频率时考虑了核苷酸之间的相互影响。 0 l i g o d y a d a n a l y s i s 【4 5 ，4 6 】算法通过计算每个，研p ，的出现次数并将它们与期 望值比较束发现统计意义大的基序，搜索过程中都利用背景序列的一些特征值。 两种算法都默认为基序的核心保守区域是由6 个碱基组成，因此，只适用于识别 长度为6 的基序。d y a d a n a l y s i s 可以识别带空位的基序，空位的长度在o 到1 6 之间，而o l i g o a n a l y s i s 不可以。两种算法最大的缺点是不允许基序有变异现象 的存在。 y m f 【1 4 】算法是专为识别酵母菌基序而设计的，算法输入中包含酵母菌基因上 游序列的补码序列构建的4 阶马尔科夫模型的转移矩阵，每个基序用例的期望出 现次数都由这个矩阵来估计，而每个基序的显著性由z d 愕来评分。算法不仅 可以查找包含字符n 的基序，而且能直接搜索由两个保守部分组成的基序。但当 待识别基序长度较大时，计算时间过长，因此只适合查找长度不大于8 的基序。 m o p a c 【4 7 】算法将正序列中出现但没有在负序列中出现的所有，一，z p 厂作为候选 基序，这样就过滤掉很多，l p 船，从而减少了进一步搜索的空间，再通过计算某 个候选基序与其他串之间的海明距离来过滤一些差异很大的，一肌e 坶，然后根据剩 下的，m p 坶的海明距离进行聚类操作，最后给出每类的基序模型做为最后的识别 结果。 2 5 2 2 基于启发式思想的基序识别算法 基于穷举思想的算法虽然保证识别全局最优解，但算法复杂度高，只适合识 别较短的高保守度的基序，为了识别更长更复杂的基序，许多算法利用启发式思 想，不要求找到全局最优解