（计算机应用技术专业论文）蚁群遗传算法在序列比对中的应用.pdf

摘要 摘要 生物信息学是以计算机为主要工具，对以指数增长的生物数据进行处理的- - f - j 交叉 学科。 序列比对是生物信息学的基本研究方法，通过序列比对可以推断基因的结构、功能 和进化关系。 蚁群算法是一种仿真算法，模拟了蚂蚁在觅食过程中寻找最短路径的方法来求解最 优解。 遗传算法足另一种仿真算法，它模拟了生物的遗传过程来寻求最优解。 蚁群遗传算法是一种混合算法，它通过遗传算法对蚁群算法的一组参数进行优化， 来达到取得全局最优解和加快收敛速度的目的。 本文通过对国内外序列比对算法的分析，将蚁群算法应用于序列比对上，设计了新 型的蚁群序列比对算法。但因蚁群算法一般仅获得局部最优解，如果将遗传算法应用于 蚁群序列比对算法上将克服这一现象，这就产生了蚁群遗传序列比对算法。蚁群遗传序 列比对算法能扩大求解空间，克服蚁群算法的局部性，求得全局最优解。实验表明蚁群 遗传序列比对算法可以显著提高序列比对的效果。 关键字：生物信息学序列比对蚁群算法遗传算法蚁群遗传序列比对算法 a b s t r a c t 一_ _ _ _ _ _ _ - _ - _ - _ _ - _ - - _ _ - _ _ _ _ _ _ - _ _ - - _ _ - _ - _ _ _ _ i _ - _ _ _ _ _ _ - _ _ _ _ _ - _ - _ - _ _ _ - _ _ - _ _ _ _ - _ _ _ _ _ _ _ - - _ - _ - _ - _ - - - _ 一 a b s t r a c t b i o i n f o r m a t i c si sa ni n t e r d i s c i p l i n a r yw h i c hu s e sc o m p u t e r sa sam a i nt o o lt od e a lw i t h e x p o n e n t i a lg r o w i n gb i o l o g i cd a t a s e q u e n c ea l i g n m e n t ( s a ) i sab a s i cr e s e a r c ha p p r o a c hi n b i o i n f o r m a t i c s ，a n dt h e s t r u c t u r e ，f u n c t i o n sa n de v o l u t i o n a lr e l a t i o no fg e n ec a l lb ec o n c l u d e db ys e q u e n c ea l i g n m e n t a n tc o l o n yo p t i m i z a t i o n ( a c o ) i sas i m u l a t i v ea l g o r i t h m ，t h r o u g hw h i c hab e t t e rr e s u l t c a nb ef o u n db yi m i t a t i n gt h ea n t st h a tf i n dt h es h o r t e s tp a t hd u r i n gh u n t i n gf o o d g e n e t i ca l g o r i t h m ( g a ) i sa n o t h e rs i m u l a t i v ea l g o r i t h mw h i c hi m i t a t e st h ep r o c e s so f b i o l o g yh e r e d i t yt og e t t h eb e s tr e s u l t a n tc o l o n yo p t i m i z a t i o ng e n e t i ca l g o r i t h m ( a c o g a ) i sam i x e da l g o r i t h m ，w h i c h g a i n st h eg l o b a lb e s tr e s u l ta n dq u i c k e n st h er a t eo fc o n v e r g e n c et h r o u g ho p t i m i z i n ga g r o u p o fp a r a m e t e r so f a c ov i ag a b a s i n go nt h ea n a l y s i so ft h ed o m e s t i ca n do v e r s e a ss e q u e n c ea l i g n m e n t s ，b ya p p l y i n g a c ot os a ，t h ep a p e rd e s i g n e dan e wa n tc o l o n yo p t i m i z a t i o ns e q u e n c ea l i g n m e n t ( a c o s a ) b u ta c o u s u a l l yo n l yg e t st h eb e s tr e s u l tl o c a l l y , a n db ya p p l y i n gg a t oa c o s a ，t h i s p h e n o m e n o nc a l lb eo v e r c o m e ，a n ds oa n tc o lo n yo p t i m i z a t i o ng e n e t i ca l g o r i t h ms e q u e n c e a l i g n m e n t ( a c o g a s a ) c o m e si n t ob e i n g a c o g a s ac a ne n l a r g e t h es e a r c hs p a c e ， o v e r c o m et h el o c a lr e s u l ta n dg e tt h eb e s tr e s u l t t h ee x p e r i m e n ti n d i c a t e sa c o g a s a c a n o b v i o u s l yi m p r o v et h ee f f e c to ft h es e q u e n c ea l i g n m e n t k e y w o r d s ：b i o i n l b r m a t i c s ，s e q u e n c ea l i g n m e n t ，a n tc o l o n yo p t i m i z a t i o n ，g e n e t i c a l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o ng e n e t i ca l g o r i t h ms e q u e n c ea l i g n m e n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 翔： 疆| j 坛 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名： 导师签名： 翠鱼艮 灶 勘d 留、 日 期 必查基z ： 么么受查q z = f2 第一章绪论 1 1 研究背景 第一章绪论 一方面，2 0 世纪生命科学迅速的发展起来了。生理学、细胞生物学、分子生物学等 学科的发展使我们从器官、组织、细胞及生物大分子等各个层次认识了生命的物质基础。 生物与其它物质有本质的区别，生物并非只是物质的简单堆积，生物体的生长发育是生 命信息控制之下的复杂而有序的过程。随着生命科学的发展，产生了大量的呈指数级增 长的关于生物的信息，如d n a 序列、氨基酸序列、蛋白质结构等。这么巨大的数据量单 靠生物学家们做实验来处理所花费的代价和时间是不可估量的，更何况依靠手工根本是 无法完成的。 另一方面，人类基因组计划( h g p ，h u m a ng e n o m ep r o j e c t ) 正式启动于1 9 9 0 年， 这是一个跨世纪、跨国界的最伟大的生命科学工程，经美、英、法、德、日、中6 国的 合作和努力，于2 0 0 0 年完成全部序列测序工作，标志着二十一世纪是生命科学的世纪。 随着分子生物科学的长足进展，把生命活动的物质基础追溯到核酸和蛋白质两大类生物 大分子的序列上，它们构成了生物数据的主要部分。关于这些生物大分子的结构、相互 作用和生物功能的研究，产生了大量的生物数据。为了更好地组织、挖掘、再利用这海 量的原始生物数据，以加速生命科学的进步和发展，计算机技术被越来越多地应用到生 物研究中，并发挥着至关重要的作用。从而一个崭新的领域一生物信息学 ( b i o i n f o r m a t i c s ) 迅速发展起来，它是应用计算机和信息技术搜集、储存、分析、整理 各种生物信息，并。，以管理和利用的一门交叉学科。生物信息学充分发挥计算机技术 和网络技术在生物学科各个领域的数据处理分析能力，将基因的结构、蛋白质功能以及 物种的进化在基因信息的基础上统一起来。 生物信息学便是在这样的背景下应运而生了。生物信息学以计算机、网络为工具， 采用数学和信息科学的理论、方法和技术去研究生物大分子，其研究重点主要落实在核 酸和蛋白质两个方面，包括它们的序列结构和功能。生物信息学以基因组d n a 序列信息 分析作为出发点，破译遗传语言，认识遗传信息的组织规律，辨别隐藏在d n a 序列巾的 基因，掌握基因调控信息，对蛋白质空间结构进行模拟和预测，依据蛋白质结构和功能 的关系进行药物分了设计。 序列比对是研究生物信息学的基本方法，序列比对的各种算法都是以生物信息学的 产生为背景而发展起来的。 江南人学硕仁学位论文 1 2 研究现状 经典的序列比对算法有：n e e d l e m a n - w u n s c h 算法【2 1 ，提出了用动态规划思想来实现 双序列比对的算法；s m i t h w a t e t m a n 算法1 3 i 是基于局部相似性比较的算法。f a s t a 和 b l a s t 是目前最为著名的两个搜索算法，它们都是基于局部相似性的算法。 最近几年，将优化算法应用于序列比对的研究逐渐多了起来。 m o l o g n i 和s h i n o d a 提出一种把遗传算法应用到双序列比对的方法，染色体由双序列 组成，首先随机产生一组染色体，然后对每一个染色体进行评估，根据打分矩阵求得个 体适应值，选择适应值最大的染色体进行复制，并利用交叉和变异算子产生下一代种群， 通过多代进化，收敛到最优比对结果。 c e d r i c ，e m m e t 和d e s m o n d 于1 9 9 7 年提出了一种应用于多序列比对的遗传算法，并实 现了基于该算法的软件包r a s a 5 1 。 蚁群算法是一种新型的模拟进化算法，它通过模拟蚁群在觅食过程中寻找最短路径 的方法来求解优化问题。用该算法求解序列比对问题是优化算法在该领域的一种尝试， 梁栋等人把蚁群算法应用到了生物信息学中的序列比对上【6 】。但是该算法存在局部最优 解的局限性。 1 3 研究意义和目标 1 3 1 序列比对研究的意义 序列比对( s e q u e n c ea 1i g n m e n t ) 是生物信息研究的基础和前提。序列比对不仅是数 掘库搜索、摹因比较和新基因发现的最常用和最经典的序列分析手段，而且序列比对的 结果作为二级生物数据，为蛋白质结构和功能预测、系统进化树的建立、基因病的治疗、 新药物设计 】等许多生物研究提供了宝贵的信息。序列比对是指通过一定算法对两个或 多个核睃或氨基酸字符序列进行对齐比较，逐列比较其字符的异同，判断它们之间的相 似程度和同源性，从而推测它们的结构、功能以及进化上的联系。 1 3 2 研究的目标 本文的目标是卣+ 先设计出一1 种新型的蚁群序列比对算法，但由于蚁群算法存在局部 最优解和收敛速度慢等缺陷，因此为了得到双序列比对的全局最优解，同时让算法快速 收敛，我们把遗传算法应用到蚁群序列比对算法上，对蚁群算法的一些参数进行组合优 2 第一章绪论 收敛，从而达到求解全局最优解和加快算法收敛速度的目的，即设计出蚁群遗传序列比 对算法。 1 4 论文结构 本文由6 章组成，各章的主要内容安排如下： 第一章是绪论，主要讲解了本文研究的国内外背景、研究的意义和目标； 第二章是生物信息学背景知识，主要讲解了生物信息学的一些名词、基本知识和常 用序列比对算法； 第三章是智能算法的原理和应用，主要包括蚁群算法、遗传算法和蚁群遗传算法； 第四章是蚁群序列比对算法的设计，主要讲解了蚁群序列比对算法的设计细节，同 时采用不同的打分函数或打分矩阵用蚁群序列比对算法对d n a 和氨基酸序列进行大量了 的实验。 第五章是蚁群遗传序列比对算法的设计，主要讲解了蚁群遗传序列比对算法的设计 细节，之后不仅采用不同的打分函数或打分矩阵用该算法对d n a 和氨基酸序列进行大量 的实验，而且也与其它的序列比对算法的结果进行了比较，结果表明我们的算法能获得 较优的结果。 第六章是对本文的一个总结和对未来的展望。 江南人学硕l ：学位论文 第二章生物信息学背景知识 2 1 生物信息学基本概念 2 1 1 生物信息学的主要研究内容 生物信息学最终是- - i - j 研究生物系统中信息现象的学科，它的主要研究内容包 括 8 - 9 ： 1 ) 大规模基因组测序中的信息分析，新基因的发现和鉴定。 2 ) 基因组相关信息的收集、储存、管理与提供。 3 ) 遗传密码的起源与生物进化分析。 4 ) 完整基因组的比较研究。 5 ) 大规模基因功能表达谱的分析。 6 ) 蛋白质分子空间结构预测、模拟与药物分子设计。 2 i 2 核酸和蛋白质 核酸【lo 】是遗传信息的携带者，核酸是由四种单体聚合成的一维高分子链，其中每个 单体又称为核二旨酸。核酸是携带遗传信息的有机大分子，遗传信息就编码在这些单体的 不同排列次序上。核酸根据单体类型的不同，可以分为脱氧核糖核酸( d e o x y r i b o n u c l e i + x a c i d ，d n a ) 和核糖核酸( r i b o n u c l e i xa c i d ，r n a ) 。脱氧核糖核酸是由腺嘌呤( a ) 、鸟嘌 呤( g ) 、胞嘧啶( c ) 、胸腺嘧啶( t ) 4 种脱氧核苷酸组成的多聚核苷酸链；核糖核酸是 由腺嘌呤( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 、尿嘧啶( u ) 4 种核苷酸组成的多聚核苷酸链。其 中，d n a 上核酸的特定序列决定了生物体结构和功能，并以其半保留复制机制，保证世 世代代准确地传递下去。 蛋白质【10 1 是一种由2 0 种氨基酸通过肽键连接而成的生物大分子。蛋白质结构和功能 都足由核酸根据三联体密码决定的，并在细胞内合成，它参与生物的一切生命活动。 因此，将一切物种核酸或蛋白质序列看作由4 个或2 0 个元素组成的字母表中选【 的 字母序列( 表2 1 ，表2 2 ) ，如： a t g g c c a a c t ) ， g s s k y p r e t t ) 分别表示一条核酸序列和 蛋白质序列。生物信息就是成千上万条以字符序列形式存储核酸或蛋白质序列，并以某 些特定格式存放在各类生物数据库中。 4 第二章生物信息学背景知识 表2 1 核苷酸代码 t a b 2 1n u c l e o t i d ea c i dc o d e 符号意义 a腺嘌呤 g 鸟嘌呤 c 胞嘧啶 t 胸腺嘧啶 表2 2 氨基酸代码 t l b 2 2a m i n oa c i dc o d e 符号意义符号意义 a 丙氨酸 n 天冬酰氨酸 c 半胱氨酸 p 脯氨酸 d 天冬氨酸 q 谷氨酰胺 e谷氨酸 r 精氨酸 f 苯丙氨酸 s 丝氨酸 g甘氨酸t苏氨酸 h 组氨酸 v 缬氨酸 i 异亮氨酸 w 色氨酸 k赖甘氨酸 y 酪氨酸 l 亮氨酸 x 任意氨酸 m 甲硫氨酸 2 1 3 遗传信息的传递与表达 科学家们发现在生物细胞核中存在大量的酸性大分子物质：脱氧核糖核酸( d n a ) ， 核糖核酸( r n a ) 。这两种大分子组成上十分相似，它们都足由“磷酸”，“脱氧核糖”或 “核糖”，以及“有机碱”组成的。此外，细胞核中还存在大量的蛋白质。这三种生物 大分子中只有d n a 的含量十分稳定，是遗传的生物基础f 1 1 1 。 d n a 是一种高分子有机化合物，它的基本单位是脱氧核苷酸。脱氧核苷酸由三部分 组成：磷酸、脱氧核糖和含氮碱基。d n a 分子是由很多不同的脱氧核苷酸组成的多脱氧 核苷酸链。图2 - 1 显示了d n a 的双螺旋结构。脱氧核糖与磷酸相问排列在外侧，形成两 条主链，构成d n a 的基本骨架。两条主链之间的横档是碱基对，排列在内侧。相对应的 两个碱基通过氢连接形成碱基对，把两条主链连接起来。碱基配对有一定的规律：a 与 t 配对，c 与g 配对。 5 南人学颂j ，学位论立 图2 - 1d n a 分子的双螺旋结构 f l g2 - it w jnh e l ixs tr u c t u y co fd mm o l e l a d n a 分子可以在解螺旋酶的作用下使双链分离再将每条单链作为一个模板，在聚 合酶的作用fr 按碱基配对的规律台成两条新的双螺旋结构，就完成了d n a 分子的复制。 d n a 取链r | 1 的条可以作为模板，按照碱基互补的原则合成r n a ，这个过程称为转 录。转录的过程如图2 2 所示： 囤2 - 2d n a 转录成r n a f i g2 2 d n a t m n s f b r i or n a r n a 的碱罄中用“尿嘧啶0 ”错换了d n a 中的“胸腺嘧啶t ”，变成了a 、u 、c 和g 。 d n a 存钏抱核当中绎过转录过程合成了r n a 链，称为信使r n a ( m r n a ) 。在细胞质当巾， 以m r n a 为模板，就，j 以台成县硝 定氨基酸顺序的蚩白质，这个过程称为翻译。m r k a 1 ，饵三个拥邻的碱基( 称为衍码子j 决定了种氨基酸。遗传信息通过如罔23 显不的过 程就完成了传递和表达。 图2 - 3 遗传信皂的传递和表达 f i g23 l r a n f e ra n de x p r c s s i o no f g e n e t i ci n f o 兀【i a t i o n | ) ；j 此归根结底，决定生物性状的遗传信息足山d n a 的脱氧核苷酸的排列顺序确定的。 d n a 柏断个壁小功能：( 1 ) 复制：在生物的传宗接代中传递遗传信息：( 2 ) 表达：在后代 个体发何巾将遗传信息表达为与亲代相似的性状。 214 生物信息学的中心法则 9 5 8 年，阡。- i sc r i c k 首先提j e 了分了生物学的中心法则m 】，它很好地鼬明了核 第h 二苹生物f 膏思学背景知识 苷酸和蛋白质这两大类生物大分子之间的信息传递关系。简单地说，d n a 作为遗传信息 的携带者，它在一定条件下i 叮以准确地自我复制。为此要先把信息“转录”到单股的r n a 链上( 此类r n a 称为m r n a ) 。细胞液中有大量核糖体，它们把m r n a 上的信息翻译成蛋白质。 新生的蛋白质要折叠形成特定的三维形状，才能有生物活性，在生命过程中发挥功能。 因此，从d n a 到r n a 然后再到蛋白质的信息表达过程是一个单向信息流，这个单向信息流 同d n a 之问的信息传递一起构成了分子生物学的中心法则。但是后来人们发现有一些病 毒里面存在反向信息流，即r n a 也可以转录成d n a 。这类病毒的遗传信息存储在r n a 中， 遗传信息的传递需要首先从r n a 反转录为d n a ，然后才能进行d n a 复制。中心法则如图2 4 所示。在翻译过程巾，每3 个核苷酸编码( 称为一个密码子) 被翻译成蛋白质中一个特定 的氨基酸。 复制 图2 - 4 分子生物学的中心法则 f i g 2 4c e n t e rp r i n c i p l eo f m o l e c u l eb i o l o g y 2 2 序列比对的基本原理 为了更好地介绍序列比对的基本原理，首先简要地讨论序列比对算法中所涉及的一 些主要概念，然后以双序列比对为例来说明序列比对的基本原理。 2 2 1 空位罚分 基因在进化过程中往往会产生残基的插入或缺失。有时是1 个或者2 个残基的插入或 缺失，有时则是大片段的插入或缺失。这样，在进行序列比对时，为了更好地反映序列 的相似性，也就必须考虑在序列比对时插入空位，并进仃f - - 训i i l l 分。也就足说，序列比对过 程中引入空位时应该罚分，罚分大小可由用户在运行程序时设定，以控制空位插入的合 理性以及达到总体上更好的比对效果n3 1 。空位罚分时涉及到两个参数，一个是空位开放 罚分，一个是空位延伸罚分。顾名思义，前者为新空位产生时进行的罚分，而后者则为 空位延伸时进行的罚分。也就足说，每当第一次插入空位时，要进行一定的空位丌放罚 分，而连续插入空位时，通常按比例给以稍小的空位延伸罚分。因此，计算一组连续空 位罚分公式如式2 1 所示： 吸= 口+ b k ( 2 1 ) 其中，a 和b 分别表示空位开放罚分和窄位延伸罚分，k 是连续空位的总个数。具体 7 江南人学硕士学位论义 使用时，常数a 和b 的值与所比较的是核酸序列还是蛋白质序列有关，而且还要与下面讲 到的替换矩阵的选择相适应。 2 2 2 替换矩阵 由于序列比对不仅需要考虑子序列之间的匹配，而且需要对整个序列进行比较。因 此，实际操作中，获得序列之问理想的序列比对并不是一件容易的事。所以，通常用替 换矩阵( 又叫计分矩阵) 赋予序列比对结果以分值，用最高的分数来解释具有显著性生物 学意义的比对结果。替换矩阵可以分为单一替换矩阵和相似性替换矩阵。单一替换矩阵 就是只考虑两个序列之间完全相同的匹配残基数目，可以把它理解为l 和0 的矩阵，即： 相同残基的分数值为1 ，不同残基的分数值为0 。表2 3 ( a ) 中显示的足d n a 序列的单一 替换矩阵。显然，这种单一替换矩阵具有很大的局限性。 表2 3d n a 的单一替换矩阵和相似性替换矩阵 t a b 2 3s i n g l er e p l a c em a t r i xa n ds i m i l a rm a t r i xo fd n a 矩阵 类型 ( a ) 单一替换矩阵 ( b ) 相似性替换矩阵 acgtacgt 替换 a1 o0 0 a0 90 1一o 1o 1 矩阵 c01o0 c0 10 90 1 0 1 go0l0 g0 1- 0 10 90 1 t0o01 to 10 10 10 9 相似性替换矩阵是基于远距离进化过程中观察到的残基替换率，用不同的分值表征 不同残基之间相似性程度。相似性替换矩阵改进了单一替换矩阵的表征性能，能揭示那 些潜在的具有生物学意义的最佳匹配。恰当选择相似性替换矩阵，可以提高序列比对的 敏感度，特别是两个序列之间相同残基较少的情况下。表2 3 ( b ) 中显示的是d n a 序列的 相似性替换矩阵。常用的蛋白质替换矩阵有突变数据矩阵【1 4 1 卯。大多数比对程序均对 特定的替换矩阵设定了空位罚分的缺省值，如果用户希望使用不同的替换矩阵，则原来 的空位分值设定不一定合适。如何设定罚分并无明确的理论可循，但大的空位开放罚分 伴随很小的空位延伸罚分被普遍证实是最佳的设定思路1 1 6 1 。 2 2 3 双序列比对基本原理 下面以一个双序列比对为例简单说明序列比对的原理。图2 - 5 所示足对两个蛋白质 序列片段进行比对的一般方法，其基本思想是将两个序列上下排列，若上下对应的残基 第二荦生物信息学背景知识 相同，用，i ：表示。可以通过插入空位使它们具有最好的匹配，即两个序列所对应的相同 残基最多。下一步则可以计算相同残基个数，并用计分给出定量指标l i t - i s ! 。图2 - 5 显示 了两个蛋白质序列片段 a g d v l i y c g v f f q ) 和 a g d l i y f f q ) 用单一的置换矩阵计分，这两个 序列在未经比对之前总分为3 。通过比对运算，在适当的位茕插入若干个空位之后，使 得比对后序列的总分变为9 ，从而得到最佳比对。 插入空位前序列 序列1a g d v l i y c g v f f q 序列2a g d l i y f f q 车木木 插入空位后 序列1a g d v l i y c g v f f q 序列2a g n l i u f q 木木丰木：l c 木幸奉宰 图2 - 5 利用插入空位的方法获得最佳序列比对 f i g 2 5 g e tt h eb e s ts e q u e n c e a l i g n m e n tw i t ht h e m e t h o db yi n s t e r i n gb l a n k 2 3 序列比对问题的描述以及序列比对的分类和目的 2 3 1 序列比对问题的描述 生物信息学1 1 9 中对序列进行比对时要经常用到字母表、序列、得分函数、得分、 替代、插入、删除和最优比对等概念，以下作一简要解释。 对于一个序列s ，isl 是序列s 的长度，s 表示序列s 中的第i 个字符。，s ，指明序列s 中第i 和j 个字符之间的序列是s 的子序列。s 中的字符由某个有限字符集合q 确定，女h d n a 由4 种核糖核酸a ，t ，c ，g 确定；氨基酸由2 0 种字母确定等。基因序列在突变中的变化 包括替代、插入和删除，我们用“一”来表示插入和删除所产生的空位。对于x ，y q u 一) ， 定义f ( x ，y ) 为计分函数，表示x ，y 比较时的得分，以下是最简单的一种： i2x = y q f ( x ，y ) = 1x y q ( 2 2 ) 【- 1x = 或y = 一 s 和t 的一个序列比对a 用序列中字符的一一对应表示，其中is ht 。l ，is 。l 和 9 江南大学硕t 学位论文 ir l 去掉空格就是s 和t 。a 的得分为： i ，l s c o r e ( a ) = 厂( ，z ) ( 2 3 ) f = l 取得最大值的比对就是最优比对。 2 3 2 序列比对的分类 根据比对序列数目的多少可以分为双序列比对和多序列比对。双序列比对实质是寻 找最佳匹配路径；多序列比对的实质是寻找多个序列之间的关联性。双序列比对是序列 分析常用方法之一，是多序列比对和数据库搜索的基础。多序列比对在识别一组相关序 列中重要生物学意义的序列模型方而具有相当重要的作用。对双序列比对算法的研究比 较成熟，基本上可以分成两类，一类是基于序列的全局相似性的全局比对算法，考察两 个序列之 j j 的整体相似性，最佳比对中包括了全部的最短匹配序列；而另一类是基于序 列的局部相似j 性，着眼于寻找某些特殊片段，比较这些片段之间的相似性，称为局部 比对算法。但对多序列比对算法的研究还在进行中，比较流行的方法有动态规划法、聚 类法、基于退火算法的方法和基于遗传算法的方法等【1 4 2 0 。2 3 1 ( 1 ) 双序列比对和多序列比对 双序列比对是指两个d n a 或蛋白质序列进行的比对。多序列比对足指三个或三个以 上自9 d x a 或蛋白质序列进行的比对。 进行同源性分析。是多序列比对的和数掘库搜索的基础r 引。动态规划算法是最为 经典的双序列比对算法。 多序列比对可以用来区分一组序列之间的差异，或者描述一组序列之间的相似性关 系，以便了解一个基因家族的共同特征，以及定量估计序列间的关系，由此推断它们在 进化中的亲缘关系。多序列比对的计算量非常大，如果采用n e e d l m a n - w u n s c h 算法，空 间和时间复杂度都很高，巨大的计算量使得该算法变得不切实际。传统的动态规划算法 在三个以上的序列比对当中就很难实现了。一般采用渐进式算法或迭代算法。 ( 2 ) 全局比对和局部比对 全局比对是对整个序列进行的比对，反映的是序列在全长范围内的相似程度。如果 相似度高，说明序列之间可能具有同源性。局部比对是对序列的子序列进行的比对，反 映的是序列在局部范围内某些片断的相似程度1 2 q ( 3 ) 精确比对和近似比对 序列比对算法从比对结果来说可以分为精确比对和近似比对。精确比对算法每次都 可以找到序列之问的最优比对。而近似比对算法则不一定每次都能找到最优比对，可能 l o 第二章生物信息学背景知识 只找到了近似最优的比对。 一般都希望得到精确的比对结果，但是这样做可能耗费大量时间，对机器性能要求 很高，难以实现。因些人们把目光转向求解近似比对的算法上。 很多优化算法都是近似比对算法，它们不一定每次都能找到最优解。比如遗传算法， 模拟退火算法等。但是这些算法收敛速度快，效率较高。目前在序列比对算法的研究当 中，优化算法受到越来越多的关注，比如，遗传算法在解决多序列比对问题中显示了很 好的性能。 2 4 序列比对的常用算法 2 4 1 用动态规化算法进行序列比对 动态规划算法【2 5 】应用到序列比对上是非常合适的。比对的结果往往不止一种。长 度为m 和n 的序列s 1 1 1 1 和t 1 n 在全长范围内的比对结果，包含了s 和t 的前缀子 序列s 1 m 和t 1 n ( 1 i m ，l j n ) 的比对结果，这是一个递归的关系。因 此可以先求解子序列的最优值，根据递归关系求解更大规模的子问题，直到求得序列 s 1 m 和t 1 n 的最优值。然后可以根据各阶段最优值的信息，采用回溯技术， 构造出最优序列比对的结构。假设有长度为m 和n 的序列s 和t ，其中f s 卜m ，j t l = n ，则 s 1 m 和t 1 n 表示s 和t 的全长序列；s 1 i 和t 1 j ( 1 i m ，1 j n ) 表示s 和t 的由前i 个和前j 个字符组成的前缀子序列。 我们构建一个大小为( m + 1 ) x ( n + 1 ) 的矩阵( 称为得分矩阵) 。矩阵中的元素m i ，j ( 0 i m ，0 j n ) 记录了前缀子序列s 1 i 和t 1 j 的最优比对得分。则根据递归 关系，m m ，n 就是s 和t 的最优比对得分。矩阵的第一行和第一列表示一个子序列同空 字符序列的比对分值，由于只能在空序列中加入空位，因此我们设定计算矩阵元素的初 始条件： m o ，0 】= 0 m i ，o = ：。( m 】，一) ( 1 i 朋，1 ，门) ( 2 4 ) m o ，j l = z ：。厂( 一，研足 ) 分析非空子序y g s 1 i 和t 1 。j 的最优比对得分m i ，j ，只有三种可能的来 源：( 1 ) s i 与一个空位的匹配得分，加上子序列s 1 i 一1 和t 1 j 的最优比对得 分：( 2 ) t i 与一个空位的匹配得分，加上子序y j s 1 i 和t 1 j 1 的最优比对得 分；( 3 ) s i l 和t i 的匹配得分，加上子序列s 1 i 一1 和t 1 j 一1 的最优比对得 分。如图2 6 所示： 江南大学硕i 二学位论文 虹j l j 一l 】 ，一l 】 l l q s l i 】，- ) j二 聊一1 , j 一1 丛二型1 2 - 聊，_ ，】 图2 - 6 矩阵元素m 【i ，j 】的得分来源 f i g 2 - 6t h es c o r er e s o u r c eo ft h em a t r i xl e m e n t ：m i , j 因此得到下面的递归关系式： f m i - 1 ，j - 1 + 厂( s 【刀，丁【，】) m i ，j 】= m a x m i - 1 ，j 】+ 厂( s 【j 】，一) ( 1 i m ，1 歹”) ( 2 5 ) i m i ，歹- 1 】+ ( 一，r 】) 根据动态规划的求解步骤，得到最优比对得分后，寻优过程就结束了。我们可以采 用回溯技术来构造最优比对。由于元素分值来自于哪个元素容易判断，以这一点为起点， 采用下面的算法就可以找到相应的最优比对了。 t r a c e b a c k ( m ，s ，t ) i = m ，j = n ： w h i l e ( i 0 j o ) i f ( m i ，j = = m i l ，j 一1 ) + u ( s i ，t j ) ) i 一一：j 一一：) e l s ei f ( m i ，j = = m i 1 ，j ) + o ( s i ，一) ) i 一一：i n s e r t ( “一“，t ，j ) e l s ei f ( m i ，j = = m i ，j 一1 3 ) + o ( 一，t j ) ) j 一一：i n s e r t ( “一”，s ，i ) ) ) ) 回溯算法从矩阵右下角的元素开始，直到j ，j 的值为o 时，也就是到达矩阵左上角 的元素时结束，得到的两条序列就是最优比对。 2 4 2n e e d l e m a n - w u n s c h 算法和s m it h - w a t e r m a n 算法 1 9 7 0 年，n e e d l e m a n 和w u n s c h 提出了比较序列全长范围内相似度的序列比对算法， 1 2 第二章生物信息学背景知识 为全局比对提供了可以实际操作的算法【2 】双序列比对中的精确比对算法大多是基于动 态规划算法并在其基础上进行改进的。该算法就是基于动态规划思想的。他们的方法和 前面介绍的动态规划算法是基本一致的。 1 9 8 1 年，s m i t h 和w a t e r m a n 提出了一种寻找并比较序列中具有局部相似性的区域的 算法1 3 l 。它也是一种基于矩阵的算法，而且也运用了回溯法建立允许空位插入的比对。 多年来，s m i t h w a t e r m a n 算法一直是序列局部比对算法基础，许多算法都是基于这一算 法开发和改进的。 s m i t h w a t e r m a n 算法相对于n e e d l e m a n w u n s c h 算法有一定的变化，首先是第0 行和 第0 列的元素分值都赋为0 ，可以把这些单元理解为序列片段的起始端，其长度为0 。在 递归关系中m i ，j 的值是式2 5 中三个值和0 之问的最大值。如果0 足最大值，表示局部 相似片段在这一点不再延伸，即片段的末端。 初始条件：麓f 三翌三：c 。耋t 耋m ，。三j 三n ， c 2 6 ， im i i l ，一1 】+ ( s 【f ，形】) 递归关系：m i ，j 】- = m a x a 丌f 一1 ，j 】+ ( s j 】，一)( 0 i m , o j n ) ( 2 7 ) l m i ，歹一l 】+ ( _ ，n 】) 序列的最优匹配片段从矩阵中最高分值元素丌始回溯来获取，次优片段从次高分值 元素回溯来获取。 2 5 本章小结 本章主要介绍了生物信息学的一些基本概念、背景知识、序列比对的原理、序列比 对的分类以及常用的序列比对方法。 江南人学硕士学位论文 第三章蚁群算法、遗传算法和蚁群遗传算法的原理和应用 3 1 蚁群算法原理与应用 3 1 1 蚁群算法的简单描述 在蚁群算法中，一只蚂蚁在行动中留下一些信息激素能被同一蚁群中后来的蚂蚁感 受到，并作为一种信号影响到后者的行动，而后到者留下的信息激素会对原有的信息激 素进行加强，并如此循环下去。这样经过的蚂蚁越多的路径被后到蚂蚁选中的可能性就 越大。由于在一定的时间内越短的路径会被越多的蚂蚁走过，因而积累的信息激素也就 越多，在下一个时间内被其它蚂蚁选中的可能性也就越大。这个过程会一直持续到几乎 所有的蚂蚁都走最短的那一条路径为止 2 6 1 。这是对蚁群算法的一个简单描述。 3 1 2 蚁群算法的基本原理 蚁群算法( 2 7 - 2 9 1 是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的 模拟进化算法，属于随机搜索算法。m d o r i g o 等人充分利用了蚁群搜索食物的过程与旅 行商问题( t s p ) 之间的相似性，通过人工模拟蚁群搜索食物的行为来求解t s p 问题。为 区别于真实蚁群，称算法中的蚂蚁为“人工蚂蚁”。 ， 像蚂蚁这类群居动物，虽然个体的行为极其简单，但由这些简单的个体所组成的蚁 群却表现出极其复杂的行为特征，能够完成复杂的任务；不仅如此，蚂蚁还能够适应环境 的变化，如在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚁 群是如何完成这些复杂任务的呢? 人们经过大量研究发现，蚂蚁个体之间是通过一种称 之为外激素( p h e r o m o n e ) 的物质进行信息传递，从而能相互协作，完成复杂的任务。蚁群 之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁 在运动过程中，能够在它所经过的路径上留下该种物质，而且能够感知这种物质的存在 及其强度，并以此指导自己的运动方向。蚂蚁倾向于向该物质强度高的方向移动。因此， 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂 蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达 到搜索食物的目的。 3 1 3 蚁群算法的模型 基本的蚁群算法是和旅仃a - - - 阃i j z _ 问题( t s p ) 的求解结合在一起的 2 7 , 3 0 l ，t s p 问题的数 学描述是：给定n 个城市的集合c = c l ，c z ，巳) ，设是城市q 和城市c 之 1 4 第三帝蚁群算法、遗传算法和蚁群遗传算法的原理和心用 问的距离，寻找一条经过所有城市( 每个城市只能经过一次) 的最短路径，使l = 主4 n 。 取最小值。 现给定一个有n 个城市的t s p 问题，m 为总蚂蚁数，以此建立蚁群算法的模型：设 f 。( ，) 为路径i j 在时刻t 上的信息素浓度。初始时刻( t = 0 ) ，各条路径上信息量相等， r 。( o ) = c ( c 为常数) ，蚂蚁k ( k = 1 ，2 ，m ) 在行走过程中，根据各条路径上的信息量 决定下一条路径的选择，在t 时刻，蚂蚁k 由城市i 转移到城市j 的概率为： 咖) ： 母砒w 畋 ( 3 ，) 【0 ，o t h e r s 略= 瓦一x ，) 2 + ，一y j ) 2 ( 3 2 ) 在这个公式中：叼，为能见度，r 口21 d 口，在t s p 问题中吃表示城市i 到城市j 的 距离，如式3 2 ；q 和b 为控制信息素和能见度之间相对重要性的参数；集合a l l o w e d , 是 指蚂蚁k 尚未走过的城市集合，这个集合随着进化过程作动态调整。经过n 个时刻，所 有蚂蚁都完成了一次周游。此时，计算每一只蚂蚁所走过的路径厶( i = l ，2 ，m ) ，并存 储蚁群所找到的最短路径k m ，k 。由式3 3 求得。 l 。，。= m in l ，) ( i = 】，2 ，m ) ( 3 3 ) t o ( f + 以) 2p f f o ) + f 口 ( 3 4 ) r 扩2 a r ： ( 3 5 ) 嵋。2 尝只蚂蚁经过路鳓 6 ， 在蚂蚁完成一次循环以后，各路径上的信息量按式3 4 进行调整。p 表示残留信息 的持久程度，此处py , j0 - 一1 之i u j 的常数，1 一p 则表示挥发因子，表示信息的挥发程度， 信息量增量按式3 5 求得。r ：表示蚂蚁k 在本次循环中留在路径i j 上的信息量；q 足一个常量，表示一只蚂蚁在所经路径卜释放的信息素的量；厶表示第k 只蚂蚁在本轮 中经过的路径的长度，可由式3 6 求得z ：。 江雨大学坝l ：学位论义 该蚁群算法计算模型是m d o r i g o 提出的三种信息素增量计算模型的其中一种，称 为a n t - c y c l e 算法，它利用的是整体信息，另两种模式是a n t q u a n t i t y 算法和 。田t - d e n s i t y 算法，它利用的是局部信息。对于求解t s p 问题，m d o r i g o 认为 a n t - c y c l e 算法的求解效果最好。 3 i 4 蚁群算法的设计步骤 假设用所谓的a n t c y c l e 算法模型定义蚁群算法的处理过程，则蚂蚁被随机的放到 不同的城市，城市与城市之间的路径上的