（计算机系统结构专业论文）生物大分子序列比对和蛋白质结构分类算法.pdf

摘要 生物信息学的一个关键问题是理解由染色体中的基因所决定的蛋白质的含义或者功 能。对蛋白质进行分类是解决这个问题的有效途径之一。在保证精确性不会有较大的降 低的前提下，如何提高蛋白质分类算法的计算效率和降低对内存的需求量，一直是生物 信息学领域关注的焦点问题之一。针对这一。问题，文章从算法和计算机体系结构两个方 面入手进行了研究。在分析蛋白质分类算法的基础上，本文把序列联配算法和基于支持 向量机的蛋白质分类算法作为研究的主攻方向。经过三年的研究，在阅读大量文献的基 础上，取得了理想的研究成果。 文章的主要内容包括：蛋白质结构预测与分类的意义；基于l 硼并行计算模型，讨 论了在s m p 多机机群系统上的算法优化与并行；在讨论序列联配算法的基础上，对 s m i t h - w a t e m a r i 算法的并行算法进行改进，并在s n p 多机机群系统上进行优化，提高了 计算性能；在讨论了基于机器学习的算法，主要是支持向量机算法的基础上，提出了结 合片断进化距离和支持向量机的蛋白质分类算法：采用分而治之的思想，利用 s u b o p t i m a l 算法，对s m i t h - w a t e r m a n 算法进行并行，得到了一种可扩展性很好的算法， 硅著地降低了对内存的需求。本文的创新点包括如下几个方面： 1 ) 采用支持向量机算法对蛋白质进行分类，提出了基于片断进化距离的内核。在将序 列转化为向量时，将每条序列与正训练集的“重心”进行比较，而不足与训练集中 的每一条序列进行比较，因此，在计算速度上比s v m - p a i r w i s e 算法有着显著得提 高。同时，序列比较时，不仅仅给出一个最后得分，而是对序列的每一部分都进行 比较，在一定程度上可以保证最后结果的精确性。实验表明，这种方法可以获得很 高的精确度，而计算速度也有很大的提高。在提前计算小片段的距离并储存的情况 下，可以获得0 ( m ) 的加速比。在不采用提前计算的情况下，在对5 4 个家族的蛋白 质进行分类的实验中，平均计算速度是后者的1 0 倍。 2 ) 由s m p 构成的多机集群系统是目前并行领域的主流体系结构之一，基于i t p m 计算模 型，分析了c o s m p s 的体系结构特点，影响性能的主要因素，并且从并行性与存储 访问性能的关系，并行性与通信的关系，以及编程模式对并行性能的影响等方面进 行讨论，给出了在c o s b l p s 系统上对并行计算进行优化的一些原则；分析了纯m p i 和m p i + s m p ( 或o m p ) 制导两种编程模式在性能上的优点与不足。进而提出了在s 即 多机机群系统上的算法并行与优化方法。 3 ) 当前针对s m i t h - w a t e r r a a n 算法的并行化算法，为了能够给出获得最优得分的联配， 在( 至少一个处理器) 中保存整个得分矩阵。因此，在处理非常长的序列，比如长 度以兆计算的序列时，内存的需求量超过了大多数计算机的内存容量。我们对 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 算法确定 生物大分子序列比对和蛋白质结构分类算法 联配的起始和截止位置，然后采用全局联配来获得所需要的联配结果。采用这种方 法，可以有效地减少算法对内存的需求，即使在普通的p c 机群中也可以对两条长 度以兆为单位的序列进行联配。同时，利用在c o s m p s 系统上对算法进行优化的方 法对并行s m i t h w a t e r m a n 算法进行了优化，取得了很好的加速比，提高了计算性 能。 4 ) 采用分而治之的策略，对s m i t h - w a t e r m a n 算法进行并行。我们采用的方法是对联配 的q u e r y 和s u b j e c t 两条序列都分成p 个子序列，然后子序列两两配对，利用 s m i t h - w a t e r m a n 算法进行联配，充分考虑分割序列造成的影响，不仅仅给出最优联 配，同时给出次优联配，称为一组结果。在此基础上，可以采用两种策略利用中间 结果生成最后结果。第一种策略是利用q u e r y 的每一条子序列分别和s u b j e c t 的所 有子序列进行扩展，生成p 组结果，然后再由这p 组结果生成最终结果。第二 种策略是利用s m i t h - w a t e r m a n 算法生成的结果构造有向无环图，在图中进行最长 路径的搜索。 关键词：生物序列联配，蛋白质分类，高性能计算机算法，支持向量机。 p r o t e i ns t r u c t u r ec l a s s i f i c a t i o na l g o r i t h m sb a s e do ns e q u e n c e s i m i l a r i t y l iy u g a n g ( p a r a l l e la l g o r i t h ma n ds y s t e ma r c h i t e c t u r e ) directed b yp r o f e s s o rl i uz h i y o n g a ni m p o r t a n tr e s c a r e ht o p i ci nb i o i n f o r m a t i c si st ou n d e r s t a n dt h em e a n i n g a n df u n c t i o no fe a c hp r o t e i ne n c o d e di nt h eg e n o m e o n eo ft h em o s ts u c c e s s f u l a p p r o a c h e st ot h i sp r o b l e mi sv i ap r o t e i nc l a s s i f i c a t i o n i th a sf o rl o n gp l a y e d ac e n t r a lr o l eo nh o wt oi m p r o v et h ec o m p u t i n ge f f i c i e n c ya n dr e d u c i n gt h em e m o r y r e q u i r e m e n to nt h ec o n d i t i o nt h a tt h er e s u l t sw i l in o tb er e d u c e dt o om u c h f o c u s i n go n t h i sp r o b l e m ，w ec h o o s et h ea g o r i t h ma n dt h ep a r a l l e l c o m p u t e r a r c h i t e c t u r ea st h ec e n t r a lt o p i co fo u rr e s e a r c h t h em a i nc o n t r i b u t i o no ft h i st h e s i si n c l u d e st h ef o l l o w s 1 ) b a s e dc at h es u p p o r tv e c t o rm a c h i n ea l g o r i t h m ，p i e c es e q u e n c ee v o l u t i o n d i s t a n c ek e r n e lh a sb e e np r o p o s e d b e c a u s ee a c hs e q u e n c ei sc o m p a r e dw i t h t h e c e n t e r s e q u e n c eo ft h ef a m i l y ，i n s t e a do fw i t he v e r ys e q u e n c eo f i t ，as i g n i f i c a n ts p e e d u pc a nb ea c h i e v e d m e a n w h i l e ，e a c hp a r to ft h et w o s e q u e n c e si sc o m p a r e da c c o r d i n g l y ，i n s t e a d e do fc o m p a r i n gt h e t w ow h o l e s e q u e n c e s ，t h es e n s i t i v i t yc a nb eg u a r a n t e e d t h er e s u l t ss h o wt h a tt h i s m e t h o di sa1 i t t l em o r ep r e c i s et h a nt h es v t - p a i r w i a em e t h o d ，w h i c hi so n e o ft h em o s ta c c u r a t em e t h o d s m o r eo v e r ，o nt h er e s p e c to fc o m p u t a ti o n a l e f f i c i e n c y ，i ti ss i g n i f i c a n t l yb e t t e rt h a nt h el a t e r ，a n di sa b o u t1 0t i m e s f a s t e rt h a nt h el a t e ri nt h ee x p e r i m e n t so fc l a s s i f y i n g5 4p r o t e i nf a m i l i e s i na v e r a g e 2 ) f o c u s i n g o nt h ep a r a l l e l i s ma n dl o c a l i t yo ft h ea r c h i t e c t u r eo fc o s m p s ，t h e m a i nf a c t o r st h a ti n f l u e n c et h ep e r f o r m a n c ea r ea n a l y z e d ，a n dt h ep r o b l e m s o fh o wt op a r a l l e l i z ea n do p t i m i z ea p p l i c a t i o n sa r ei n v e s t i g a t e d t h em e r i t s a n dd e m e r i t so ft h et w op r o g r a m m i n gm o d e l s ：t h em p im o d ea n dt h e 船i + a m p d i r e c t i v em o d ea r ei n v e s t i g a t e d t h e n ，m e t h o d so fh o wt oi m p r o v e m e n t p e r f o r m a n c ea n dp a r a l l i z ea l g o r i t h m so nt h ec l u s t e ro fs m p sa r ep r o p o s e d 3 ) h i g hp e r f o r m a n c ep a r a l l e l s m i t h w a t e r m a n a l g o r i t h m f o r p r o t e i n c l a s s i f i c a t i o n t h i sm e t h o dc a l lr e d u c et h es p a c ec o m p l e x i t yf r o m0 ( m n ) t o 0 ( m ) w h i l en e a r l yd o u b l et h er u n n i n gt i m e 4 ) u s i n gt h es t r a t e g yo fd i v i d ea n dc o n q u e r ，as c a l a b l ep a r a l l e la l g o r i t h mo f i l i 生物大分子序列比对和蛋白质结构分类算法 t h es m i t h w a t e r m a na l g o r i t h mi sp r o p o s e d ，w h i c hp o r t i o n e dt h ew h o l ed y n a m i c p r o g r a m m i n gm a t r i xa n de a c hp r o c e s s o rh o l d sap a r to fi t u s et h i sm e t h o d ， b e t t e rs e n s i t i v i t yc a nb eo b t a i n e dw i t ht h es a m en u m b e ro fp r o c e s s o r s ：o r m u c hm o r ep r o c e s s o r sc a nb eu s e dw i t ha l m o s tt h es a m es e n s i t i v i t y s o ，i t i sm o r es c a l a b l ea n dt h u sc a nr e d u c et h es p a c er e q u i r e m e n to fe a c hp r o c e s s o r s i g n i f i c m l t l y t h et h e s i s c o n s i s t so f ：1 ) i n t r o d u c t i o n so f t h e s i t u t a t i o na n dt h e s i g n i f i c a n e eo ft h ep r o t e i n c l a s s i f i c a t i o n ：2 ) b a s e d o nt h ei i p mm o d e l ，w ep r o p o s e d h o wt oi m p r o v et h ep e r f o r m a n c eo fa l g o r i t h m so nc l u s t e r so fs m p s ：3 ) s t a r t i n g f r o ms t u d y i n ga l g o r i t h m sb a s e do ns e q u e n c ea li g n m e n t s ，m e t h o d so nh o wt oi m p r o v e t h ed a r a i l e ls m i t h - w a t e r m a na l g o r i t h ma n do i lh o wt oo p t i m i l i z ei t si m p r o v e m e n t s o nc o s m p s ：4 ) a l g o r i t h m so nc o m b i n i n gp i e c ee v o l u t i o n d i s t a n c ea n d s v mi sp r o p o s e d 5 1b a s e do nt h es t r a t e g y o fd i v i d ea n dc o n q u e r ，m e t h o d s t op a r a l l e l t h e s m i t h 唧a t e r m a na l g o r i t h mh a sb e e np r o p o s e d k e y w o r d s ：s e q u e n c ea l i g n m e n t ，o p t i m a l i z ep e r f o r m a n c eo fa l g o r i t h m s ，s u p p o r t v e c t o rm a c h i n e 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谓 的地 方外，论文中不包含其他人已经发表或撰写过的研究成果。与我 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 作者签名：夺王如 日期：午冀为 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以 采用影印、缩印或其它复制手段保存该论文。 作者签名：李互崮 导师签名： 醐伽峙锞二 第一章绪论 2 i 睦纪是生命信息学的世纪，所谓的生物信息学，是利用计算机来处理生物学中的 各种数据，以帮助人们解决生物学中的复杂问题的一门科学。具体地说，生物信息学 贺 0 0 是利用数理和信息科学的观点、理论和方法去研究生命科学中的现象，并且组织和分 析生命科学中提供的呈现指数增艮的数据的一门新兴的交叉学科。研究内容包括遗传物 质的载体d n a 、r n a 及其编码的蛋白质等，研究工具以计算机为主，通过开发各种软件， 对以指数增长的浩如烟海的生物学数据( d n a 、r n a 和蛋白质的序列、结构) 进行收集、 整理、储存、发布、提取、加工、分析和研究，从而达到逐步认识生命的起源、进化、 遗传和发育的本质，破译隐藏在d n a 序列中的遗传语言，揭示人体生理和病理过程的分 子基础的目的，并且通过这样的分析，为人类疾病的预测、诊断、预防和治疗提供最合 理和有效的途径。目前，生物信息学已经成为生物医学、农学、遗传学、细胞生物学等 学科发展的强大动力，也是药物设计、环境监测的重要组成部分。 随着以历时十多年，耗资数十亿美元的人类基因组计划( i l u m a ng e n o m ep r o j e c t ) 贺 0 0 为代表的基因组规模的研究工作的逐步完成，人们已经了解了包括人类在内的多种生 物的全基因组序列的草图，但是对于基因所编码的蛋白质的结构、功能和生理角色的认 识，却远远不够。为了弄清楚在基因组研究过程中产生的海量数据的意义，即基因所编 码的基因产品蛋白质的功能和生理角色，人们加强了对蛋白质的结构与功能的研究， 出现了蛋白质组工程。所谓的蛋白质组工程，是指通过利用蛋白质化学、蛋白质晶体学 和动力学方面的研究来获取有关蛋白质在物理、化学等方面的信息，在此基础上对编码 该蛋白的基因进行有针对性的设计改造，进而通过基因工程等手段将其进行表达和分离 纯化，达到最终将其投入实际应用的目的。这一切，对生物信息学提出了新的要求。 在这一章中，简要地介绍一下生物信息学中的一些基本的背景知识，包括遗传的规 律、d n a 、基n a n 染色体、r n a 、转录和翻译、变异、蛋白质和基因的编码等，为以后的 讨论提供背景知识。然后介绍论文的主要内容以及其中的创新点。 1 1 生物信息学简介 在这一节中，简要地介绍生物信息学中的一些基本概念，详细内容可以参考文献 s m 9 7 ，w 9 5 ，w t o ，郝张0 2 ，贺o o 。 1 1 1 生物信息学基本概念 作为生命的最基本的组成元素，d n a ( d e o x y r i b o n u c l e i ca c i d s ) 分子，r n a 生物大分子序列比对和蛋白质结构分类算法 ( r i b o n u e l e i ea c i d s ) 分子以及蛋白质分子决定了一切生命的外在的形状和内在的功 能。 d n a 是由两条脱氧核糖核苷酸构成的长链相互螺旋缠绕而成。1 9 5 3 年w a t s o n hc r i c k 发现了d n a 分子的结构，通常这一发现被认为标志着现代分子生物学的诞生。每个脱氧 核糖核苷酸包括：磷酸盐( p h o s p h a t e ) 、糖( s u g a r ) 和四种碱基中的一种。这四种碱基 为：腺嘌呤( a d e n i n e ) 、鸟嘌呤( g u a n i n e ) 、胸嘧啶( c y t o s i n e ) 和胸腺嘧啶( t h y m i n e ) ， 依次可表示为a 、g 、c 、t 。d n a 分子呈双螺旋结构，每个单链都是通过磷酸二酯键 ( p h o s p h o d i e s t e rb o n d s ) 连接在起的核苷的聚合体，两个单链通过氢键连结在一起， 这些单链结成碱基对，而每一个碱基对又包括一个嘌呤基( a 或g ) 和一个嘧啶基( c 或 t ) 。 d n a 分子之所以呈双螺旋结构，是由于碱基对之间的互补能力。其配对的规则是：a 只能和t 配对，g 只能和c 配对。由于两对碱基对之间的氢键个数不相同：a 和t 之间有 两个氢键，而c 和g 之间有三个氢键，因此c 和g 的结合力要强于a 和t 的结合力。d n a 的结构如图1 1 所示： 图卜1 a ，d n 的平商结构目图i - i ( 五jd 舰自嗷螺旋结构固 由于构成d n a 分子框架的糖的结构是不对称的，使得d n a 分子具有方向性。糖分子 的5 个碳原子被表示为：c r ，c f ，c ，c 。，c ，每一个糖分子通过连接到链的上游， 通过c ，连接到链的下游，因此通常认为d n a 链的方向是从5 到3 。相互配对的两条d n a 单链的方向是相反的。尽管从携带信息的角度看，d n a 双螺旋中的一条已经足够包含全 部信息，但是，两条链并不是等价的。 细胞分子中还有另外一种核酸r n a ( r i b o n u c l e i ca c i d 核糖核酸) 能够携带遗传信 息。r n a 和d n a 的相同之处在于其碱基也具有配对能力，但r n a 使用尿嘧啶u ( u r a c i l ) 2 第一章绪论 来代替d n a 中的胸腺嘧啶t ( t h y m i n e ) ，即：在r n a 中腺嘌呤a ( a d e n i n e ) 和尿嘧啶u ( o r a e i l ) 配对，鸟嘌呤g ( g u a n i n e ) 和胸嘧啶c ( c y t o s i n e ) 配对。r n a 和d n a 的不 同之处主要是： i ) r n a 是一单链的分子结构，不相邻的核酸分子经常通过碱基的配对能力连接在 1 起，形成各种空间结构。 2 ) d n a 位于细胞核内，而r n a 既可以在细胞核巾，也可以在细胞质中出现。 3 ) d n a 分子的功能是编码遗传信息，而r n a 分子的功能比较广泛。有的充当遗传 物质( 病毒) ，有的是遗传物质的载体，还有的具有特定的功能。 蛋白质分子是由氨基酸依次连接形成的有机高聚物，它负责生命分子中的大部分的 化学反应。条蛋白质序列所含有的氨基酸的数目从几十到几万甚至更多，但是，只有 少数的氨基酸残基负责蛋白质的功能。同时，在蛋白质序列中离得很远的氨基酸在空问 中有可能离得很近，因此蛋白质有十分复杂的三维结构。很短的氨基酸链不能折叠成三 维结构，通常称为多肽，不能称为蛋白质。氨基酸是比核苷酸略小的有机分子，它的中 心碳原子称为。碳( c 。) 。d 碳有四个化学键，一个接羧基( c o o t i ) 、一个接氨基( n i l ，) ， 一个简单地连接氢；第四个键一h 的侧链r ，从一个h 到接近3 0 个原子的基团，形成不同 的氨基酸。尽管自然界中存在的和实验室中合成的氨基酸的种类很多，但是，所有的蛋 白质都是由2 0 种固定的氨基酸组成。这2 0 种氨基酸的名称、缩写，如表卜1 所示。 表卜1 氨基酸的种类与简写 字 缩写名称字母缩写名称 母 aa l aa l a n i n e 丙氨酸 mm e tm e t h i o n i n e 蛋氨酸 c c y sc y s t e i n e半胱氨酸 n a s h h s p a r a g i n e 天冬酰胺酸 d a s pa s p a r t a t e天冬氨酸 pp r o p r 0 1 i n e 脯氨酸 eg l ug l u t a m a t e 谷氨酸 qg l ng l u t a m i n e 谷氨酸盐 p h e n y l a l a n i n e 苯基丙氨 fp h er a r ga r g i n i n e精氨酸 酸 g g l yg l y c i n e氨基乙酸 s s e r s e r i n e 丝氨酸 ht t i s h i s t i d i n e组氨酸 tt h rt b r e o n i n e 苏氨酸 i i l ei s o l e u c i n e 异亮氨酸 vv a l v a l i n e缬氨酸 k l y sl y s i n e赖氨酸 w t r pt r y p t o p h a n 色氨酸 ll e ul e u c i n e 亮氨酸 y t y rt y r o s i n e酪氨酸 r - - h 的甘氨酸，左右对称，没有光学活性，其他1 9 种氨基酸都有左、右之分，也具 有光学活性。氨基酸聚合成大分子时，相邻的氨基和羧基缩水形成作用力很强的肽键， 3 生物大分子序列比对和蛋白质结构分类算法 因此，蛋白质也是有方向的一维链，带氨基的一头称为n 端( n ) ，另一头带羧基称为 c 端( c ) 。 按照外形、在生物组织中的位置和作用，可以把蛋白质分为三类：1 ) 纤维蛋白；2 ) 跨过或者部分镶嵌在磷脂膜中的膜蛋白，可用于实现膜内外的信息交换和物质传递；3 ) 大致为球形的球蛋白。 i i 2 遗传信息的传递 随着分子生物学的深入研究，人们发现除了某些病毒的遗传信息由r n a 分子记载外， 其他所有生物的全部遗传信息都记载在d n a 分子中。这些遗传信息不但决定了生物体个 体的具体形态，而且，还将上一代生物体的特征信息传递给后代，使得后代也表现出相 同或者相似的形态。由于在真核生物体中，记载遗传信息的d n a 位于细胞核中，而决定 生物体形态的蛋白质分子则位于细脆核外的细胞质中，必然存在某种媒介将这些信息从 d n a 分子传递到蛋白质，承担这一信息传递任务的是信使r n a ( m e s s a g er n a ，m r n a ) 。这 称为分子生物学的中心法则，如图卜2 所示。 d n a + 一复制叶d n a j 转录 l e d n a + 一反转录m r n a l 翻译 i 蛋白质酶 l 折叠 功能卜相互作用0 南 图卜2 分子生物学的中心法则 d n a 的自我复制是细胞生命周期的重要事件，这使得细胞核中拥有两份相同的d n a ， 复制完成后，触发细胞分裂成两个，每个拥有一份完整的d n a 。 从d n a 到m r n a 进行复制时，首先利用一种生物酶将d n a 分子的双链结构暂时打开。 由于d n a 分子的每一条链上，都分布着长短不等的包含遗传信息的片断，即“基因”。d n a 到m r n a 的复制不是完全的复制，而是针对某些基因进行。对于一个生物体来说，所有细 胞的d n a 都是相同的，但是，在不同的组织中，复制到m r n a 的基因不同，甚至同一组织 第一章绪论 在生命个体的不同发展阶段，复制到m r n a 的基因可能也不同，所以最后生成的蛋白质有 所不同，体现出不同的结构和功能。 最初，人们以为遗传信息是单向传递的，由d n a 到m r n a ，再到蛋白质。然而，1 9 7 0 年，d b a l t i m o r e 和肌h t e r m i n 等人同时发现，有些r n a 病毒可以将r n a 反转录成d n a ， 并找到了相应的反转录酶。 m r n a 组装完成后，进入细胞质参与生成蛋白质。每条m r n a 生成一条蛋白质，对 应方式是三个核糖核苷酸( 称为密码子) 生成。个氨基酸。尽管有6 4 个不同的密码子， 但是，由于有的氨基酸可以对应几个密码子，同时有的密码子玎i 与任何氨基酸对应。密 码子与氨基酸的对应关系对于任何生物都是一样的，因此，也被称为通用遗传编码，如 表卜2 所示。 新生的肽链必须折叠成唯一的、特定的三维结构，才能发挥生物活性，成为真正的 蛋白质。 表卜2 氨基酸和密码子的对应关系表 f i r s tt h i r d p o s i t i o ns e c o n dp o s i t i o np o s i t i o n ( 5 e n d )( 3 e n d ) ucag p h es e r t y rc y s u p h es e r t y rc y s c u l e us e r s t o ps t o p a l e us e t s t o pt r p g l e up r oh i s a r g u l e up r oh i s a r g c c l e up r og l n a r g a l e up r og l n a r g g i l et h ra s ns e tu i l et h ra s hs e rc a i l et h r l y sa r g a m e tt h r l y sa r g g v a la l a a s pg l y u v a la l a a s pg l y c g v a la l ag l u g l y a v a la l ag l u g l y g 5 生物丈分子序列比对和蛋自厦结构分类算法 1 2 生物信息学中的任务 生物信息学的任务是从事对基因组研究的相关生物信息的获取、加工、储存、分配、 分析和解释。或者说，是对海量的生物信息数据的收集、整理与服务并从中发现新的规 律。 目前生物信息学领域，大部分人都把注意力集中在基因组、蛋白质组、蛋白质结构 以及与之相结合的药物设计上，具体如下： 1 ) 新基因的发现与鉴定 新基因的发现是生物信息学领域的一个非常重要的问题，包括通过计算分析从e s t ( e x p r e s s e ds e q u e n c et a g s ) 序列库中拼接出完整的新基因编码区，以及通过计算分析 从基因组d n a 序列中确定新的基因编码区，到目前为止，已经有很多分析方法用于耨基 因的发现，如根据编码区具有的独特的序列特征、根据编码区与非编码区在碱基组成上 的差异、根据高维分布的统计方法、根据神经网络方法、根据分形方法等。使用基因组 信息学的方法通过超大规模计算是发现新基因的重要手段，可以说大部分新基因是靠理 论方法预测出来的。随着人类基因组计划的完成，发现薪基因的任务显得尤其重要。 2 ) 非蛋白编码区生物学意义的分析 图l 一3 非编码区示意图 近年来对完整基因组的研究发现，所有生物的基因组中都存在有一定的非编码区， 所占比例从1 0 到9 5 以上不等。尽管非蛋白编码区的生物学意义目前还不是很清楚， 从生物进化的观点来看，既然随着生物体功能的完善和复杂化，非编码区域有着明显增 加的趋势，说明这部分序列必定具有重要的生物功能。一般认为，它们与基因在四维时 空的表达、调控有关。深入了解这些非编码区序列的功能是当前生物信息学领域面临的 一个真正的挑战。 3 ) 大规模基因功能表达谱的分析 随着基因组规模测序任务的完成，我们已经获得了包括人类在内的一些生物的完整基因 图谱，但是仍然存在着一系列由上述数据所不能说明的问题，例如：基因表达的产物是 6 第一章绪论 否出现与何时出现，基因表达产物的浓度是多少；是否存在翻译后的修饰过程，若存在 是如何修饰的等等。这些问题的实质是：我们虽然知道了基因，知道了核酸序列，但我 们不知道它们是如何发挥功能的，或者说它们是如何在特定的时间、空间进行基因表达 的，表达的量有多少。虽然生物体内的所有细胞的基因组是相同的，但是，在不同的组 织中表达基因的数目有着很大的差别，有的组织中约有上万个，有的组织中只有几十或 几百个基因表达。不确切知道每种组织中表达基因的数日，以及每个基因的表达量，就 无法从分子水平上了解这一组织在生命活动中的功能。研究工作还表明，同组织在个 体的不同生长发育阶段所表达的基因的种类、数量也是不同的，有些基因是在幼年时期 表达的，有些是中年阶段表达的，有些要到老年时期才会表达；如果不考虑伴随着生物 的生长发育，基因表达状况的不同，就无法确切地说明生命的过程。特别是现在关于干 细胞功能表达谱的研究，不仅与医疗实践关系密切，而且为发育生物学、进化生物学的 研究提供了极好的模型。因此不少科学家认为基因组研究应当进入一个内函更丰富、更 深刻的阶段。这阶段的核心是获得基因的功能表达谱。按物理学家的观点是应将存在 于人类基因组的静态的基因图谱，向时间、空间维上展开。 4 ) 基因组演化与物种演化 目前，在分子演化方面已经取得了许多重要的成就，但是不能仅仅依靠某些基因或 者分子的演化现象来阐明物种整体的演化历史。例如，智人与黑猩猩之间虽然有着显著 的差异，但是二者有9 8 一9 9 的结构基因和蛋白质是相同的，差别就在于组织方式的不 同。物种演化历史中，基因组整体的组织方式有若非常重要的作用，这是因为基因组是 物种所有遗传信息的储藏库，从根本上决定着物种个体的生长发育。因此，从基因组整 体结构组织和整体功能调节网络出发，结合相应的生理现象，对基因组和物种的演化进 行研究，将是揭示物种真实演化历史的有效途径。 5 ) 蛋白质空间结构的测定 d n a 序列的钡4 序速度，远远超过测定蛋白质三维结构的速度，而且随着基因组规模 测序工作的完成，已知氨基酸组成的蛋白质序列的数量在以指数形式递增，仅仅依靠实 验方法来测定蛋白质的结构远远满足不了人们的需要。因此，利用计算的手段从蛋白质 序列甚至由d n a 读框翻译出的氨基酸序列预测蛋白质可能的结构，就成为追切的任务。 目前，利用计算手段来预测蛋白质结构的主要手段分为：“基于知识”的方法和“基于物 理的方法。 那些明显依赖于由已知结构的序列信息得到相关参数的方法被称为“基于知识”的， 与之形成鲜明对比的是“基于物理的方法”，这一类方法通过构成元素的相互作用来解释 或者预测蛋白质的结构。目前，给定一条蛋白质序列，通过基于知识的方法来预测要比 使用基于物理的方法更好。随着实验结构基因组的出现，基于比较或者同源模建的方法 生物大分子序列比对叩蛋白质结构分类算法 在预测迅速增长的序列数据库中的序列结构方面，显得越来越重要。 5 ) 新药设计 用反向生物学原理，根据人类基因序列数据，经过生物信息学分析、高通量基因表 达、高通量功能筛选和体内外药效研究开发得到新的候选药物。蛋白质的空间结构模拟 和药物设计已有多年的历史，随着人类基因组研究的飞速发展，寻找人类基因的碱基序 列事业在取得不断的进展，同时，随着结构生物学的发展，相当数量的蛋白质以及一些 核酸、多糖的三维结构已经获得了精确的测定。在这种情况下，根据生物大分子结构的 知识，有针对性地设计药物成为热点。实际上，生物信息学不仅可以提供生物大分子空 间结构的信息，还能提供电子结构的信息，如能级、表面电荷分布、分子轨道相互作用 以及动力学行为的信息。 总之，生物信息学包括：对基因组序列信息进行分析，找到基因组序列中代表蛋白 质和rn a 基因的编码区；阐明基因组中大量存在的非编码区信息的实质，破译隐藏在 dn a 序列中的遗传密码；在此基础上，归纳、整理并分析与基因组遗传信息的释放及 其调控相关的转录谱和蛋白质谱的数据，从而认识代谢、发育、分化、进化的规律。 除此之外，生物信息学的一项更重要的任务是如何运用数理理论成果，对生物体进 行完整系统的描述，以便使人类能够从一个更明确的角度、以一种更易于操作的方式， 来认识和控制自身以及其他生命体。 1 3 论文研究的主要内容和创新点 本文围绕提高蛋白质分类与结构预测算法的计算速度、减少内存需求这一中心议题， 从体系结构特点，算法的并行，蛋白质序列空间到向量空间的转化等方面，寻求改进性 能的方法与途径。 论文首先讨论了蛋白质结构预测与分类的意义和现状，并且介绍了相关的蛋白质结 构与分类的数据库。 其次，由于生物信息学中的算法普遍具有计算量大、存储量大的特点，提高计算速 度，降低内存需求量显得尤其重要。计算速度的提高离不开对体系结构的清晰的认识， 基于t t p m 并行计算模型，分析了目前并行处理领域的主流结构之一的由对称多处理机构 成的机群系统，研究了在这种体系结构中的算法并行与优化方法。 第三，讨论了基于序列联配的算法。序列联配算法在生物信息学中有着非常重要的 作用，应用于生物信息学的各个领域。文章从两条序列的全局、局部联配算法的复杂度， 得分矩阵的含义以及选择，空位罚分，联配结果的统计学意义等方面进行介绍相关算法。 针对s m i t h - w a t e r m a n 算法，给出了分块行流水算法的改进算法，进步降低了内存需求， 可以在由p c 构成的机群上进行两条长度以m 为单位的序列的联配。并且，针对这一方法， r 第一章绪论 在由对称多处理机构成的机群系统卜进行优化，获得了超线性的加速比。 第四，两条序列联配的动态规划算法的并行。在基于序列联配的算法当中， s m i t h w a t e r m a n 算法被认为是最好的，但是它的计算复杂度和空问复杂度都很高，影响 丁它的应用，人们从启发示和并行两个方面来降低它对时间和存储的要求。其中，p s w d c 算法就是在s m i t h w a t e r m a n 算法的基础上发展起来的，我们在p s w - d c 算法的基础上， 对其进行改进，提高结果的灵敏度并且在c o s m p s 系统上进行优化。 第五，利用机器学习算法对蛋白质进行分类时既利用了正样本的信息，又利用了负 样本的信息，因此会有相当好的精确度。文章在分析了现有的基于机器学习，特别是基于 支持向量机的蛋白质分类算法基础上，提出了基于片断进化距离的蛋白质分类算法。 最后，给出了结论以及下一步的研究工作。本文的内容是在研究蛋白质分类算法的 基础上形成的。但是有关算法的应用并不仅仅局限于蛋白质分类。 本文的主要创新点包括如下： 1 ) 基于h p m 计算模型，分析了s m p 构成的多机集群系统( c o s m p s ) 的体系结构特点， 影响性能的主要因素，并且从并行性与存储访问性能的关系，并行性与通信的关系， 以及编程模式对并行性能的影响等方面进行讨论，给出了在c o s t s 系统上对并行计 算进行优化的一些原则；分析了纯m p i 和m p i + s i 船( 或o m p ) 制导两种编程模式在性能 卜的优点与不足。进而提出了在s 日) 多机机群系统上的算法并行与优化方法。 2 ) 提出了结台片断进化距离和支持向量机算法的蛋白质分类算法。在将序列转化为向 量时，将每条序列与正训练集的“重心”进行比较，而不是与训练集中的每一条序 列进行比较，因此，在计算速度上比s v m p a i r w i s e 算法有着显著得提高。同时，序 列比较时，不仅仅给出一个最后得分，而是对序列的每一部分都进行比较，可以保 证最后结果的精确度。实验表明，这种方法的精确度比目前同类算法中精确度最高 的s v m - p a i r w i s e 算法略强。在提前计算小片段的距离并储存的情况下，可以获得 0 ( m ) 的加速比。在不采用提前计算的情况下，在对5 4 个家族的蛋白质进行分类的实 验中，平均计算速度是后者的1 0 倍。 3 ) 当前针对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 算 法采用分块的行流水算法进行并行，并且采用两次s m i t h - w a t e r m a n 算法确定联配的 起始和截止位置，然后采用全局联配来获得最终的联配结果方法减少内存需求。采 用这种方法，可以有效地减少内存需求，即使在普通的p c 机群中也可以进行两条长 度以兆为单位的序列的联配。同时，利用在c o s l 口s 系统上对算法进行优化的方法对 s m i t h - w a t e r m a n 算法进行了优化与并行，取得了很好的加速比，提高了计算性能。 生物大分子序列比对和蛋白质结构分类算法 4 ) 由于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 算法进行并行。我们采用的方法是对 联配的q u e r y 和s u b j e c t 两条序列都分成p 个子序列，然后子序列两两配对，利 用s m i t h - w a t e r m a n 算法进行联配，充分考虑序列分割造成的影响，不仅仅给出虽优 联配，同时给出次优联配，称为一组结果。在此基础上，可以采用两种策略利用中 间结果生成最后结果。第一种策略是利用q u e r y 的每一一条子序列分别和s u b j e c t 的 所有子序歹d 进行扩展，生成p 组部分结果，然后再由这p 组部分结果生成最终结 果。第二种策略是利用s m i t h w a t e r m a n 算法生成的结果构造有向无环图，在图中进 行最长路径的搜索。这一算法具有更好的可扩展性，可以利用更多的处理器，从而 进一步降低了单个处理器的内存需求。 1 4 论文的结构 本文的结构安排如下，第二章重点介绍了蛋白质结构分类与预测的现状，以及对高 性能计算的