（计算机软件与理论专业论文）生物基因序列比对算法的并行优化研究.pdf

摘要 本文在介绍了不同基因序列比对算法及其各自优缺点的基础上，针对s m i t h w a t e r m a n 算法着重分析了一些并行化方法，并结合集群式( c l u s t e r i n g ) 计算机 系统提出了一种全新的并行优化算法。该算法引入了哈希( h a s h ) 函数，在将原 算法串行优化的同时，减弱了其原有的强数据相关性，并进行了合理的并行优化。 该优化算法更快，更具平台适应性，真正充分利用到了近期蓬勃发展的高性能集 群式计算机系统，符合当今科技发展趋势。 该算法的主要思想是：利用h a s h 函数对欲比较序列进行采样，抽取部分样 本进行初期比较。初期比较完毕后得到若干可能相似的序列，此时才进行完整的 比较，得到符合用户要求的相似序列。该算法不仅减少了总比较次数，加强了比 对效果，缩减了比对时间，而且将原来数据相关性很强、不适合并行化的动态规 划算法改变成为可并行化且易季并行化的新的优化算法，使其能够自如地运行在 各种高性能并行计算机系统上。 该算法是通过消息传递接口( m p i ) 嵌入c c + + 编程实现的，运行在l i n u x 系统平台上。各进程之间的通信由消息传递的方式完成，已成功地运行在自强 2 0 0 0 高性能机群上，获得了可喜的结果。 本次研究的主要任务如下： 1 收集众多的生物基因序列比对算法，经过初步的分析、研究，从中找出 s m i t h w a t e r m a n 算法进行研究，它很常用但难以并行化。 2 借鉴世界著名期刊b i o i n f o r m a t i c s 中e f f i c i e n tl a r g e s c a l e s e q u e n c e c o m p a r i s o nb yl o c a l i t y s e n s i t i v eh a s h i n g 一文中的思想，通过引入h a s h 函 数的方法，将s m i t h - w a t e r m a n 算法变换结构，使之易于并行化，并结合 不同并行机的特征，设计出了通用的并行化算法。 3 对l i n u x 编程接口进行深入研究，对m p i 接口的集群式系统的工作原理 进行分析，由此设计出能充分利用并行机工作的序列比对程序。 本次研究项目来源于上海市科委重点基金项目“网络环境中若干关键技术的 研究”的子题目“算法并行化及其应用”。此算法的测试工作就是在集群式系统 自强2 0 0 0 上完成的。该系统属粗粒度并行系统，与细粒度系统相比，通信代价 较高，但由于较高的性价比，使其更易被广泛应用，现已被应用在航空、航天、 金融、生物、气象等多种应用及科技领域。 关键词：生物信息学算法；并行化；高性能；集群机；序列比对算法 a b s t r a c t i nt h i st h e s i s ，s o m ed i f f e r e n ts e q u e n c ea l i g n m e n ta l g o r i t h m sa r ei n t r o d u c e df i r s t o nt h eb a s i so ft h a t ，s m i t h - w a t e r m a na l g o r i t h mw i l lb ea n a l y z e dp a r t i c u l a r l y b y u s i n gc l u s t e r i n gc o m p u t e rs y s t e m s ，ab r a n n e wp a r a l l e l i z i n go p t i m i z i n ga l g o r i t h mw i l l b e p u tf o r w a r d t h ea l g o r i t h mi n t r o d u c e dh a s h f u n c t i o n ，b e s i d e so p t i m i z i n gt h eo r i g i n a l g o r i t h m ，i ta l s or e d u c e dt h ed a t ar e l a t i o n s ，w h i c hb e n e f i t e dt h ep a r a l l e ls y s t e mb y p a r a l l e l i z i n gp r o p e r l y t h o s em a k ei t f a s t e r , m o f ep l a t f o r m i n d e p e n d e n t ，a n dm o r e s u i t a b l ef o rh i g h p e r f o r m a n c e c l u s t e r i n gc o m p u t i n gs y s t e mo f t o d a y t h em a i ni d e ao ft h ea l g o r i t h mi st os a m p l et h ei n p u tq u e u e sb yh a s hf u n c t i o n u s et h es a m p l e st op r o c e s st h ef i r s tc o m p a r i s o n a f t e rt h a t ，s o m es i m i l a rs e q u e n c e s w i l lb ef o u n d a tt h a tt i m et h ec o m p l e t ec o m p a r i s o nc a nb es t a r t e dt ow o r ko u tt h e s i m i l a rs e q u e n c e st h a tc u s t o m e r s r e q u i r ef o r t h ea l g o r i t h m n o to n l yr e d u c e st h et i m e s o f c o m p a r i s o n s ，b u ta l s oe n h a n c e st h ec o m p a r i s o ne f f e c ta n dc u t st h ec o m p a r i s o nt i m e i t c h a n g e st h eo r i g i n a ld y n a m i cp r o g r a m m i n ga l g o r i t h m ( w h o s ed a t ai s s t r o n g l y r e l a t e da n dn o ts u i t a b l ef o rp a r a l l e l i z a t i o n ) t oan e w o p t i m i z e da l g o r i t h m ( w h i c hc a r l b ee a s i l yp a r a l l e l i z e d ) i tc a l lr u no na l lk i n d so f h i g h - p e r f o r m a n c ep a r a l l e lc o m p u t e r s y s t e m sf r e e l ya n de f f e c t i v e l y t h ea l g o r i t h mi sp r o g r a m m e d u s i n gc c + + a n di n t e r f a c em p ii m b e d d e d ，w h i c h i sp e r f o r m e do np l a t f o r ml i n u x t h em e t h o dc o m m u n i c a t i o na m o n gt h ec o u r s e si s m e s s a g ep a s s i n g t h es y s t e mi sn o w r u n n i n go n t h ez i q i a n g2 0 0 0h i g h - p e r f o r m a n c e c l u s t e r i n gc o m p u t e rs y s t e m s t h er e s u l ti sg r a t i f y i n g t h em a i nt a s ki sa sf o l l o w s ： 1 g a t h e rs o m ef a m o u ss e q u e n c e a l i g n m e n ta l g o r i t h m si nb i o e n g i n e e r i n gf i e l d b ya n a l y z i n gt h o s e ，s m i t h - w a t e r m a nw a sf o u n d ，f o ri t sp o p u l a r l yu s e da n d d i f f i c u l t yo f p a r a l l e l i z i n g 2 u s et h er e f e r e n c ee f f i c i e n tl a r g e s c a l e s e q u e n c ec o m p a r i s o nb yl o c a l i t y ， s e n s i h v eh a s h i n go ft h ef a m o u sw o r l d w i d ej o u r n a lb i o i n f o r m a t i c s u s i n g - i l i h a s hf u n c t i o n ，w ec h a n g e dt h es t r u c t u r eo fs m i t h w a t e r m a n ，t om a k ei t e a s i e rt ob ep a r a l l e l i z e d f o r d i f f e r e n t p a r a l l e lc o m p u t e rs y s t e m s h a v e d i f f e r e n tc h a r a c t e r s ，ag e n e r a lp a r a l l e la l g o r i t h mh a sb e e nd e s i g n e d 3 s t u d yt h el i n u xp r o g r a m m i n gi n t e r f a c e a n a l y z et h ep r i n c i p l eo fc l u s t e r i n g c o m p u t e rs y s t e m sw i t hm p ii n t e r f a c e o nt h eb a s i so ft h o s e ，t od e s i g na p a r a l l e ls e q u e n c ea l i g n m e n tp r o g r a mm a k i n gf u l l u s eo fm o d e m p a r a l l e l c o m p u t e rs y s t e m s t h i st h e m ei s s u p p o r t e db yt h e s c i e n c ef o u n d a t i o no fs h a n g h a i m u n i c i p a l c o m m i s s i o no fs c i e n c ea n dt e c h n o l o g y t h er e s e a r c ht i t l ei s ”r e s e a r c ho fs o m e k e y t e c h n o l o g i e si nt h en e t w o r ke n v i r o n m e n t ”，w i t ha s u b t i t l eo f ”a l g o r i t h m sp a r a l l e l i s m a n da p p l i c a t i o n ”t h ea l g o r i t h mw a st e s t e do nz i q i a n g2 0 0 0 ，ac l u s t e r i n gc o m p u t e r s y s t e m t h es y s t e mi s ac o a r s e g r a i n e d s y s t e m c o m p a r i n gw i t ht h ef i n e g r a i n e d s y s t e m ，i t h a sah i g h e rc o m m u n i c a t i o ne x p e n s e h o w e v e rf o rt h e i r h i g h e rc o s t p e r f o r m a n c e ，t h ec o a r s e g r a i n e ds y s t e m sa r ew i d e l yu s e di nm a n yf i e l d so f a p p l i c a t i o n a n ds c i e n c e ，s u c ha sa v i a t i o n ，s p a c e f l i g h t ，f i n a n c e ，b i o l o g y , m e t e o r o l o g y , e t c k e y w o r d s ：a l g o r i t h m p a r a l l e l i z a t i o n ；h i g h - p e r f o r m a n c e ； c l u s t e r i n g b i o i n f o r m a t i c s ；s e q u e n c ea l i g n m e n ta l g o r i t h m 1 v 上海大学工学硕士学位论文 引言 人类基因组计划( h u m a ng e n o m ep r o j e c t ，h g p ) 于1 9 9 0 年正式实施以来， 世界各国纷纷投入巨资，建立了自己的生物信息学研究机构，为解读人类基因组 这部“生命书”而努力。 在当前的生物经济时代，基因不是金钱，但胜过金钱。洛克菲勒大学有一条 肥胖基因，售价高达2 0 0 0 万美元。由于经济利益的驱动，已有2 0 0 0 个“功能已 知的基因”被授予专利。这样，受谴责的“基因专利”便获得公认，迫使人们改 变原来的伦理观念，不得不参加“基因争夺战”。因为人类基因组的基因总数是 有限的，毕竟只有6 万1 0 万个。每当一个基因获专利，就等于少了一个基因。 于是，人们为了专利而抢夺基因。特别是我国的基因资源，常常无偿地被国外掠 夺，丧失知识产权，连当事人也不知情。因此，我们只有参与竞争去争取。为了 捍卫宝贵的基因资源，防止被其他国家窃取，我国于1 9 9 4 年终于正式启动了人 类基因组计划。 随着计划的实施和进展，不断产生巨量的分子生物学数据，如核苷酸序列。 这些数据有着数量巨大和关系复杂等特点，不利用计算机是根本无法实现数据的 存储和分析的，于是生物信息学这门新兴的综合性学科便悄然兴起，并蓬勃 发展起来。 生物信息学最首要的任务，是从数据中提取知识。而“比较”则是科学研究 中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。在生物 信息学研究中，序列比对是最常用和最经典的研究手段，是研究的重要基础。 将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物 学领域中绝大部分的问题在计算机科学领域中主要体现为序列或字符串的问题。 随着人类基因组计划的快速进展，d n a 和蛋白质序列数据库的规模正呈指数增 加，伴随着序列数据库的增长，三维结构数据库也在不断增长，这就迫切地需要 开发用于对这些巨量数据进行分析的方法和工具。于是，提高序列比对算法的效 率成了一项重要的研究课题。 当今科技正在飞速地向前发展，信息量也在不断地增大，高性能计算技术已 经广泛应用于生物科学，空闻科学，天文学，人工智能，气象学，图像处理等各 上海大学工学硕士学位论文 个研究领域，它们的计算量常达万亿次。为了在生物信息学领域能够更好的运用 现有资源，发挥特长，就要对这些领域内的算法进行一定的并行优化，将串行算 法优化后移植到高性能并行机上充分和用到“高性能”、“高效率”。 本文即对生物序列比对算法之一世界知名的s m i t h w a t e r m a n 算法 进行了并行优化，使其可以在集群式高性能并行机上进一步得到高效的运用。同 时，也充分发挥了我校自强2 0 0 0 的优势，使其成功地运用在生物信息研究领域。 上海大学工学硕士学位论文 第一章生物信息学背景介绍 1 1 生物信息学简介 生物信息学( b i o i n f o r m a t i c s ) 就其萌生而言，是一门比较古老的学科，因为 早在计算机初创期的1 9 5 6 年就已经在美国田纳西州的g a t l i n b u r g 召开过首次“生 物学中的信息理论讨论会”；而就其发展而言，却是- - i 1 相当年轻的学科，因为 继2 0 余年的沉默之后，只有伴随着八、九十年代计算机技术的迅猛发展，它才 同时得以获得自身的大发展。无论从理论上来讲还是从现实情况来看，生物信息 学的实质就是利用计算机科学和网络技术来解决生物学问题。它的诞生和发展是 应时所需，是历史的必然，已经悄然渗透到生物科学的每一个角落，以至人们在 意识到它的存在之前就已经离不开它了! 二十世纪尤其是末期，生物科学技术的迅猛发展，无论从数量上还是从质量 上，都极大地丰富了生物科学的数据资源，数据资源的急剧膨胀首先迫使我们不 得不考虑寻求一种强有力的工具去组织他们，以利于对已知生物学知识的储存和 进一步加工利用。大量多样化的生物学数据资源中必然蕴含着大量重要的生物学 规律，这些规律是我们解开许多生命之谜的关键所在，然而继续沿用传统手段以 人脑来分析如此庞杂的数据实在是太勉为其难了! 人们同样需要寻求一种强有力 的工具去协助人脑完成这些分析工作。可以说，伴随着二十一世纪的到来，生物 科学的重点和潜在的突破点已经由二十世纪的试验分析和数据积累转移到数据 分析及其指导下的试验验证上来，生物科学也正在经历着一个从分析还原思维到 系统整合思维的转变。那么，我们所寻求的那种强有力的数据处理分析工具就成 为未来生物科学的关键所在；刚巧，伴随着生物科学这需求的加剧，以数据处 理分析为本质的计算机科学技术和网络技术同样获得了突飞猛进的进展，自然就 成为生物科学家的必然选择，计算机科学技术和网络技术日益渗透到生物科学的 方方面面，一门崭新的、正是如火如荼的、拥有巨大发展潜力的生物信息学也就 悄然而坚定地发展和成熟起来了! 可以说，历史必然性的选择了生物信息学 生物科学与计算科学的融合体作为下一代生物科学研究的重要工具。 八十年代末期，林华安博士认识到将计算机科学与生物学结合起来的重要意 上海大学工学硕士学位论文 义，终于为这一领域构思了一个合适的名称生物信息学( b i o i n f o r m a t i c s ) ， 林博士也因此赢得了“生物信息学之父”的美誉。 生物信息学是在此背景下发展起来的综合运用生物学、数学、物理学、信息 科学以及计算机科学等诸多学科的理论方法的崭新交叉学科。生物信息学是内涵 非常丰富的学科，其核心是基因组信息学，包括基因组信息的获取、处理、存储、 分配和解释。基因组信息学的关键是“读逢”基因组的核昔酸顺序，即全部基因 在染色体上的确切位置以及各d n a 片段的功能；同时在发现了新基因信息之后 进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行药物设计。了 解基因表达的调控机理也是生物信息学的重要内容，根据生物分子在基因调控中 的作用，描述人类疾病的诊断、治疗内在规律。它的研究目标是揭示“基因组信 息结构的复杂性及遗传语言的根本规律”，解释生命的遗传语言。生物信息学已 成为整个生命科学发展的重要组成部分，成为生命科学研究的前沿。 1 ，2 国内研究现状 二十一世纪是生命科学的世纪，其里程碑就是即将于今年完成的，历时1 3 年，耗资数十亿的著名的人类基因组计划( h u m a ng e n o m ee r o j e c t ，h g p ) 。因 为该计划的完成将为最终揭示人体构造之迷奠定坚实的数据基础；而应人类基因 组计划和生物科学迅猛发展的要求而迅速兴起的生物信息学则历史性地成为下 一世纪生命科学浪潮中当仁不让的弄潮儿。 国内对生物信息学领域越来越重视，在一些著名院士和教授的带领下，在各 自领域取得了一定成绩，有的在国际上还占有一席之地，如北京大学的罗静初和 顾孝诚教授在生物信息学网站建设方面、中科院生物物理所的陈润生研究员在 e s t 序列拼接方面以及在基因组演化方面、天津大学的张春霆院士在d n a 序列 的几何学分析方面、中科院理论物理所郝柏林院士、清华大学的李衍达院士和孙 之荣教授、内蒙古大学的罗辽复教授、上海的丁达夫教授等等。 到1 9 9 9 年1 2 月1 5 日发布的第1 1 5 版为止，g e n b a n k 中的d n a 碱基数目 已达4 6 亿5 千万，d n a 序列数目达到5 3 5 万；其中e s t 序列超过3 3 9 万条； u n i g e n e 的数目已达到7 万个；已有2 5 个模式生物的完整基因组被测序完成， 上海大学工学硕士学位论文 另外的7 0 个模式生物基因组正在测序当中。 到2 0 0 0 年1 月2 8 日为止，人类基因组已有1 6 f 1 0 序列完成测定，另外3 7 7 的序列已经初步完成；同时功能基因组和蛋白质组的大量数据已开始涌现a 如何 分析这些数据，从中获得生物结构、功能的相关信息是基因组研究取得成果的决 定性步骤。 新年伊始，在生命科学界纪念d n a 双螺旋结构模型建立5 0 周年和世界第 个基因工程实验完成3 0 周年的热烈气氛中，1 0 0 0 多名生命科技领域科研人员 参加了今天在北京大学医学部举行的北京生命科学领域联合年会。国家“8 6 3 ” 计划生物技术领域首席科学家强伯勤院士在会上提出6 点预言。其中提到：继人 类基因组计划取得突破性进展之后，全基因组的精细图有望于今年4 月完成。 我国是全球第一人口大国，对于国家来说，能否清楚地掌握自身的生物信息 资源，并对其进行有效的管理，为生命科学研究人员提供方便的信息查询，避免 重复研究，有效地保护知识产权，促进交流与合作，是当前我国基因研究领域急 需解决的首要问题。为了使我国的生命科学研究从一开始就能够步入正轨，在国 家”8 6 3 “计划生物技术领域的资助下，生命科学研究院生物信息中心于2 0 0 0 年3 月正式成立，并作为生命科学研究院的主要技术平台之一开展了一系列的工作， b i o s i n o 数据库集是生命科学研究中心开发的第一个面向国内外的公共核酸序列 数据库，该数据库的主要功能是接受国内核酸序列的注册，进行核酸序列数据库 的同源性搜索。 但从全国总体上来看与国际水平差距很大。一方面，国内生物( 医药) 科学 研究与开发对生物信息学研究和服务的需求市场非常广阔；另一方面，真正开展 生物信息学具体研究和服务的机构或公司却相对较少，仅有的几家科研机构主要 开展生物信息学理论研究，声称提供生物信息学服务的公司所提供的服务也仅局 限于简单的计算机辅助分子生物学实验设计，而且服务体系并不完善；目前国内 互联网上已经有了几家生物信息学网站，但大部分偏重于所有生物( 医) 学领域 的新闻报道，生物信息学专业技术服务的含量太少( 这其实也是国内生物信息学 研究力量薄弱的必然体现) ，这就与国外有了较大差距。为了弥补这个差距，我 国的生物信息学领域需要投入更多的人力物力，来促进其更快的发展，与世界接 轨。 上海大学工学硕士学位论文 1 3 国外研究现状 国外也一直非常重视生物信息学的发展，各种专业研究机构和公司如雨后春 笋般涌现出来生物科技公司和制药工业内部的生物信息学部门的数量也与日俱 增。但由于对生物信息学的需求是如此迅猛，即使是像美国这样的发达国家也面 临着供不应求、人才匮乏的局面。尽管在许多大学和研究机构已经各自成立了自 己的生物信息学部门或中心，1 9 9 9 年6 月3 日，美国国家卫生研究院( n i h ) 的 专家委员会还是建议，迅速在大学和研究机构中建立2 0 个生物计算中心，给予 每个中心每年8 0 0 万美元的支持，从事有关研究和人才培养。 近来，英国鉴于国内对生物信息学专业入才日益迫切的需求，所有主要的研 究资助机构：医学研究委员会( m r c ，m e d i c a lr e s e a r c hc o u n c i l ) 、生物技术和 生物科学研究委员会、工程学和物理科学研究委员会( e p s r c ，e n g i n e e r i n g a n d p h y s i c a ls c i e n c e sr e s e a r c hc o u n c i l ) 、粒子物理和天文学研究委员会( p p a r c p a r t i c l ea n d a s t r o n o m yr e s e a r c hc o u n c i l ) 和w e l l c o m et r u s t 不仅已经达成共识， 认为应该高度优先地满足对生物信息学技术的需求，而且已经实现了对生物信息 学人才培养的大力资助。 事实上，欧美等发达国家在生物信息方面已有较长时间的积累。从数据库的 角度来讲，早在6 0 年代，美国就建立了手工搜集数据的蛋白质数据库。美国洛 斯阿拉莫斯国家实验室1 9 7 9 年就已经建立起g e n b a n k 数据库，欧洲分子生物学 实验室1 9 8 2 年就已经提供核酸序列数据库e m b l 的服务，日本也子1 9 8 4 年着 手建立国家级的核酸序列数据库d d b j 并于】9 8 7 年开始提供服务。从专业机构 的角度来讲，美国于1 9 8 8 年在国会的支持下成立了国家生物技术信息中心 ( n c b i ) ，其目的是进行计算分子生物学的基础研究，构建和散布分子生物学数 据库；欧洲于1 9 9 3 年3 月就着手建立欧洲生物信息学研究所( e b i ) ，日本也于 1 9 9 5 年4 月组建了自己的信息生物学中心( c i b ) 。 目前，绝大部分的核酸和蛋白质数据库由美国、欧洲和日本的3 家数据库系 统产生；他们共同组成了d d b j e m b l g e n b a l l k 国际核酸序列数据库，每天交 换数据，同步更新。其他些国家，如德国、法国、意大利、瑞士、澳大利亚、 丹麦和以色列等，在分享网络共享资源的同时，也分别建有自己的生物信息学机 构、二级或更高级的具有各自特色的专业数据库以及自己的分析技术，服务于本 上海大学工学硕士学位论文 国生物( 医学) 研究和开发，有些服务也开放于全世界。 2 0 0 2 年1 0 月7 日，英国科学家悉尼布伦纳( s y d n e y b r e n n e r ) 、约翰苏 尔斯顿( j o h n e ，s u l s t o n ) 和美国科学家罗伯特霍维茨( h r o b e r t h o r v i t a ) 因在 “器官发育和程序性细胞死亡的遗传学调控”方面做出的卓越贡献而荣膺2 0 0 2 年度诺贝尔生理学或医学奖。他们根据对线虫的研究，找到了所谓“死亡基因”。 现在人们已经知道人类基因组中也存在着多数与线虫中控制细胞死亡相类似的 基因。细胞产生和细胞死亡在机体中保持着一种动态平衡，这种平衡一旦被打破， 就会产生很多疾病。当程序性细胞死亡发生障碍，细胞只生不死，这时就会发生 肿瘤、自身免疫性疾病等。而过多的细胞死亡，又会导致像艾滋病、神经退化性 疾病、中风、心肌梗死等。因此无论是抑制还是激活程序化细胞死亡都有重大的 医疗价值。一旦彻底弄清楚了细胞死亡的全过程，现今困扰人们的一些疾病将会 得到很好的控制。 2 0 0 3 年1 月1 日，专业杂志英国自然的网站上公布了这样条消息： 继人类第2 2 、2 l 和2 0 号染色体上的基因于近年陆续被破译之后，一个国际科研 小组日前又破译出人体第1 4 号染色体上的基因，使得人体染色体这部包含2 3 “章”的“天书”被破译出4 “章”。科学家们对第1 4 号染色体上的8 千多万个 碱基对完成了测序，对上面的所有基因进行了破译，共发现大约1 0 0 0 个基因， 准确率达到9 9 9 9 。此次科学家们确定的1 0 0 0 多个基因中，有9 6 的基因此前 已经被科学家们陆续单独发现，且包含个此前己被发现的与阿尔茨海默症有联 系的基因。此外，还有多个基因与一些遗传疾病密切相关，并有大量基因对人体 免疫系统有重要意义。 近期，目本科学家通过老鼠实验发现了生成精子的关键基因，该成果有可能 帮助人们治疗精子异常导致的不孕症。2 0 0 3 年1 月1 3 日，有关研究人员在日 本经济新闻上介绍，这种基因叫“z f p l 4 8 ”，它控制合成的蛋白质还影响其它 基因。此外，还发现，由于“z f p l 4 8 ”不发挥作用老鼠脑神经发育也出现了 障碍。由此推断，这个基因在动物发育过程中发挥着各种各样的作用，其功能低 下会导致发育不良。今后科学家们将进一步研究这一基因，以便弄清神经和脑发 育异常的机理。 一一占查奎兰三堂堡主兰垡堡壅 h _ - _ _ - _ _ _ _ _ - _ _ _ _ _ h _ _ _ _ - _ - d _ _ _ q _ _ 第二章同源比较算法 t 。比较”是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象 可能具备的特性。在生物信息学研究中，“比对”是最常用和最经典的研究手段， 是实现同源 较的方法。 比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行 比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询 序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮 助。近年来随着生物信息学数据大量积累和生物学知识的整理，通过比对方法可 以有效地分析和预测一些新发现基因的功能。 2 1 序列比对方法概述 序列比对算法分为两种：序列两两比对和多序列比对。 2 1 1 序列两两比对 序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就 推o n , f j 二者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段的缺 失、以及序列重组等遗传变异过程分别演化而来。序列相似和序列同源是不同的 概念，序列之间的相似程度是可以量化的参数，而序列是否同源需要有进化事实 的验证。在残基一残基比对中，可以明显看到序列中某些氨基酸残基比其它位置 上的残基更保守，这些信息揭示了这些保守位点上的残基对蛋白质的结构和功能 是至关重要的，例如它们可能是酶的活性位点残基，形成二硫键的半胱氨酸残基， 与配体结合部位的残基，与金属离子结合的残基，形成特定结构m o t i f 的残基等 等。但并不是所有保守的残基都一定是结构功能重要的，可能它们只是由于历史 的原因被保留下来，而不是由于进化压力而保留下来。因此，如果两个序列有显 著的保守性，要确定二者具有共同的进化历史，进而认为二者有近似的结构和功 能还需要更多实验和信息的支持。通过大量实验和序列比对的分析，一般认为蛋 上海大学工学硕士学位论文 白质的结构和功能比序列具有更大的保守性，因此粗略的说，如果序列之间的相 似性超过3 0 ，它们就很可能是同源的。 早期的序列比对是全局的序列比较，但由于蛋白质具有的模块性质，可能由 于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描 述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基 的相似性分数，分数越高则说明两个残基越相似。因此，序列比对问题变成在矩 阵里寻找最佳比对路径，目前最有效的方法是n e e d l e m a n w u n s c h 动态规划算法， 在此基础上又改良产生了s m i t h w a t e r m a n 算法和s i m 算法。在f a s t a 程序包中 可以找到用动态规划算法进行序列比对的工具l a l i g n ，它能给出多个不相互交 叉的最佳比对结果。 在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和空 位罚分。粗糙的比对方法仅仅用相同不同来描述两个残基的关系，显然这种方 法无法描述残基取代对结构和功能的不同影响效果，缬氨酸对异亮氨酸的取代与 谷氨酸对异亮氨酸的取代应该给予不同的打分。因此如果用一个取代矩阵来描述 氨基酸残基两两取代的分值会大大提高比对的敏感性和生物学意义。虽然针对不 同的研究目标和对象应该构建适宜的取代矩阵，但国际上常用的取代矩阵有 p a m 和b l o s u m 等，它们来源于不同的构建方法和不同的参数选择，包括 p a m 2 5 0 、b l o s u m 6 2 、b l o s u m 9 0 、b l o s u m 3 0 等。对于不同的对象可以采 用不同的取代矩阵以获得更多信息，例如对同源性较高的序列可以采用 b l o s u m 9 0 矩阵，而对同源性较低的序列可采用b l o s u m 3 0 矩阵。 空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有什么合适的 理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观 特色。一般的处理方法是用两个罚分值，一个对插入的第一个空位罚分，如1 0 1 5 ；另一个对空位的延伸罚分，如1 2 。对于具体的比对问题，采用不同的 罚分方法会取得不同的效果。 对于比对计算产生的分值，到底多大才能说明两个序列是同源的，对此有统 计学方法加以说明，主要的思想是把具有相n t q 度的随机序列进行比对，把分值 与最初的比对分值相比，看看比对结果是否具有显著性。相关的参数e 代表随 机比对分值不低于实际比对分值的概率。对于严格的比对，必须e 值低于一定 上海大学工学硕士学位论文 闽值才能说明比对的结果具有足够的统计学显著性，这样就排除了由于偶然的因 素产生高比对得分的可能。 g e n b a n k 、s w i s s p r o t 等序列数据库提供的序列搜索服务都是以序列两两 比对为基础的。不同之处在于为了提高搜索的速度和效率，通常的序列搜索算法 都进行了一定程度的优化，如最常见的f a s t a 工具和b l a s t 工具。f a s t a 是 第一个被广泛应用的序列比对和搜索工具包，包含若干个独立的程序。f a s t a 为了提供序列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典里 搜索可能的匹配序列，字典中的序列长度由k t u p 参数控制，缺省的k t u p = 2 。f a s t a 的结果报告中会给出每个搜索到的序列与查询序列的最佳比对结果，以及这个比 对的统计学显著性评估e 值。f a s t a 工具包可以在大多提供下载服务的生物信 息学站点上找到。 b l a s t 是现在应用最广泛的序列相似性搜索工具，相比f a s t a 有更多改进， 速度更快，并建立在严格的统计学基础之上。n c b i 提供了基于w e b 的b l a s t 服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务 器上进行搜索，从电子邮件中获得序列搜索的结果。b l a s t 包含五个程序和若 干个相应的数据库，分别针对不同的查询序列和要搜索的数据库类型。其中翻译 的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成蛋 白质序列。b l a s t 对序列格式的要求是常见的f a s t a 格式。f a s t a 格式第一 行是描述行，第一个字符必须是“ ”字符；随后的行是序列本身，一般每行序列 不要超过8 0 个字符，回车符不会影响程序对序列连续性的看法。序列由标准的 i u b i u p a c 氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“”号代 表不明长度的空位：在氨基酸序列里允许出现“u ”和“”号；任何数字都应该被去 掉或换成字母( 如，不明核酸用n ”，不明氨基酸用x ) 。此外，对于核酸序列， 除了a 、c 、g 、t 、u 分别代表各种核酸之外，r 代表g 或a ( 嘌呤) ：y 代表 t 或c ( 嘧啶) ；k 代表g 或t ( 带酮基) ；m 代表a 或c ( 带氨基) ；s 代表g 或c ( 强) ；w 代表a 或t ( 弱) ；b 代表g 、t 或c ；d 代表g 、a 或t ：h 代 表a 、c 或t ；v 代表g 、c 或a ：n 代表a 、g 、c 、t 中任意一种。对于氨基 酸序列，除了2 0 种常见氨基酸的标准单字符标识之外，b 代表a s p 或a s n ：u 代表硒代半胱氨酸：z 代表g l u 或g i n ；x 代表任意氨基酸；一，代表翻译结束标 上海大学工学硕士学位论文 2 1 2 多序列比对 顾名思义，多序列比对就是把两条以上可能有系统进化关系的序列进行比对 的方法。目前对多序列比对的研究还在不断前进中，现有的大多数算法都基于渐 进的比对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。进行多 序列比对后可以对比对结果进行进一步处理，例如构建序列模式的p r o f i l e ，将序 列聚类构建分子进化树等等。 目前使用最广泛的多序列比对程序是c l u s t a l w ( 它的p c 版本是 c l u s t a l x ) 。c l u s t a l w 是一种渐进的比对方法，先将多个序列两两比对构 建距离矩阵，反应序列之间两两关系；然后根据距离矩阵计算产生系统进化指导 树，对关系密切的序列进行加权；然后从最紧密的魇条序列开始，逐步引入临近 的序列并不断重新构建比对，直到所有序列都被加入为止。c l u s t a l w 的程序 可以自由使用，在n c b i 的f t p 服务器上可以找到下载的软件包。c l u s t a l w 程序用选项单逐步指导用户进行操作。用户可根据需要选择打分矩阵、设置空位 罚分等。e b i 的主页还提供了基于w e b 的c l u s t a l w 服务，用户可以把序列和 各种要求通过表单提交到服务器上，服务器把计算的结果用e m a i l 返回用户。 c l u s t a l w 对输入序列的格式比较灵活，可以是前面介绍过的f a s t a 格式，还 可以是p i r 、s w i s s - p r o t 、g d e 、c l u s t a l 、g c g m s f 、r s f 等格式。输出格式 也可以选择，有a l n 、g c g 、p h y l i p 和o d e 等，用户可以根据自己的需要选 择合适的输出格式。用c l u s t a l w 得到的多序歹；比对结果中，所有序列排列在 一起，并以特定的符号代表各个位点上残基的保守性，“卑 号表示保守性极高的 残基位点；“”号代表保守性略低的残基位点。 2 1 3 小结 综上所述，基因序列的同源比较是得到新基因后预测其功能的第一步，通过 同源比较来预测基因功能是基于这样一个假设：如果两基因序列有相当的同源 性，那么功能也有相似性。利用同源比较算法，将待检测的新基因序列到d n a 和蛋白质序列库进行同源检索后，便可以得到一系列与新基因同源性较高的基因 上海大学工学硕士学位论文 或片段，这些基因和片段的已知的功能信息就为进一步研究新基因提供了相当的 参考价值和导向。 因此，在人类基因组计划中，对于计算机处理的领域进行些研究是非常有价 值，并能取得长远利益的。其中的同源比较算法则是个很好的切入点，因为其 中对分子生物学，和生物化学相关知识要求的比较少，不需要非常资深的经历，而 主要是针对计算机的数据处理方面的研究。 2 。2 同源比较算法 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个 序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。进一步的比 对是将多个蛋白质或核酸同时进行比较，寻找这些有进化关系的序列之间共同的 保守区域、位点和p r o f i l e ，从而探索导致它们产生共同功能的序列模式。此外， 还可以把蛋白质序列与核酸序列相比来探索核酸序列可能的表达框架；把蛋白质 序列与具有三维结构信息的蛋白质相比，从而获得蛋白质折叠类型的信息。 同源比较分为整体对齐( g l o b a la l i g n m e n t ) 和局部对齐( 1 0 c a la l i g n m e n t ) 两 大类。整体对齐对两个序列全长的相似性做出判断，而局部对齐则着眼于两个序 列是否有局部的序列相似。由于数据库中的许多基因序列是不完整的，而分子生 物学家对序列中的保守顺序比非保守顺序更感兴趣，所以数据库检索的同源比较 算法以局部对齐为主。 目前最流行的可用于局部对齐的算法有：s m i t h w a t e r m a n 算法，f a s t a 算 法和b l a s t 算法。 s m i t h w a t e r m a n 算法是严格的动态规划算