（计算机软件与理论专业论文）基于频率变换和最小边界矩形的高效motif发现算法.pdf

东北大学硕士学位论文 摘要 基于频率变换和最小边界矩形的高效m o t i f 发现算法 摘要 d n a 序列中的m o t i f 在生命科学研究中通常用作基因信号的标志，此外m o t i f 对于 蛋白质转录规律的解析和药物靶点的定位都有很高的应用价值，因此m o t i f 发现问题已 经成为当前生物信息学中最有挑战性的问题之一。虽然关于m o t i f 发现算法的研究已经 进行了很多年，并且取得很多比较满意的成果，但是这个领域的研究还存在很多没有很 好解决的问题。本文介绍了一种用于发现m o t i f 的数学模型c l i q u e ，并且提出了一种利 用频率变换和最小边界矩形( m b r ) 技术的高效m o t i f 发现算法e d a m 算法。e d a m 算法与以往的m o t i f 发现算法所不同的是它将d n a 序列转换成频率向量，并且基于频 率向量的性质在c l i q u e 发现过程之前对频率向量进行过滤，从而削减了搜索空间，提高 了运行效率。e d a m 算法通过逐步扩展c l i q u e 的方式，搜索表达m o t i f 的c l i q u e 。算法 主要分成：d n a 样本序列的频率变换过程，m b r c l i q u e 的过滤过程以及m o t i f 的发现 过程三部分。e d a m 算法的主要优点是利用作为序列之间的频率距离近似估计它们之间 的h a m m i n g 距离，并且使用基于频率距离定义的m b r c l i q u e 进行过滤，从而使得e d a m 算法具有很好的过滤功能模块。实验结果表明本文算法的运行时间较以往o ( n 2 ) 的利用 图论中边搜索相似子序列的算法有很大的提高。 关键词：m o t i f ；c l i q u e ；最小边界矩形；频率向量；生物信息学 东北欠学硕士学位论文a b s _ r a e t a ne f f i c i e n tm o t i f d i s c o v e r ya l g o r i t h m w i t h f r e q u e n c yt r a n s f o r m a t i o na n dm b r a bs t r a c t m o t i f si nd n as e q u e n c e sa r eg e n e r a l l yu s e da st h eg e n es i g n a l si nb i o l o g ya n df i n d i n g m o t i f si nd n a s e q u e n c e sh a si m p o r t a n ta p p l i c a t i o n si nd e c i p h e r i n gt r a n s c r i p t i o n a lr e g u l a t o r y m e c h a n i s m sa n dd r u gt a r g e ti d e n t i f i c a t i o n t h e r e b y , m o t i fd i s c o v e r yp r o b l e mh a sb e c a m eo n e o ft h em o s tc h a l l e n g i n gp r o b l e mi nb i o - i n f o r m a t i c s a l t h o l l g ht h er e s e a r c ho nm o t i fd i s c o v e r y p r o b l e mh a sb e e nm a n yy e a r s ，a n dt h er e s e a r c hh a sg a i n e ds e v e r a la c h i e v e m e n t s ，m a n y t r o u b l e s o m ep r o b l e m sa r es t i l ll e f tf o ru s i nt h i sp a p e r , w ep r o p o s ea ne f f i c i e n ta l g o r i t h m e d a mf o rf i n d i n gm o t i f sb a s e do nf r e q u e n c yt r a n s f o r m a t i o na n dm i n i m u mb o u n d i n g r e c t a n g l e ( m b r ) t e c h n i q u e s t h ed i f f e r e n c e sb e t w e e ne d a ma n df o r m e ra l g o r i t h m sa r et h a t e d a mt r a n s f o r m st h es u b s e q u e n c e si n t of r e q u e n c yv e c t o r sa n dh a saf i l t r a t i o nb e f o r es e a r c h f o rm o t i f s i nt h i sm e t h o d ，t h es e a r c h i n gs p a c ei sm u c hs m a l l e rt h a no t h e ra l g o r i t h m s ，a n di t p e r f o r m sb e t t e rt h a no t h e r s i tw o r k si nt h r e ep h a s e s ，f r e q u e n c yt r a n s f o n n a t i o n ，m b r c l i q t e s e a r c h i n ga n dm o t i fd i s c o v e r y i nf i e q u e n c yt m n s f o n n a t i o n ，e d a md i v i d e st h es a m p l e s e q u e n c e si n t oas e to fs u b s e q u e n c e sb ys l i d i n gw i n d o w s ，t h e nt r a n s f o r m st h e mt of r e q u e n c y v e c t o r sw h i c ha r es t o r e di nm b r s m b r - c l i q u es e a r c h i n g ，b a s e do nt h e 矗e q u e n c yd i s t a n c e t h e o r e m se d a ms e a r c h e sf o rm b r c l i q u e su s e df o rm o t i fd i s c o v e r y i nm o t i fd i s c o v e r y , e d a md i s c o v e r sl a r g e rc l i q u e sb y e x t e n d i n gs m a l l e rc l i q u e sw i t ht h e i rn e i g h b o r s t o a c c e l e r a t et h ec l i q u ed i s c o v e r y - , w ep r o p o s ear a n g eq u e r yf a c i l i t yt oa v o i dt m n e c e s s a r y c o m p u t a t i o n sf o rc l i q u ee x t e n s i o n t h ee x p e r i m e n t a lr e s u l t si l l u s t r a t ef l a a te d a mw e l ls o l v e s t h et u t o r i n gt i m eb o t t l e n e c ko ft h em o t i fd i s c o v e r yp r o b l e mi nl a r g ed n ad a t a b a s e k e yw o r d s ：m o t i f ；c l i q u e ；m b r ；f r e q u e n c yv e c t o r ；b i o i n f o r m a t i c s i ij 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 弓【i 琢 日 期：如口己 。7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文第一章绪论 第一章绪论 2 l 世纪是生命科学的时代，也是信息时代。随着人类基因组计划的实施，有关核酸、 蛋白质的序列和结构数据呈指数增长。面对巨大而复杂的数据，运用计算机管理数据、 控制误差、加速分析过程势在必行。人类基因组计划在测序过程中产生的海量数据更是 离不开超级计算机，需要利用高性能计算机来“解读”。科学家们积极运用数学、计算机 科学和生物学的各种工具，来阐明和理解基因组学获得的大量数据中所包含的生物学意 义。从2 0 世纪8 0 年代末开始，一门新兴学科生物信息学应运而生。近年来，计算机 和i n t e r n e t 的发展更是为生物信息的传递提供了硬件基础和便利。 1 1 生物信息学 以核酸、蛋白质等生物大分子数据库为主要对象，以数学、信息学、计算机科学为 主要手段，以计算机硬件、软件和计算机网络为主要工具，对浩如烟海的原始数据进行 存储、管理、注释、加工，使之成为具有明确生物意义的生物信息。并通过对生物信息 的查询、搜索、比较、分析，从中获取基因编码、基因调控、核酸和蛋白质结构功能及 其相互关系等理性知j 。在大量信息和知识的基础上，探索生命起源、生物进化以及细 胞、器官和个体的发生、发育、病变、衰亡等生命科学中重大问题，搞清它们的基本规 律和时空联系，建立“生物学周期表”。 生物信息学作为一个新兴的学科领域，它的研究对象就是最近几年随着生物测序技 术的进步而得到的大量的生物序列数据，如d n a 、r n a 、蛋白质等多种生物序列。这 些数据是相互之间紧密联系的，例如，不管是基因的表达还是蛋白质的功能，通常都是 多个基因多个蛋白质相互协调相互作用的结果。所以对生物数据的研究所涉及的技术必 然涵盖了计算机与信息科学，数理科学，系统与控制科学等多个先进的学科1 2 l 。 1 2 生物信息学的发展状况 通俗来讲，基因组是由四种不同的脱氧核糖核苷酸( a 、t 。c 和g ) 按照特定的编码 规则串联成的脱氧核糖核苷酸串( d n a ) ，其中蕴藏着生物体中所有的结构信息和控制 信息，因此，基因组可以说就是生物体内的控制中心，其中的功能单位可以转录为核糖 核苷酸序列( r n a ) ，有的就以r n a 的形式发挥生物功能，有的则进一步被翻译成为各 种蛋白质而行使生物体构建和生命调控功能。因此，基因组是一本完整地讲述人体构造 和运转情况的指南，有了它，就可以揭开有关人体生长、发育、衰老、患病和死亡的秘 密，因而危害人类健康的5 0 0 0 多种遗传病以及与遗传密切相关的癌症、心血管疾病、 东北大学硕士学位论文第一章绪论 关节炎、糖尿病、高血压、阿尔茨海默氏病以及多发性硬化症和精神病等，就都可以得 到诊断和治疗。 人类基因组计划就是要测出人类基因组的全部脱氧核糖核苷酸序列( 估计其中编码 有约十万多个蛋白质基因) ，进而弄清楚其中所有功能单位的组织结构形式以及调节机 制，并绘制成直观图谱，该计划实现之后更深入的工作就是要弄清楚基因组所编码的所 有蛋白质的表达情况，最终达到从整体系统水平上认识人体构造与功能并帮助制定有效 治疗策略和开发有效治疗药物的目的。除此以外，还要对其它几个属于不同生物进化期 的模式生物的基因组进行测序，如酵母、果蝇、蠕虫和小鼠等，利用这些模式生物可以 进行很多在人体内不可能进行的实验研究，是我们了解人类基因组功能的重要工具。所 有这些工作都涉及到大量数据的处理工作，而且数据量也在以科学史上前所未有的高速 度增长着，所有这些情况表明，生物学已不再是仅仅基于试验观察的科学，仅靠传统的 研究手段是无济于事的，理论和计算将越来越发挥巨大作用，数学、物理、计算机科学 将日益渗透到生物学研究中来，海量的数据必须通过生物信息学的手段进行收集、分析 和整理后，才能成为有用的信息和知识，才能再加以传播应用，也就是说，只有经过生 物信息学手段的分析处理，我们才能获得对基因组的正确理解，因此可以说生物信息学 兴盛于人类基因组计划，囚为人类基因组计划首次为生物信息学创造了施展身手的巨大 空间；当然，生物信息学并不局限于人类基因组工程，它已经深入到生命科学的方方面 面。 1 2 1 生物信息学的国外发展状况 国外一直非常重视生物信息学的发展，各种专业研究机构和公司如雨后春笋般涌现 出来，生物科技公司和制药工业内部的生物信息学部门的数量也与日俱增。尽管在许多 大学和研究机构已经各自成立了自己的生物信息学部门或中心，1 9 9 9 年6 月3 日，美国 国家卫生研究院( n i h ) 的专家委员会还是建议。迅速在大学和研究机构中建立2 0 个生 物计算中心，给予每个中心每年8 0 0 万美元的支持，从事有关研究和人才培养，该建议 可能在2 0 0 1 年开始实施。 近来，英国鉴于国内对生物信息学专业人才日益迫切的需求，所有主要的研究资助 机构医学研究委员会( m r c ，m e d i c a lr e a 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 ga n d p h y s i c a ls c i e n c e s r e s e a r c h c o u n c i l ) 、粒子物理和天文学研究委员会( p p a r c ，p a r t i c l ea n da s t r o n o m yr e s e a r c h c 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 并于1 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 ) 。 从数据分析技术的角度来讲，早在1 9 6 2 年，z u c k e r k a n d l 和p a u l i n g 就将序列变异 分析与其演化关系联系起来，从而开辟了分子演化的崭新研究领域：1 9 6 4 年，d a v i e s 开创了蛋白质结构预测的研究；1 9 7 0 年，n e e d l e m a n 和w u n s c h 发表了广受重视的两序 列比较算法：1 9 7 4 年，r a t h e r 首先运用理论方法对分子遗传调控系统进行处理分析； 1 9 7 5 年，p i p a s 和m c m a h o n 首先提出运用计算机技术预测r n a 二级结构；随着1 9 7 6 年之后大量生物学数据分析技术的涌现，s c i e n c e 于1 9 8 0 年第2 0 9 卷就已经发表了关于 计算分子生物学的综述；正如我们现在所看到的那样，在八九十年代，生物学数据分析 技术在国外更是获得了突飞猛进的发展。 从专业出版业来看，由于没有专业领域专门的期：州，起初的专业文献都散落在各种 其他领域的期刊中，到了1 9 7 0 年，出现了c o m p u t e r m e t h o d sa n d p r o g r a m s i n b i o m e d i c i n e 这本相关期刊，到1 9 8 5 年4 月，就有了第一种生物信息学专业期干c o m p u t e r a p p l i c a t i o n i n t h e b i o s c i e n c e s ；现在，我们可以看到的专业期刊已经很多了，包括书面期 刊和网上期刊两种，如b i o i n f o r m a t i c s ( f o r m e r l yc o m p u t e ra p p l i c a t i o n s i nt h e b i o s c i e n c e s ) 、a c t ab i o t h e o r e t i c a 、b i o l n f o r m a t i c st e c h n o l o g y s y s t e m s 、b i o i n f o r m n e w s l e t t e r 、b r i e f i n g si nb i o i n f o r m a t i c s 和j o u r n a lo fc o m p u t a t i o n a lb i o l o g y 等。 从网络资源来看，国外互联网上的生物信息学网点非常繁多，大到代表国家级研究 机构的、d , n 代表专业实验室的都有，大型机构的网点一般提供相关新闻、数据库服务 和软件在线服务，小型科研机构一般是介绍自己的研究成果，有的还提供自己设计的算 法的在线服务，总体而言，基本都是面向生物信息学专业人士，各种分析方法虽然很全 面，但却分散在不同的网点，分析结果也需要专业人士来解读。 目前，绝大部分的核酸和蛋白质数据库由美国、欧洲和日本的3 家数据库系统产生； 他们共同组成了d d b j ，e m b l g e n b a n k 国际核酸序列数据库，每天交换数据，同步更新。 其他一些国家，如德国、法国、意大利、瑞士、澳大利亚、丹麦和以色列等，在分享网 络共享资源的同时，也分别建有自己的生物信息学机构、二级或更高级的具有各自特色 的专业数据库以及自己的分析技术，服务于本国生物( 医学) 研究和开发，有些服务向 东北大学硕士学位论文第一章绪论 全世界开放。 1 2 2 生物信息学的国内发展状况 国内生物信息学研究近年来发展的步伐很快，而且国内对这个的领域的研究也越来 越重视。如北京大学生物信息学中心、华大基因组信息学研究中心、中国科学院上海生 命科学院生物信息中心、中国科学院生物物理所、中国科学院上海生化细胞所是我国生 物信息学研究和应用技术研发的重点单位。国家自然科学基金委已经在生物化学、生物 物理学与生物医学工程学学科下设立了生物信息学项目，这些项目被列入生命科学部优 先资助的研究项目。国家8 6 3 计划特别设立了生物信息技术主题，从国家需求的层面上 推动我国生物信息技术的大力发展。在一些著名院士和教授的带领下，在各自领域取得 了一定成绩，有的在国际上还占有一席之地，如北京大学的罗静初和顾孝诚教授在生物 信息学网站建设方面、中科院生物物理所的陈润生研究员在e s t 序列拼接方面以及在基 因组演化方面、天津大学的张春霆院士在d n a 序列的几何学分析方面、中科院理论物 理所郝柏林院士、清华大学的李衍达院士和孙之荣教授、内蒙古大学的罗辽复教授、上 海的丁达夫教授等等；北京大学于1 9 9 7 年3 月成立了生物信息学中心，中科院上海生 命科学研究院也于2 0 0 0 年3 月成立了生物信息学中心，分别维护着国内两个专业水平 相对较高的生物信息学网站，但从全国总体上来看与国际水平差距很大。一方面，国内 生物( 医药) 科学研究与开发对生物信息学研究和服务的需求市场非常广阔，另一方面， 真正开展生物信息学具体研究和服务的机构或公司却相对较少，仅有的几家科研机构主 要开展生物信息学理论研究，声称提供生物信息学服务的公司所提供的服务也仅局限于 简单的计算机辅助分子生物学实验设计，而且服务体系并不完善。 随着中国加入世界贸易组织，我国与国外在生物信息学领域的交流和合作逐步增 多，例如由美国s u n 公司和中科院基因组生物信息学中心暨北京华大基因研究中心联合 创办的生物信息学中心在京宣告成立。2 0 0 0 年5 月，在提前完成国际人类基因组计划1 项目的“工作框架图”后，华大基因与丹麦农业部共同开展家猪基因组的研究；8 月， 又与美国最大的基因组研究中心结成了姐妹中心。与此同时，s u n 即宣布北京基因组研 究中一5 , ( b g i ) 与德拉威生技研究中心( d b i ) 获选成为s u nc e n t e r so f e x c e l l e n c e ( c 0 e ) 。此两 个研究中心因其在运算生物学的领导地位，结合其他机构共同开发生物科技的潜力而获 选为s u nc o e 。d b i 所以获选成为高性能运算生物学领域的s u nc o e ，来自于先进的蛋 白质结构、生物路径模拟、电脑侦测序列重复与s n p 、以及整体基因组的比较。未来， 两个研究中心将正式加入s u n 的学术研究机构社群，开发先进技术以从事突破性的研发 工作。除了b g i 和d b i 以外，s u n 日前亦已完成在维吉尼亚生技研究中心和威斯康辛麦 迪逊大学设立运算生物学c o e 。此外，生物信息研究一直是国家计委密切关注和重点支 东北走学硕士学位论文第一章绪论 全世界开放。 1 2 2 生物信息学的国内发展状况 国内生物信息学研究近年来发展的步伐很快，而且国内对这个的领域的研究也越来 越重视。如北京大学生物信息学中心、华大基因组信息学研究中心、中国科学院上海生 命科学院生物信息中心、中国科学院生物物理所、中国科学院上海生化细胞所是我国生 物信息学研究和应用技术研发的重点单位。国家自然科学基金委已经在生物化学、生物 物理学与生物医学工程学学科下设立了生物信息学项目，这些项目被列入生命科学部优 先资助的研究项目。国家8 6 3 计划特别设立了生物信息技术主题，从国家需求的层面上 推动我国生物信息技术的大力发展。在一些著名院士和教授的带领下，在各自领域取得 了一定成绩，有的在国际上还占有一席之地，如北京大学的罗静初和顾孝诚教授在生物 信息学网站建设方面、中科院生物物理所的陈润生研究员在e s t 序列拼接方面以及在基 因组演化方面、天津大学的张春霆院士在d n a 序列的几何学分析方而、中科院理论物 理所郝柏林院士、清华大学的李衍达院士和孙之荣教授、内蒙古大学的罗辽复教授、上 海的丁达夫教授等等；北京大学于1 9 9 7 年3 月成立了生物信息学中心，中科院上海生 命科学研究院也于2 0 0 0 年3 月成立了生物信息学中心，分别维护着国内两个专业水平 相对较高的生物信息学网站，但从全国总体上来看与国际水平差距很大。一方面，国内 生物( 医药) 科学研究与开发对生物信息学研究和服务的需求市场非常广阔，另一方面， 真正开展生物信息学具体研究和服务的机构或公司却相对较少，仅有的几家科研机构主 要开展生物信息学理论研究，声称提供生物信息学服务的公司所提供的服务也仅局限于 简单的计算机辅助分子生物学实验设计，而且服务体系并不完善。 随着中国加入世界贸易组织，我国与国外存生物信息学领域的交流和合作逐步增 多，例如由美国s u n 公司和中科院基因组生物信息学中心暨北京华大基因研究中心联合 创办的生物信息学中心在京宣告成立。2 0 0 0 年5 月，在提前完成国际人类基因组计划1 项目的“工作框架图”后，华人基因与丹麦农业部共同开展家猪基因组的研究；8 月， 又与美国最大的基因组研究中心结成了姐妹中心。与此同时，s u n 即宣布北京基因组研 究中心( b g i ) 与德拉威生按研究中，心( d 1 3 1 ) 获选成为s u nc e n t e r so f e x c e l l e n c e ( c o e ) 。此两 个研究中心因其在运算生物学的领导地位，结合其他机构共同外发生物科技的潜力而获 选为s u n c o e 。d b i 所以获选成为高性能运算生物学领域的s u n c o e ，来自于先进的蛋 白质结构、生物路径模拟、电脑侦测序列重复与s n p 、以及整体基因组的比较。未来， 两个研究中心将正式加入s u n 的学术研究机构社群，开发先进技术以从事突破性的研发 工作，除了b g i 和d b i 以外，s u nf i 前亦已完成在维吉尼皿生技研究中心和威斯康辛麦 迪逊大学设立运算生物学c o e 。此外，生物信息研究一直是国家计委密切关注和重点支 迪逊大学设立运算生物学c o e 。此外，生物信息研究一直是国家计委密切关注和重点支 东北大学硕士学位论文第一章绪论 持的重要领域。对中国科学院今后在生物信息学领域的有关研究和科研基础设施建设， 国家发展计划委员会将在中国科学院建设“生物信息系统国家研究中心”，形成有国际竞 争能力的基因组学、蛋白质组学和生物信息学的整体技术平台。2 1 世纪是生命科学大发 展的时代。以人类基因组计划为序幕的生物信息学研究，是全面认识生命及其过程的重 要手段。我国要必然要参与由此引发的生物信息革命，从根本上改变生命科学和生物产 业的思维方式和研究体系，成为新世纪国际竞争中举足轻重的国家。 1 3 生物信息学当前的研究方向 生物信息学的主要目的是揭示生命进化的奥秘，它以分析生物大分子序列为手段， 目的就是要全面认识在生物遗传中起决定作用的基因，以及和生物体功能有着密切关系 的蛋白质。从而在本质上认识生物体的活动和进化规律，如生物生长、发育、代谢、分 化、进化、遗传等规律。根据当前生命科学，计算机科学及其它相关科学技术的发展状 况，目前在生物信息学领域中的研究热点主要有以下几个方向： ( 1 ) 蛋白质组学研究：基因组对生命体的整体控制必须通过它所表达的全部蛋白质来 执行，由于基因芯片技术只能反映从基因组到r n a 的转录水平上的表达情况，由于从 r n a 到蛋白质还有许多中间环节的影响，因此仅凭基因芯片技术我们还不能最终掌握 生物功能具体执行者蛋白质的整体表达状况；因此近几年在发展基因芯片的同时， 人们也发展了一套研究基因组所有蛋白质产物表达情况蛋白质组研究技术。此项技 术实现并不是困扰生物信息学发展的主要问题，最重要的就是如何运用生物信息学理论 方法去分析所得到的巨量数据，从中还原出生命运转和调控的整体系统的分子机制。分 为蛋白质序列预测和蛋白质功能预测。 图1 1 蛋白质的一级结构图，二级结构图及三级结构图的比较 f i g1 1 t h ec o m p a r i s o n b e t w e e n p r o t e i n s f i r s t g o n s t r u c t i o n s e c o n dc o n s t r u c t i o na n dt h i r dc o n s t r u c t i o n 5 东北大学硕士学位论文第一章绪论 蛋白质是由多种氨基酸按一定顺序排列形成的，蛋白质序列又分为一级结构序列， 二级结构序列，三级结构序列，在三级结构的基础上最近又提出了四级结构的概念。一 级结构是一个平面的结构，他只包含构成蛋白质的氨基酸的排列顺序，二级结构和三级 结构是空间立体结构。蛋白质序列的预测就是由已知的一级结构来预测其相应的高级结 构。目前多种计算机和数学统计方法都用于蛋白质结构预测，如神经元网络，支持向量 机等。蛋白质的功能预测是和蛋白质的空间结构紧密相连的，试验表明，特定的蛋白质 空间结构会产生蛋白质的特定作用。这些问题都是蛋白质处理中的主要工作内容。 ( 2 ) 基因组学研究：所谓基因就是d n a 分子上具有遗传效应的特定核苷酸序列的总 称，是具有遗传效应的d n a 分子片段。每个基因具有自身的遗传密码。基因虽然只有 小小的一段，却有着重要的功能。它不仅可以通过复制把遗传信息传递给下一代，还可 以使遗传信息得到表达。蛋白质由2 0 种不同的氨基酸通过肽键连接而成。各种氨基酸 在线形链中的顺序，决定了这种分子的三维结构，也决定了它的功能。比如不同人种之 间基因组的差别仅为o 1 ；人猿间差别约为1 。但他们表型问的差异十分显著。因 此比较的分析d n a 和蛋白质是解开其中奥秘的重要手段。这方面的研究包括基因比对， 基因发现，基因组中非编码区的研究，在基因组水平上研究生物进化等。基因序列比对 就是对两个以上的基因序列进行比较，找出其相似性。基因比对是很多基因研究工作的 基础。如经过比对发现的某个基因组的相似特征可以用来进行基因发现和识别等。基因 发现是在基因比对的基础上，对特定的基因序列( 尚不存在) 计算它的出现概率，如果 出现概率达到一定的阈值，我们就认为这个基因序列可能存在于自然界中，并在以后的 基因测序中重点来发现这些基因。对非编码区的研究主要是由于非编码序列与基因的表 达调控有关，具有重要的生物功能。因此寻找这些区域的编码特征、信息调节与表达规 律也是基因处理的重要问题。在基因组水平对生物进化进行研究，主要是由于近几年来 生物学界对基因序列差异和生物进化之阳j 的关系越来越重视，目前已经发现同一种群基 于不同分子序列所重构出的进化树可能不同。这些问题都深深的吸引着生物信息学家的 关注。 ( 3 ) 生物信息学在经济生活的应用：蛋白的空间结构模拟和药物设计已有二三十年的 历史。对蛋白质空间结构的充分了解，可以指导如何选定药物作用的靶位，对药物分子 的设计也有指导作用。目前主要研究的是大分子( 如蛋白质) 的结构和功能之间的关系， 药物分子与大分子之间的结合方式，关键性基因的致病机制和生物分子在指定细胞的分 布和位点等。随着这些研究结果的发现，大量的潜在的致病基因将被发现，多种针对许 多新的生物靶点的药物将被研制出来。此外，很多疾病与基因突变或基因多态有关，有 人估计与癌症相关的原癌基因约有1 0 0 0 个，抑癌基因约有1 0 0 个。约有6 0 0 0 种以上的 人类疾患与各种人类基因的变化相关联。更多的疾病是环境( 包括致病微生物) 与人类 东北大学硕士学位论文第一章绪论 基因( 基因产物) 相互作用的结果。随着人类基因组计划的深入，当我们知道了人类全 部基因在染色体上的位置、它们的序列特征( 包括s n p s ) 以及它们表达规律和产物( r n a 和蛋白质) 特征以后，人们就可以有效地判定各种疾忠的分子机制，进而发展合适的诊 断和治疗手段。为此，有两项生物信息学工作是重要的：一是构建与疾病相关的人类基 因信息数据库( 包括s n p 数据库) ，二是发展有效地分析基因分型数据的生物信息学算 法，特别是将s n p 数据与疾病和致病因素相关的计算方法。另外一个生物信息学在当 今社会的重要应用意义在于帮助人类了解生物进化的过程。进化论研究的核心是描述生 物进化的历史( 系统进化树) 和探索进化过程的机制。自本世纪中叶以来，随着生物学 的不断发展，进化论的研究也进入了分子水平。当前分子进化的研究已是进化论研究的 重要手段，并建立了一套依赖于核酸、蛋白质序列信息的理论方法。近年来，随着序列 数据的大量增加，对序列差异和进化关系的争论也越来越激烈。不少的研究结果并不支 持分子钟的假设，对垂直进化和水平演化之间关系的讨论正逐渐引起人们的重视。一个 使用整个基因组的信息的复杂，丰满的进化模式将启示我们彻底了解进化的规律。 【4 ) 基因组就是细胞内遗传信息的携带者d n a 的总体。基因组中不同的区域具 有不同的功能，基因组结构是指不同功能区域在整个d n a 分子中的分布情况。人类基 因组包含着人类的全部遗传信息，所以搞清楚核苷酸排列顺序无疑将成为人类破解遗传 之谜的第一步。人类只有一个基因组，大约包含5 一1 0 万个基因，由大约3 0 亿个碱基 对组成，分布在细胞核的2 3 对染色体中。为了破解这个人类自身的秘密，1 9 8 6 年，著 名生物学家、诺贝尔奖获得者雷纳托杜尔贝科( r e n a t o d u l b e e c o ) 在科学杂志上率先 提出“人类基因组计划”( h u m a n o e n o m e p r o j e c t ，简称h g p ) 1 3 1 ，旨在阐明人类基因组3 0 亿个碱基对的序列，发现所有人类基因并搞清其在染色体上的位置，破译人类全部遗传 信息，使人类第一次在分子水平上全面地认识自我。1 9 9 0 年1 0 月，美国政府决定出资 3 0 亿美元正式启动“人类基因组计划”，预期到2 0 0 5 年得到人体的全部基因序列。随后 研究其相互作用和基因功能，从而揭开人类全部遗传规律。“人类基因组计划”启动以后， 英国、法国、德国、中国和e l 本迅速跟进，纷纷加入到此项意义重大的研究中。在各国 科学家的努力下，整个工程进展i l i o n 。我国于1 9 9 9 年7 月在国际人类基因组注册，得 到完成人类3 号染色体短臂上一个约含有3 0 0 0 万碱基的区域的测序任务。我国因此成 为参与这一研究计划的唯一发展中国家。我国负责的测序区域约占人类整个基因组的1 ，简称“1 项目”1 4 1 。我国能够参与这一伟大计划，说明我国在这一领域掌握了一定的 技术，而且对基因的研究有了一定的成绩。2 0 0 0 年4 月，中国科学家按照国际人类基因 组计划的部署，完成了1 人类基因组的工作框架图。2 0 0 3 年4 月1 4f i ，美国联邦国 家人类基因组研究项目负责人弗朗西斯柯林斯博士在华盛顿隆重宣布，人类基因组序列 图绘制成功，人类基因组计划的所有目标全部实现。由美、英、i ? 1 、法、德和中国科学 东北大学硕士学位论文第一章绪论 家经过1 3 年努力共同绘制完成了人类基因组序列图，在人类揭示生命奥秘、认识自我 的漫漫长路上又迈出了重要的一步。“人类基因组计划”被誉为生命科学的“阿波罗登月 计划”，是人类有史以来最为伟大的世纪工程垆】。这一计划的实现将对整个人类产生巨大 影响。但是，人类基因组测试的完成不是科学研究的终点，而是新科学的起点。为了理 解它，给它做出全面的注释，科学家们需要找到里面包含的所有基因和调控这些基因的 序列。还有关于这些基因的表达是如何受哪些因素调控的? 他们的表达产物蛋白质 是如何形成一定的结构并互相识别或装配进而发挥特定的生物功能的? 测序完成之后， 科学家们纷纷转向对基因功能的研究，生物学将进入一个崭新的时代后基因组时 代。所谓的“后基因组计划”则是对基因功能的研究，即“功能基因组学”。“后基因组计划” 的研究内容，就是对基因组的功能进行探索，寻找功能基因及其编码的蛋白质，测定蛋 白质的结构，破译第二套遗传密码，实现多学科交叉，应用其它学科的知识来解决生物 学问题等等。要彻底地破译人类基因组中所包含的全部信息仍然需要进行数十年的研究 和分析。到时候，人类的许多疾病都可以在分子水平上寻找致病原因以及治疗方法。这 将给医药行业带来很大的挑战，新药的开发原则将针对疾病的潜在致病原因。“人类基 因组计划”的顺利完成把我们带入了基因的世纪，我们正在向着解开生命的秘密的目标 前进。 1 4 生物信息学的意义与影晌 生物信息学不仅仅是- - 1 3 科学学科，它更是一种重要的研究开发工具。生物信息学 是一门研究生物和生物相关系统中信息内容物和信息流向的综合系统科学，只有通过生 物信息学的计算处理，我们才能从众多分散的生物学观测数据中获得对生命运行机制的 详细和系统的理解。它是今后几乎进行所有生物( 医药) 研究开发所必需的舵手和动力 机，只有基于生物信息学通过对大量已有数据资料的分析处理所提供的理论指导和分 析，我们才能选择正确的研发方向，同样，只有选择正确的生物信息学分析方法和手段， 我们才能正确处理和评价新的观测数据并得到准确的结论。而且，由于生物信息学是生 物科学与计算科学、物理学、化学和计算机网络技术等密切结合的交叉性学科，使其具 有非常强的专业性，生物信息学的发展将会对生命科学带来革命性的变革【6 】。它的成果 不仅对相关基础学科起巨大的推动作用，而且还将对农业、医药、卫生、食品等产业产 生巨大的影响。同时，我们也不应该忽视生物信息学中存在的问题。例如当代社会的很 多的社会伦理问题，如果处理不好，它就会像一个潘多拉盒子一样对整个人类社会构成 威胁。诸如试管婴儿、人工受精乃至克隆人等都将引发一系列的伦理、法律和社会问题。 如果将来基因和蛋白质的测试会像现在的血常规化验一样快捷方便，那么个人的基因组 中包含的隐私，如含有什么致病基因或对某种疾病的易感基因，将会很容易被检查出来， 一旦结果泄漏出去，被检对象就可能在就业、婚姻、保险等多方面受到歧视，社会发展 8 东北夫擘硕士学位论丈第一章绪论 将会陷入混乱。如果没有相应的法律加以保护，整个生物信息学将会岌岌可危。 总之，当前是生物信息学研究的一个有活力的新时代。不少科学家还说它是人类基 因组研究的收获时代，它不仅将赋予人们各种基础研究的重要成果，也会带来巨大的经 济效益和社会效益。 东北大学硕士学位论文第二章m o t i f 发现算法的相关工作 第二章m o t i f 发现算法的相关工作 在本章中，我们将详细地介绍m o t i f 在生物医学上的发现，认识，及应用的过程， 在此之后，本章将阐述m o t i f 在生物医学研究中的作用，意义和m o t i f 在社会生活中的 应用价值和产生的影响。m o t i f 发现问题及其所属的序列分析领域是生物信息学中传统， 具有挑战性的科研领域之一，本章将介绍序列分析当前的发展状况及基本的概念和技术 手段。在完整的介绍m o t i f 发现问题的相关知识之后，为了更清晰，更准确地理解m o t i f 的概念，本章将从数学角度定义m o t i f 问题。在本章的最后部分，我们将介绍m o t i f 发 现问题已经得到的研究成果，广为接受的算法。本章将详细地介绍利用图沦中c l i q u e 的 概念，发现m o t i f 的算法w i n n o w e r 算法。 2 1m o t i f 及其生物意义 在基因表达的过程中，蛋白质的合成主要分为转录和转译两个阶段。在蛋白质的转 录阶段中，转录因子通常在相应的转录区域中具有相同的长度( 大约8 - - 2 0 b p s ) 和很高 的相似性，因此把转录因子的d n a 序列称作m o t i f ( 基序) 。因为基因功能区域中的序 列一旦发生突变将直接破坏生物组织的功能，所以功能区域中的序列都含有m o t i f ，而 非功能区域中的序列并不限制突变的发生，所以很少包含m o t i f 。根据m o t i f 在d n a 序 列的特点，他经常用来表示基因的信号区域，从而解析蛋白质转录规律和定位药物的靶 点。 m o t i f 所表达的基因信号是在1 9 7 0 年h a m i l t o ns m i t h 在发现h i n di i 酶之后，第一次 注意到的。发现基因信号中的重复出现区域在1 9 7 0 年还不是一件很容易的事，之后 h a m i l t o ns m i 1 连续发表了两篇关于h i n d i i 酶的文章，一篇关于酶的提纯。另外一篇 关于寻找酶的公认基因信号区域。但是3 0 多年过去了，尽管对这个课题进行了很多研 究，基因信号的发现问题还远远没有解决。多数在d n a 序列中的基因信号由于太复杂， 至今还找不到好的用于识别它们的模型和可靠的算法1 7 1 。当前发现的m o t i f 都有一些规 律，他们一般是短小的，有些是已经退化的，常常出现在所有样本序列中。它们通常具 有独一无二的模式，代表一些独特的生理功能。这些功能区域一旦发生突变会影响生理 规则，会对组织产生十分有害影响，所以这些功能区域被限制包含有m o t i f 另一方面 非功能区域并不限制突变的发生，所以非功能区内域聚积了大量的基因突变垆，9 ，1 。 在通常情况下，弱的d n a ( a p a t t e m m a t c h i n ga l g o r i t h m f o rc o d o n o p t i m i z a t i o n ) 信号 是嵌入到已经了解的富含功能区域的一组d n a 样本序列中。这不等于样本序列集的每 条序列都明确包含这些功能模式，比如限定蛋白质的d n a 信号可能会含有与它等价的 东北大学硕士学位论文第二章m o t i f 发现算法的相关工作 核苷酸序列。对于生物信息学，这个问题可以称作为发掘隐藏在样本中的信号区域。 随着很多组织模型的全序列被全部解析出来，比较地序列分析技术成为了重要的了 解基因组功能的手段i “】。全序列分析技术是对所有序列全局分析的- - f v 方法，所以用它 发掘基因序列内部关系会更准确合理，因此比较地全序列分析技术成为现在最广泛使用 的用于序列分析的手段。为了阐明在进化过程中物种基因发生突变的规律，我们可以匹 配基因序列的内部区域，并且使用多序列比对的方法