（计算机应用技术专业论文）借助并行遗传算法对est序列拼接问题的研究.pdf

上海大学硕士学位论文 摘要 近年来，高性能计算机和大型并行计算技术进入了高速发展阶段，并己投 入了各个领域的实际使用。一些集群式超级计算机( c l u s t e r i n gc o m p u t e r ) 以高 性价比优势已成为国际上高性能计算机重要发展方向，并被广泛使用。在对生 物信息学的数据研究过程中，一个问题的计算通常要花上数小时甚至几天时间。 为了加快研究步伐，集群式计算机是一个理想的选择。 利用e s t ( e x p r e s s e ds e q u e n c et a g s ) 序列数据发现新基因，是当前国际 上基因组研究的热点。但程序设计十分复杂，计算量巨大。遗传算法是一种能 在复杂而庞大的搜索空间中利用问题的固有知识来缩小搜索范围，避免组合爆 炸，从而得到最优解或准最优解的通用搜索算法。在本文的研究中结合核酸序 列的特征，针对e s t 序列拼接的组合优化问题，充分利用近期蓬勃发展的高性 能集群式计算机系统，提出一种高效的并行遗传算法，并在我校的集群式高性 能计算机系统自强2 0 0 0 上实现。这个算法克服了现有工具软件的弱点，其测试 结果得到了生物学专家们的认可。 关键词：生物信息学；e s t 序列；新基因发现；并行遗传算法 上海大学硕士学位论文 a b s t r a c t r e c e n t l y ，h i g h p e r f o r m a n c ea n dm a s s i v e l yp a r a l l e lc o m p u t i n g t e c h n o l o g yc o m e si n t oah i g h s p e e dd e v e l o p i n gp h a s ea n di su s e di na l l k i n d so ff i e l d s s o m eh i g h p e r f o r m a n c ec o m p u t e rs y s t e m s ( c l u s t e r i n g c o m p u t e r ) a p p e a r t h e yb e c o m et h em a i n l yd e v e l o p i n gd i r e c t i o na n da re w i d e l yu s e df o rt h e i rh i g hp e r f o r m a n c e c o s t r a t e t os o l v ea b i o i n f o r m a t i c sp r o b l e m ，i tu s u a l i fc o s t ss e v e r a lh o u r so rd a y s t h e s e h i g h p e r f o r m a n c ec l u s t e r i n gc o m p u t e r sa r ec o n s i d e r e dt ob eag o o dc h o i c e t os p e e du pt h er e s e a r c h t od i s c o v e rg e n ef r o me s ts e q u e n c ei sap r i m a r i l yc o n c e n t r a t e dw o r k o ft h eg e n o m er e s e a r c ha l lo v e rt h ew o r l d h o w e v e r ，i ta l w a y ss u f f e r ss o m e d i f f i c a l t i e ss u c ha sc o m p l e xa l g o r i t h md e s i g na n de x t r e m e l ym a s so f c o m p u t a t i o n t h eg e n e t i ca l g o r i t h m ( g a ) i sak i n do fg e n e r a ls e a r c h a l g o r i t h mt h a tf i n d st h em o s to p t i m a ls o l u t i o no rs u b o p t i m i z e ds o l u t i o n w i t h i nc o m p l e x 、i m m e n s es e a r c hs p a c e ，a n da v o i d si n f o r m a t i o ne x p l o s i o n b yu s i n gi n t e r n a lc h a r a c t e r i s t i c so ft h ep r o b l e m t h i sp a p e rp r o p o s e sa s p e c i a l l yi m p r o v e dg e n e t i ca l g o r i t h mt h a tcanb ea p p l i e dt oj u n c t u r eo f e s ts e q u e n c e ，w eo f f e r sa ne f f e c t i v ep a r a l l e l i z e dv e r s i o nw h i c hi s i m p l e m e n t e do nc l u s t e r i n gc o m p u t e r sz i q i a n g2 0 0 0 ，a sw e l l t h i s a l g o r i t h mo v e r c o m e st h es h o r t c o m i n g so ft h ep r e s e n tt o o l s ，a n dt h eo u t c o m e g e t se ：k n o w l e d g ef r o mt h es e n i o rb i o l o g i s t s k e y w o r d s ：b i o i n f o r m a t i c s ；e s ts e q u e n c e ；g e n ed i s c o v e r y ：p a r a l l e l g e n e t i ca 1 9 0 r it h m 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工 作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期 上海大学硕士学位论文 绪论 科学研究进入微观世界后，往往会展现一个前所未有的局面。在这里，我 们能真实的贴近物质和生命的本原。爱因斯坦相对论的创建和量子力学的研究， 将人们对物质世界的认识提升到了一个新的高度。同样，对人类自身的研究也 进入了微观领域。自文明丌创以来一直困扰人类的两大问题：我们从哪罩来? 要往何处去? 在我们这一代人手中有了崭新的解答方案。 生命科学的研究核心就是对基因的研究。生命体表现出来的一切性状都能 归结到基因的控制。随着各国科学家的不懈努力和积累，到1 9 9 9 年底，已有 2 5 个模式生物( 一些有利于进行研究的生物) 完整基因组被测试完成，还有另 外7 0 余个微生物的基因组丁f 在测序当中。2 0 0 1 年3 月，在n a t u r e 和s c i e n c e 杂志上同时发表了由国际人类基因组协作组和c e l e r a 公司分别完成的人类基 因组序列及其初步的分析。已被测序的人类基因组含有约2 9 亿碱基，其物理图 谱覆盖率为9 6 ，序列覆盖率为9 4 。随着世界各地生物学家们不断地提交实验 成果，产生了一个庞大复杂的生物数据库，并且数据量以每1 4 个月翻一翻的速 度增长。在取得了这样的巨大成就后，一个新的问题摆在我们面前：如何解读 这些数据，从中提取出有用的信息? 生物学研究的新范式在于：所有的“基因” 先从理论上被知晓( 用电子方式从数据库中读取) ，然后科学家再转向实验室里 去检验该假设( w 6 i l b e r t1 9 9 ln a t u r e ) i “。 于是生物信息学一一这门新兴的综合性学科便悄然兴起，并蓬勃发展起 来。生物信息学是一门交叉学科，它所研究的材料是生物学的数据，它进行研 究所采用的方法是从各种计算技术衍生出来的。而生物学数据的复杂性和海量 性决定了必然要由计算机辅助来解读其中的信息。如今大型计算机的数据处理 能力已经发展到每秒数干亿乃至数万亿次计算的水平。有了这技术支持条件， 连同计算方法的创新和发展，基因组研究和其他生物学研究所产生的海量数据， 才能够得到有效地管理和处理，生物信息学才得以形成和发展。如今，充分利 用现有的资源，提出高效、精确的算法来处理庞杂的生物学数据成了一项重要 的研究课题。 上海大学硕士学位论文 高性能计算技术已经广泛应用于生物科学、空间科学、天文学、人工智能、 气象学和图像处理等各个研究领域。为了在生物信息学领域能够更好的运用现 有资源，发挥其特长，就要针对各种具体的问题对算法进行优化，如此才能在 将之移植到高性能并行机时充分利用到“高性能”、“高效率”。 根据生物学数据的不同和对其处理方式的不同，生物信息学包括的研究内 容与方式也是多种多样的。本文从算法着手，针对生物学数据中的一个重要类 型e s t 序列的拼接问题，提出一种优化的并行遗传算法。并在我校的集群式高 性能计算机系统自强2 0 0 0 上展开研究和实现。 上海大学硕士学位论文 第1 章生物信息学概论 1 1 简介 人类基因组计划( h u m a ng e n o m ep r o j e c t ，h g p ) 是美国科学家在1 9 8 5 年 率先提的，其目的在于阐明人类基因组d n a ( 脱氧核糖核酸) 核苷酸序列， 破译人类全部遗传信息【lj 。h ( ；p 于1 9 9 0 年正式启动，随着h g p 产生的数据爆炸， 一门新兴学科一一生物信息学应运而生。生物信息学是以计算机为主要工具， 丌发各种软件，对h 益增长的d n a 和蛋白质序列和结构等相关信息进行收集、 储存、发行、提取、加工、分析和研究，同时建立理论模型，指导实验研究。 它由数据库、计算机网络和应用软件三大部分构成，在基因组计划中发挥不可 替代的作崩。 美国人类基因组计划中给基因组信息学的定义是：它是一个学科领域，主 要工作是对基囚组信息的获取、处理、存储、分配、分析和解释。该定义包含 两方而的内容：一方面是发展强大有效的信息分析工具，构建适合于基冈组研 究的数据库，崩j ：搜索、管理、使用人类基因组和模式生物基凶组的巨量信息； 另一方面是配合实验研究，确定约3 0 亿个碱基刑的人类基因组完整核苷酸顺 序，找出人类全部约1 0 万个基因在染色体上的位置以及包括基因在内的各种 i ) s a 片段的功能，即”读懂”人类基冈。 如此海量且又复杂的生物学数据，对计算机科学和信息技术无疑是一种压 力和挑战。值得庆幸的是，人类基因组计划一开始就与信息高速公路和数据库 技术形成了同步发展。在现有的形势下，世界各国政府和民间都不遗余力的加 大对生物信息学的研究力度，把巨大的人力物力投入进来，培养具有跨学科能 力的人才，建立大规模的生物信息学服务系统，以求彻底解读所有的遗传信息。 如今，国际上的三大生物信息中心即美国的国家生物技术信息中心 ( n c b i ) 、欧洲生物信息学研究所( e b i ) 和日本d n a 数据库( d d b j ) 已经建立 和维护了源自数百种生物d n a 序列的大型数据库。大量的数据被产生并管理起 来，包括核酸序列库、蛋白质序列库、分子建模数据库等级和二级数据库。 同时，一大批管理和分析生物数据的软件被开发出来，比如由n c b i 开发和维护 的e n tr e z 分了检索系统、b l a s t 、s m i t h w a t e r m a n 、c l u s t a l w 算法等，作为信 上海大学硕士学位论文 息检索、序列比划、分子建模利预测的工具。基因组学的研究从结构基因组学 过渡到功能基因组学，即从“是什么”过渡到“为什么”的研究1 。 生物信息学的发展，不仅导致生物学、物理学、数学、计算机科学等多种 科学文化的融合和相互促进，也造就了一批新的从事交叉学科研究的科学工作 者。科学家们普遍相信本世纪初的若干年是人类基因组研究取得辉煌成果的时 代，也是它创造巨大的经济效益和社会效益的时代。 1 2 生物信息学研究的意义 生物信息学的研究结果不仅具有重要的理论价值，也可直接应用到工农业 生产和医疗实践当中去。因此，生物信息学相关的分析与应用算法、软件和数 据库，都具有重要的经济价值，最终都会形成商品，提供经济和社会效益p j 。 很多疾病与基因突变或基因多态有关，有人估计与癌症相关的原癌基因约 有i 0 0 0 个，抑癌基因约有i 0 0 个。约有6 0 0 0 种以上的人类疾患与各种人类基 因的变化相关联。更多的疾病是环境( 包括致病微生物) 与人类基因( 基因产 物) 相互作用的结果。随着人类基因组计划的深入，当我们解读了人类全部基 因特征以后，人们就可以有效地判定各种疾患的分子机制，进而发展合适的诊 断和治疗手段。 根据不同物种问的进化距离和功能基因的同源性，可以比较容易地找到各 种家畜、经济作物与其经济效益相关的基因，并进一步认识它们发育、生长和 抗逆的各种途径和机制。在此基础上，利用相关的基因组分子标记，就可以加 快育种的速度，将它们按照人们的愿望加以改造，为人类造福。 1 3 凼内外研究现状 闭际_ j ：生物信息学研究存发达固家中比较受重视。近年来，美国一些最著 名的大学，如哈佛大学、普林斯顿大学、斯坦福大学、加州大学伯克利分校等 都投资几千万到上亿美元成立了生物学、物理学、数学等学科交叉的研究中心。 美国n i h ( n a t i o n a li n s t i t u t e so fh e a l t h ) 的一个顾问小组建议在生物计算 领域设立总额为数亿美元的重大科研基金，并成立5 到2 0 个计算中心以处理海 上海人学硕士学位论文 量的基因组相关信息。 基因绢研究潜在的f ：! 大商业利润使得崮际上。批大型制药公司和化学公 司向该领域大舭模的进军。各大计算机公司也纷纷投巨资加强高性能计算机的 研制工作。为了满足人类基因组计划的研究需要，i b m 至今在生物科技领域已 经投资2 亿美元，集中了不同领域的5 0 名研究员专门从事计算机应用于生物科 技领域的研究，投入1 亿美元丌发有1 0 0 万个c p u 、每秒运算速度高达千万亿 次的超级计算机“蓝色基因”，专为生物信息学研究服务。 随着破译生命密码的人类基因组计划接近尾声，科学家们又全力以赴投入 到了生物学下一个挑战性领域的研究：蛋白质组学( p r o t e o m i c s ) 。人体内真正 发挥作用的是蛋白质，其中藏着开发疾病诊断方法和新药的“钥匙”。由于生 物功能的主要实现者是蛋白质，而蛋白质又有自身特有的活动规律，所以仅仅 从基因的角度来研究是不够的。美国米里亚德遗传学研究所、甲骨文公司和同 本曰立公司组成联盟，计划在3 年内完成人体所有蛋白质的图谱。美国塞莱拉 公司现己进入蛋白质组研究阶段，目的是每天对数百万个蛋白质片段进行识别 和分类，最终绘制出一张蛋白质组图。这些研究掀起了一场寻找新蛋白质以及 确定它们功能的竞赛。美国加州前线战略管理咨询公司的一项研究显示：蛋白 质组学已逐步形成产业和市场，今后5 年内这个市场的规模将有巨大发展，有 望从目前的5 6 亿美元扩大到2 0 0 5 年的2 7 7 亿美元， 国际上生物信息学发展异常迅猛，大大带动了我国生物信息学的发展。在 我吲，生物竹息学随着人类摹凶组研究的展外j 刚刚起步，但已显露出蓬勃发 展的势火。许多科研单化已经丌；! f i 或准备”始从事这方面的研究t 作。北京大 学建立起“个e b l 的镜像数据库，提供数据检索服务。在复旦大学遗传学研究 所，为克隆新基冈叮建立的一整套生物信息系统也已初具规模。p 科院l 海生 化所、生物物理所等冉结构生物学和基医i 预i 9 1 i f 研究方面也有相当的基础，中科 院计算所也= r = 始在生物信息方面投入大量的人力物力，从事相关的研究。南、 北方人类基因组中心的相继建成，北大生物城的建立等，标志着我国对生物信 息学的嚣视。我们有理相信，我园的生物信息学在2 l 世纪会有巨大的飞跃。 爿i 物倩息学研究需要高性能计算的支持，中科院计算所生物信息学试验室 创立的p r o n ol o r 卜物信息处理平台是个基于”曙光3 0 0 0 ”高性能计算机的牛 上海大学硕士学位论文 物信息并行处理半台，该半台集成大量国际通用算法以及我们自己开发的原剑 性算法，具有高度并行化、运f j ：速度快、功能丰富的特点。适于海量数据处理， 同时具有用1 r l 友好界而以及可视化功能，可以为生物学家提供良好的、高效的 计算服务。 杭州华大基因研究发展中心提供了一系列的高性能计算资源服务。曙光 2 0 0 0 、曙光3 0 0 0 、s u n 系列服务器可以提供最好最快的高性能计算服务。能够 存贮和处理海量的数据，服务于具有特殊要求的单位和研究团体。现在已经利 用这个资源提供包括蛋白质三维结构预测、新药模拟开发在内的高要求数据计 算服务。 在此基础上我国科研人员取得了可喜的成果。开发出了达到国际先进水平 的软件，比如基冈的电腑克隆软件包、d n a 序列综合特自f 信息分析软件包、蛋 白质组数拟分析研究软件包等。围绕高性能计算机系统开展大计算量算法与软 件的并行化工作，例如把b l a s t ，p h r a p ，s m i t h - w a t e r m a n 和p r o s p e c t o r 等软件的 并行化，实现最大限度地发挥大规模并行计算机的效率。其中最引人关注的是 由国家杂交水稻研究中心、华大基因研究中心和中科院遗传所植物生物技术实 验室三家单位联合开展的研究项目“超级杂交水稻基因组计划”。2 0 0 2 年4 月4 同，中国科学院和美国科学杂志在京联合举行通报会宣布：地球上一 半以上的人类所赖以生存的粮食作物水稻的基因序列不仅被中国科学家独 立绘制完成，而且获得成功“解读”，从而使人类第一次在基因组层面“认识” 水稻。期间共测了近五亿个碱基对，目静正在对有关数据进行整理，对己定位 的基因进行深入的功能鉴定和分析，并构建d n a 库。值得一提的是，通过测序 发现了与光合作用相关的基因位点，而光合作用与超高产密切相关，从而使我 们的水稻品种得到更大改良，产量更高，品质更好成为可能。由此可见，基因 工程和传统育种技术的结合。在中国农作物品种改良研究中将大有可为。 1 4 本章小结 本章主要介绍了生物信息学的背景知识。包括生物信息学的概念、研究的 意义和国内外的研究现状等三个方面。阐明了计算机科学特别是高性能计算机 系统在生物信息学研究中的巨大作用。 上海人学硕士学位论文 第2 章应用于e s t 序列的遗传算法分析 2 1 遗传物质的构成分析 在生物体的每一个体细胞核中都包含了一种叫“染色体”( c h r o m o s o m e ) 的物质【4 1 。比如说：人的每个体细胞核中都有4 6 条染色体，它们成对出现，其 中2 2 对是常染色体，一对是性染色体( x x 或者x y ) 。染色体主要由蛋白质和 d n af 脱氧核糖核酸) 这两种物质组成。d n a 是由a ，c ，g ，t ( 腺瞟呤、胞 嘧啶、鸟嘌呤、胸腺嘧啶) 四种碱基连接而成的聚合物。四种碱基互相连接的 氢键有严格的互补关系：a - 一t 、( 卜一c 。如下所示： aacggtttccggagctggattc ttgccaaaggcctcgacctaag u 幽2 - 1d n a 的纽成 1 9 5 3 年w a t s o n 和c r i c k 提出了d n a 的双螺旋结构模型，揭示了d n a 作 为遗传信息携带者的本质。二十世纪六十年代遗传密码被破译：四种碱基的每 三个碱基组成一个密码，共有6 4 种排列方式( 4 x 4 4 ) 。进一步发现密码是简 并的，即两种以上的三联体决定一个氨基酸，一共可以表示2 0 种氨基酸。这些 氨基酸不同顺序的排列以肽链连接就构成了蛋白质。生物体的所有“部件”， 包括皮、毛、骨骼、脏器都是由蛋白质构成的。蛋白质扮演着构筑生命大厦的 “砖块”角色。绝大多数生物的遗传物质都是d n a ，而且这些生物d n a 的化 学组成和碱基配对规律都是一样的，但是物种之间的差异如此之大，使我们不 禁感叹生命的奇妙。这也就是下面所介绍的基因表达的作用。 一段d n a 碱基序列的表现意义如下所示： 厂起始点终止点 1，士0 窿瓣黼 醺瞄瑚翻幽 禽外“子内含子外监子内含子外监子 图2 - 2 碱幕序列的的崽义 上海大学硕士学位论文 舛显子( e x o n s ) 是碱基序列中有编码蛋白质功能的部分。 内含子( i n t r o n s ) 是碱基序列中除了外显子，剩余的d n a 序列。 启动子( p r o m o t e r ) 是d n a 碱基链上的一个特定位点，指示基因表达的 丌始。 基因携带的生物信息的表达是高度调控的，不同细胞中会有不同的基因被 表达，细胞中活跃基因的总数决定了一个细胞的特点和它在生物体中的作用。 基因的表达由一段位于编码序列上游的被称为启动子的碱基序列调控，细胞中 一个基因的表达由其启动子的序列以及该启动子与r n a ( 核糖核酸) 聚合酶和 转录因子的结合能力来决定。 存遗传过程中，基因表达是基因编码的信息转化为细胞结构并在细胞中行 使功能的过程h 。可以由下面的简图表示： 圈2 - 3 基凶表达的过程 转录( t r a n s c r i p t i o n ) 过程中d n a 双链打开，以某一d n a 链为模板，按 照碱基互补原则形成一条新的r n a 链，是基因表达的第一步。随后在一个叫剪 切( s p l i c i n g ) 的过程中r n a 中的内含子被去除，剩下携带遗传信息的r n a 被 称为信使( m e s s e n g e r r n a ，m r n a ) ，在蛋白质合成时充当模板。r n a 中由尿 嘧啶u 代替了d n a 中的胸腺嘧啶t 。如下所示： a a c u u g u c c u u u g g a c u a c c g u u g c a a u c g g i 芏| 2 - 4r n a 的组i 成 因此得到的三联体密码子是u c a 、u a g 、g a c 、a a c 等，分别对应一种 氨基酸。m r n a 上携带的遗传信息指导蛋白质的合成过程，称为翻译 ( t r a n s l a t i o n ) 。在另外两种r n a ：核糖体r n a ( r i b o s o m a lr n a ，r r n a ) 、转运 r n a ( t r a n s f e rr n a ，t r n a ) 的共同作用下，碱基序列按照密码子的对照被翻译 成氨基酸多肽链，这个氨基酸的序列决定了蛋白质的三维空间结构，从而导致 了生命表现形式的多样性。 上海大学硕十学位论文 2 2 本文研究的切入点 介绍了遗传物质的组成和遗传机制后，就进入本文研究的正题。本文研究 的对象是一种叫“表达序列标签”( e x p r e s s e ds e q u e n c et a g ，e s t ) 的核 酸序列片段。e s t 序列是很短的序列片段( 3 0 0 5 0 0 b p ) 【6 1 。由于m r n a 序列的 极不稳定性导致无法直接对其进行测序，生物学家将m r n a 逆转录成e d n a ( 互补 d n a ) 序列，然后随机选取e d n a 克隆进行测序，得到的序列片段即e s t 序列。如 下所示： g c t t t c c c g g g a c t c g g t c c c a a c c a c c t g a | 整i2 - 5e s t 序列 由此可见，e s t 是基因组中被表达的部分，携带着完整基因的某些片段。 是进一步研究基因功能位点并发现新基因的钥匙。国际上已经出现了几个基于 e s t 的基因索日i 7 】。这些基因索引数据库( 即二次数据库) 构建了基因框架，极 大地方便了相关研究者。这些二次库按序列相似性或e s t 序列的实验克隆标记 号，将来自于同一基因的e s t 序列归类为一个簇( c l u s t e r ) ，每个簇的e s t 序列 是以非组装状态存放的，仅有部分基因功能位点的信息。利用e s t 序列数据发 现新基因，是当前国际上基因组研究的热点。中科院生物物理研究所和杭州华 大基因研究中心合作，建立了基于高性能计算机系统的e s t 数据分析平台【8 j 【9 1 。 该平台提供基因注释、分类，基因表达分析、基因编码区多态性分析等服务。 该平台的目的是提供大规模的数据处理，即对所有相关数据库中的e s t 数据进 行筛选、组装、比较，为用户提供全面的数据分析服务。这种算法进行大量的 数据库检索，计算量相当大，只有在超级计算机或者大型并行计算机上才能实 现。 在探索这一课题的过程中，有幸得到了上海血液病研究所隶属于南方基因 组的生物学家赵倩博士和孙晓建博士的大力支持和帮助。据他们介绍，每天在 各个实验室旱都会通过测序产生上百条e s t 序列，包括各种模式生物的和人类 各条染色体上的e s t 序列。相比较利用上述大型e s t 序列数据平台的检索、分 析，他们常用的是j 些小巧快捷的工具软件。比如个叫“c l u s t e r i n g 上海大学硕士学位论文 a 1 i g n m e n tt o o l s ( c a t ) ”的工具软件，能对实验中测得的e s t 序列数据进行快 速的分类和拼接，将一些初步的信息反馈给研究人员，使他们能够进一彗狩列 硝 片段进行比对，测试等工作。他们展示了从同一基因上彰叔的一簇e s t 序列拼 接起来得到e d n a 全长如下图所示： a a g c t t t c c c g g g a c t c g g t c c c t t t g g a c t t a c c g g c a a t t c g g c c d n a 伞妖 ( ：( hr ( c c g g g a c l ( g g e s t 序列】 g g g a c r c g g t c c c t t t c g 。 e s t 序列2 ( ；( ：t 1 ( 1 ( 1 ( ：( ：( ：a ( 1 1 ( g gf c c c e s t 序列3 c g g t c c c l _ t t g g a c t t a c c g g c a a e s t 序列4 ic c c lt t g g a c i f a e s t 序列5 _ _ _ _ _ _ _ - _ _ - _ _ - - _ _ _ _ _ _ _ _ e s t 序列n l 笙| 2 6 e s t 序列的拼接演示 不难看出，e s t 序列的基本特征就是各条序列间存在重复片段，将各条e s t 序列拼接还原，即将其中的重复序列叠在一起并读取全长就能得到一条被表达 基因的片段。但是从c a t 取得的结果有一个缺陷：由于这个软件在算法实现中 采取模糊匹配的方法，得到的e d n a 序列中总有一些位置上发生碱基的缺失，需 要手动修f 和补全，造成了不小的麻烦，因此我们想设计一个新的算法来克服 这个缺点。经过充分的讨论和研究，我们得到的结论是：e s t 序列的拼接就是 一个组合优化的过程。因此，将之转换成数学模型，用一种算法来实现这个过 程并克服c a t 工具的缺点是可行的。 遗传算法以其强大的全局搜索能力和避免组合爆炸的优势，在组合优化 领域得到了相当广泛的研究和应用，并已经在解决一些经典组合优化问题( 如 旅行商问题、背包问题等) 中显示了良好的性能。在e s t 序列拼接问题上，我 们从遗传算法如何解决旅行商问题( t r a v e l l i n gs a l e s m a np r o b l e m ) 中得到启发： 将每一条e s t 序列看作一个城市节点，两两城市节点问的距离可以用两条e s t 序列相互间的重复片段来表示，如图： i i 竺蚓纛三焉烹黧b 篡端 上海大学硕十学位论文 寻求各条e s t 序列的一个最佳组合也就类似于寻求t s p 问题中的一条最短 路径。 在确立了指导思想后，下面我们就进入算法应用的分析。 2 3 应用于本文研究的遗传算法分析 2 3 1 遗传算法和生物进化模型 遗传算法采纳了自然进化模型，如选择、交叉、变异等。计算开始时产 生定数目的n 个个体( 父个体1 ，父个体2 ，父个体3 ，父个体n ) ，即 种群随机地初始化，并计算每个个体的适应度函数，初始代就产生了。如果不 满足优化准则，就开始产生新一代的计算。为了产生新一代，按照适应度选择 个体，附带要求基因重组( 交叉) 而产生子代，所有的子代按一定概率变异。 然后子代的适应度又被重新计算、子代被插入到种群将父代取而代之，构成新 的代( 子个体1 ，子个体2 ，子个体3 ，子个体n ) 。这一过程循环执行， 直到满足优化准则为止。基本遗传算法的流程如下： 圈2 - 8 遗传算法的生物模型流程图 上海大学硕士学位论文 2 3 2 基本遗传算法设计的原理和方法 1 遗传算法的各个算子在不同的问题求解过程中可以有不同的变化，针对 e s t 序列的拼接问题，我们设计或选取的各个算子在下面一一介绍。 1 编码 由于是模拟t s p 问题的设计，每条e s t 序列当作一个城市节点，所以采取 实值编码。将e s t 序列的编号排列作为遗传算法种群中的个个体( 染色体) ， 以8 条e s t 序列为例就是：57 4 30 126 。 实值编码的搜索能力没有二进制编码强，但是在变异操作上比后者更能保 持种群的多样性【1 ”。实值编码的表示机制如下： 设定种群种的个体数目是n ，x ：表示第t 代的第i 个个体，ie e 1 ，2 ，n ) 。 每个个体的基因位数l = m ，由m 个实数构成，个体x ：r ”，x ：可以表示m 维的行向量，即x ，i ：( xi ( i ) x ；x p ) 。这样第t 代的种群x t 可以表示为 7”12” n + m 的矩阵x 。= ( x ：x x ，) 7 。初始种群矩阵x o = ( x ；x ；x o ) 7 中 没有相同的两行，而且每列中没有相同的元素，对任意i ：j ( i ，j 1 ，2 ，n ) ) 有x j x ；而且个体中没有两个个体的同一基因位是相同的。 在交叉操作中，任意两个互异的个体交叉后产生的新个体一定在这两个父 个体所构成的超体丌 m i n ( x j “，x ) ，m a x ( x j “，z ) 】的顶点上。可见新个体受到 父个体所构成的超体的限制。 实值编码中的个体x ：中的第p 个基因的变异操作v d 定义为： d ( x ：，p ) = x ：+ n ( 0 ，d ) 其中n ( 0 ，d ) 是均值为0 、方差为万的高斯噪声。可见实值编码操作的变异 量可以任意小。这样可以保证只要变异量足够小，产生地新个体可以与父个体 充分地接近。从而保证种群的稳定性。 上海大学硕+ 学位论文 2 适应度函数地选取 在遗传算法中存在欺骗问题，即在进化初期，会产生一些超常个体。若 按比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响了算法 的全局优化性能。在进化的后期算法接近收敛，种群中个体适应度差异较小时， 继续优化的潜能降低，可能获得某个局部最优解。为了防止上述现象的产生， 在适应度函数选取过程中应尽量避免下面两种情况： 设n 个个体的适应度函数值f l s f 2 曼。g 。，且f 一f ，= 彳i ( i = 1 , 2 ，n 一1 ) 。 a ) 若= m a x 4 i f ( i = l ，2 ，n 2 ) ) ，且an - l _ ( n - 2 _ ) ( n 一- 1 ) a ，则 f n - t 寺善f 只。 b ) 若小m a x _ 2 ，3 ，蚴) 且赴坠警坐删 眶去喜f e 在具体实现中我们注意到了防止上述情况的发生，将一条e s t 序列中与相 邻序列匹配的最长的子串长度占它的总长度的百分比定义为该序列的匹配度 m = ( m a t c h l e n g t h w h o l e l e n g t h ) x1 0 0 。以一条染色体57 430126 为例 编号为4 的序列的匹配度就是： ”，=!歪!j!三；i；i；ii；!j重绁x。4 号序列碱基总长度 ” 无法与相邻序列匹配的序列的m 就是0 。一条染色体的适应度f 就是 其中所有序列匹配度的总和( m ) 。由于采取严格匹配的原则，只取两条序列中 完全重叠的子串作为计算依据，就能克服拼接全长的碱基缺失( 断链) 问题。 3 选择操作 选择是一种全局随机搜索，在选择操作中我们采用了按比例的适应度分配 ( p r o p o r t i o n a lf i t n e s sa s s i g n m e n t ) 。也叫做轮盘赌或蒙特卡罗( m o n t ec a r l o ) 选 择。利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若某个个体 上海大学硕十学位论文 i 的适应度是f i ，则其被选择的概率表示为：p i = ，。 ，m ，r o i 4 交叉和变异操作 交叉是结合来自父代种群的信息产生新个体的操作。在此我们采用多点交 叉操作，多点交叉的破坏性可以促进解空间的搜索，使搜索更健壮以防止过早 地收敛。详情请见第四章算法实现部分。 如果只考虑交叉操作实现进化机制，在多数情况下是不行的，这与生物界 近亲繁殖影响进化历程是类似的。因为种群的个体数目是有限的，经过若干代 交叉操作，将出现源于一个较好祖先的子个体逐渐充斥整个种群的现象，种群 会过早收敛( p r e m a t u r ec o n v e r g e n c e ) ，最后获得的个体不能代表问题的最优解。 为避免过早收敛，有必要在进化过程中加入具有新遗传基因的个体。解决办法 之一是效法自然界生物变异。模仿生物变异的遗传操作，对于基因码进行的小 概率变化，即达到变异的目的。 变异本身是一种局部随机搜索，与选择交叉操作结合在一起，在保持种群 的多样性防止过早收敛的同时，保证了遗传算法的有效性。实值变异的步长选 择比较困难，最优的步长视具体情况而定。这里采用的经验公式是： x = x 0 5 l 其中舭萋警州d 以概率击取值l ，以1 一去取值0 ，通常一2 0 ； l 为变量的取值范围：x 为变异前变量取值；x 为变异后变量取值。 如何确定算法的参数中交叉概率p c 和变异概率p m 是影响遗传算法行为和 性能的关键所在3 l ，直接影响算法的收敛性和精度。这两个值的过大或过小都 会对遗传算法的进行有副作用。我们采用了一种自适应遗传算法a g a ( a d a p t i v e g a ) ，p c 和p m 能够随个体适应度的变化自动调整，以提供最佳的p c 和p m 。 具体实现在第四章中详细介绍。 2 3 3 遗传算法的并行优化 一般来讲，串行遗传算法可以在合理的计算时间内发现问题的满意最优解 上海大学硕十学位论文 但随着问题规模和复杂度地不断提高，串行遗传算法的搜索过程将会成倍地延 长。因此，在提高遗传算法搜索速度研究上的一个重要方向就是并行化 1 ”，实 现算法的并行化后它的效率将大大提高。而遗传算法并行性是与生俱来的。在 自然进化的任何时刻，总是同时有大量的物种在彼此独立地向前进化。在同一 物种内部，也同时存在着大量的个体通过自然选择、交配和基因突变而同时进 化着。显然，自然界的进化过程本身就是一个并行过程。遗传算法是人们对自 然进化过程的机器模拟，分别用选择( s e l e c t i o n ) 、交y ( c r o s s o v e r ) 和变异( m u t a t e ) 等遗传操作来模拟自然进化过程中的自然选择、交配和基因突变。遗传算法来 源于自然进化，与自然进化有密不可分的关系，很自然的也就继承了自然进化 过程所固有的并行性。 从图2 8 可以看到：算法只有在最外层( 初始化部分) 是纯串行的，而在 内部层次上存在着许多潜在的并发性。遗传算法的并行化主要分为三个模式： 主从式( m a s t e r - - s l a v e ) 、粗粒度孤岛模型( i s l a n d sm o d e l ) 、细粒度领域模 型( 扩散式模型d i f f u s i o nm o d e l ) 。其中，粗粒度模型与自然进化形式最接 近，将种群分成若干个子群并分配给各自对应的处理机，每个处理机上的子群 体所含个体的数量大于l ，各子群体在其各自的处理机上并行独立地运行简单 遗传算法，进行计算适应度。选择，重组交叉和变异等操作。在一定的时间间 隔后各个子群体按一定的拓扑结构交换特定的个体，也就是模拟自然界各个物 种群体间的基因播散过程。该模型对系统平台要求不高，可以是松散耦合并行 系统，最适用于内存分布式的m i m d 机器，使机器的潜能最大地发挥。在本文研 究中我们采用的就是粗粒度模型的并行遗传算法。 并行遗传算法粗粒度模型的示例如下： 岛屿分布的子群体 图2 - 9 并行遗传算法的相i 粒度模型 迁移 上海大学硕士学位论文 迁移( m i g r a t i o n ) 是并行遗传算法引入的一个新算子，它模拟了自然界在 进化过程中子群体间个体扩散的行为。迁移算子的采用使并行遗传算法更适合 于全局寻优并且计算量较小。迁移策略可以从几个方面来考虑：迁移个体的选 择方法、迁移个体的数量、迁移周期、迁移的拓扑结构。每一个方面都有很多 种不同的方法可供选择，通常根据具体的问题来制订迁移策略。 并行遗传算法的性能主要体现在收敛速度和精度两个方面，其主要影响因 素是子群体的数量、规模、和个体迁移策略。在这个应用于e s t 序列拼接的并 行遗传算法设计中两个必须关注的地方是： 1 个体适应度的计算占整个算法计算量的很大比重，因此，要确保各节 点的负载均衡，高效地实现算法的并行化。 2 设计合理的数据结构以使各进程的通信开销不能过大，确保并行算法 的高效率。 最后我们要考虑的是：利用现有的编程手段如m p i 库的帮助，就可以 根据串行遗传算法设计出其并行版本。我校自强2 0 0 0 集群式高性能计算机系统 是实瑚这种并行算法的良好环境。生物研究所的内部局域网抑或是一台配置先 进的p c 机上的多个进程也可以模拟这种集群环境，轻松移植并行算法，为算 法的实际应用提供了操作平台。 2 4 本章小结 这一章主要介绍本文研究的切入点。从遗传物质的构成和遗传机制入手， 讲述了e s t 序列的生物学意义和基本遗传算法的原理，分析了本文研究的一些 基础理论和数学模型：比如e s t 序列的拼接问题如何与遗传算法结合、基本遗 传算法的流程和遗传算法并行化的讨论。本章制定了研究的框架，为下文的进 一步展丌做了铺挚。 上海人学硕士学位论文 第3 章高性能计算机系统和m p i 编程环境 本次研究以我校的集群式高性能计算机系统“自强2 0 0 0 ”作为测试平台， 所以有必要介绍一下相关的软硬件环境。 3 1 高性能计算机简介 随着人类文叫的进步，我们在探索道路上遇到的问题也越来越复杂，就需 要制造出更先进的t 具柬辅助。2 1 世纪人类遇到的课题是：基因工程，全球天 气的准确预报，地球物理模拟，核爆炸模拟等。要处理这些问题中的巨量数掘 仅仅依靠提高节个处理器的运算速度显然是不能胜任的。因此，利用多个处理 器之间的并行处理成为提高计算速度的一个很自然的选择，大规模并行计算已 经成为研究科学和工程技术问题的一种崭新的手段和方式。 目前世界上的大规模并行机的峰值速度已达每秒力亿次以上。2 0 0 3 年6 月 2 3 号，在德国海德堡召丌的超级计算机会议公稚的最新t o p5 0 0 名单中，最高 记录是由n e c 公司为只本横滨地球模拟中心制造的超级计算机，峰值速度达到 3 5 8 6t f l o p s ( 万亿次每秒) ，随后是h p ( 惠普) 用在美国阿拉莫斯国家实验 室的a i p h a s e r v e r ，以及用在美国劳伦斯利弗莫尔国家实验室的两个h p 系统。 在我国，2 0 0 3 年2 月，联想的“深腾1 8 0 0 ”万亿次高性能计算机已经开始为大 庆油阳承担石油地震资料处理生产性业务。2 0 0 3 年3 月，由中科院计算所和曙 光共同研制完成的“曙光4 0 0 0 l ”超级服务器通过了专家组的验收。这套系统 的浮点计算速度峰值到达了每秒3 万亿次，并捐j 有6 4 4 g b 内存，百万亿字节 ( 1 0 0 t b ) 的数据存贮能力，标志着我国的高性能计算机性能水平又上了一个 新台阶。值得注意的是，这些系统不再以峰值速度作为研制目的，而将重点放 在特定应用的实际性能方面，针对客户的需求在科研模式上