（计算机软件与理论专业论文）改进的系统发育谱方法在蛋白质功能预测中的应用.pdf

摘要 后基因组时代的到来，生物信息学的研究重心日益从基因组测序工作转移到对已测 序基因组的功能进行注释。传统的基于同源性的注释方法由于自身存在的缺陷在精确度 方面已经不能满足人们的需要。非同源性的功能注释方法渐渐受到人们的重视。有别于 同源性方法中对基因或蛋白质问相似性的考虑，非同源性方法则是根据基因或蛋白质之 间的进化上的相关性来预测它们之间的功能关联。在众多非同源性方法中，系统发育谱 方法是应用得最为广泛的一种，同时也是最具研究价值的一种。 系统发育谱方法最早是由p e l l e 酊n i 等人于1 9 9 9 年提出的。该方法从刚一提出就引 起人们的广泛关注。在此后的几年时间里，众多研究学者对这种方法做出了不同程度的 改进。这些改进包括了系统发育谱的三个步骤，即参照基因组的选择、系统发育谱的构 建以及谱的相似性分析。尽管如此，该方法到目前为止还有许多不足之处，如参照基因 组的选取还没有一定的标准，对相似谱的聚类也还没有有效地利用现有的经典聚类算 法。针对这些不足，对系统发育谱算法提出了两点改进：一是为构造基于权重的系统发 育谱，从而间接减少了对于参照基因组选择的过分依赖；二是在对构造好的发育谱进行 相似性分析时，结合使用两种应用最为广泛的经典聚类算法一层次聚类算法和k 均值 聚类算法。通过两种方法的取长补短来达到更好的聚类效果。 关键字：参照基因组；系统发育谱：权值；层次聚类：k 均值聚类 a b s t r a c t w i t ht h ea r r i v a lo fp o s t - g e n o m ee r a ，t h ef o c i l so fb i o m f 0 皿a t i c si i l c r e a s i n 酉yh a sb e e n t m s f e 皿c df 两mt l l eg e n o m es e q u e n c i l l gt og e n o m ef u n c t i o n a l 蛐o t a t i o n t h et m d i t i o n a l m e t h o dt h a tb a s e do nh o m o l o g yc a nn o tm e e tp e o p l e sn e e d si nt h ea c c u r a c yb e c a u s e0 ft h e i r o w ns h o n c o m i n g s w h i l en o n - h o m o l o g o u sm e t h o d s 孕a d u a l l yb e c o m em o r c 觚dm o r e i m p o r t a n t b e i n gd i 能rf 如mh o m o l o g o u sm e t h o d s ，n o n - h o m o l o g o u sm e t h o d sp r e d i c tt h e f u n c t i o n0 fg e n e s0 rp r o t e i n sa c c o r d i n gt ot 1 1 e i re v 0 1 u t i o nr e l e v a n c e a m o n gs 0m 孤y n o n - h o m o l 0 9 0 u sm e t h o d s ，p h y l o g e n e t i cp r o f i l em e t h o di st h em o s tw i d e l ya p p l i e do n ef o ri t s 孕e a tr e s e a r c hv a l u e p h y l o g e n e t i cp r o f i l em e t h o da r o u s e dp e o p l e sa t t e n t i o n 弱s o o n 嬲i tw 弱p r o p o s e db y p e l l e 伊i n ji n1 9 9 9 ，锄dm 趾yr e s e a r c h e r sd i dal o to fw o r kt 0i m p r o v eo ni ti nt h en e x tf e w y e a 娼t h ei n l p r 0 v e m e n t so np h y l o g e n e t i cp r o f i l em e t h o di n l p l e m e n t e dm a i n l yo nt h et h r e e s t e p si i l d u d i n gt h es e l e c t i o no ft h er e f e r e n c cg e n o m e ，t h ef o u n d a t i o no fp h y l o g e n e t i cp r o f i l e 趾dt h e 觚a l y s i so ft h ep r o 丘l e s s i 1 n a r i t y 1 1 1 ep h y l o g e n e t i cp r o f i l em e t h o ds t n lh 硒m a n y d e f i c i e n c i e s ，f o re x 锄p l e ，t h e r ci sal a c ko fc e n a i ns t 柚d a r d0 nt h es e l e c t i o no fr e f e r e n c c g e n o m e ，t h ec l 弱s i c a ld u s t e r i n ga 1 9 0 r i t mh a sn o ty e tb e e nu s e di nt h ec l u s t e r i n go fs i i l l i l a r p r o f i l e se 施c t i v e l y t 0t h e s ed e f i c i e n d e s ，觚oi m p r 0 v e m e n t s 伽p h y l o g e n e t i cp r o f i l em e t h o d w e r ep r o p o s e di nt h j sp a p e r f i r s t ，c 0 n s t m c t i n gw e i g h tb a s e dp h y l o g e n e t i cp r o f i l e ，w h i c h d e c r e a s e dt h ee x c e s s i v ed 印e n d e n c co nt h es e l e c t i o no fr e f e r e n c eg e n o m e s e c 0 n d ，j o i n i n gt h e 1 l i e r a r c h i c a ld u s t e 血ga l g o r i t 陆锄dk - m e 加sd u s t e r i n ga l g o r i t h mw h i c ha r ct l l em o s t p o p u l a rc l a s s i c a lc l u s t e r i n ga l g o r i 岫t 0o b t a i nb e t t e rd u s t e rr e s u l t k e yw o r d s ：r e f e r e n c eg e n o m e ；p h y l o g e n e t i cp r o f i l e ；w e i g i l tv a l u e ；h i e r a r c l l i c a ld u s t e 血g a 1 9 0 r i t h m ；k - m e a n sa l g o r i t h m i i 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名： 丕绚奎摘 日期： q 墨：竺 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：翌蓟查墒 日 期：鱼墨：6 ：9 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 写磊i 差 ( ) 孑6 仁 电话： 邮编： 东北师范大学硕士学位论文 己i 吉 丁i口 生物信息学是用数理和信息科学的观点、理论和方法去研究生命现象、组织和分析 呈现指数增长的生物学数据的一门学科。生物信息学以计算机、网络为工具，采用数 学和信息科学的理论、方法和技术去研究生物大分子，其研究重点落实在核酸和蛋白质 两个方面，包括它们的序列、结构和功能。生物信息学以基因组d n a 序列信息分析作为 出发点，破译遗传语言，认识遗传信息的组织规律，辨别隐藏在d n a 序列中的基因，掌 握基因调控信息，对蛋白质空间结构进行模拟和预测，依据蛋白质结构和功能的关系进 行药物分子设计n ，。 揭示生物分子数据的内涵是生物信息学的长远目标。生物分子数据之间存在着复杂 的联系，这些数据中蕴含着丰富的生物学知识和生物学规律。目前生物信息学的主要任 务是研究生物分子数据的获取、存储和查询，发展数据分析方法。主要包括三个方面： ( 1 ) 收集和管理生物分子数据为信息分析和数据挖掘打下基础；( 2 ) 进行数据处理和 分析，通过发现数据之间的关系，认识数据的本质进而上升为生物学知识；( 3 ) 开发 分析工具和实用软件，借机具体的问题，为具体的生物信息学应用服务。 随着一系列基因组计划的相继开展，尤其是人类基因组计划的顺利实施，人们步入 后基因组时代。生物信息学的重心也从之前的对基因组的测序过渡到揭示隐藏在这些基 因组中过得生物学功能。对功能预测的方法大致分为两种畸】【7 】：基于同源性的功能注释 方法和基于非同源性的功能注释方法。有别于同源性方法中对基因或蛋白质间相似性的 考虑，非同源性方法则是根据基因或蛋白质之间的进化上的相关性来预测它们之间的功 能关联。由于这种基于进化的观点能够更真实准确的反映基因或蛋白质之间的功能关 联，因此非同源性方法逐渐受到人们的重视。在众多非同源性方法中，系统发育谱方法 是应用最为广泛的一种，同时也是最有研究价值的一种。它最早是由p e l l e 面n i 等人提 出的，在他提出的几年时间里，众多研究学者对该方法进行了不同程度的改进，也都取 得了不错的效果，目前该方法已经在原核生物的基因组功能注释中、蛋白质相互作用中 得到了应用，并取得了较好的效果。 东北师范大学硕士学位论文 第一章绪论 1 1 研究意义 生物信息学是一门以分子生物学数据库为主要对象，以数学技术和计算机技术为主 要手段，以计算机、应用软件和计算机网络为主要工具的，通过对海量的原始序列数据 进行收集、存储、管理、分析、注释、加工和处理而获取生物学新知识的新型交叉学科 n 】。它是当今生命科学和自然科学的重大前沿领域之一，其研究范畴是以基因组d n a 序 列的信息分析作为出发点，分析基因组结构，寻找或发现新基因，分析基因调控信息， 并在此基础上研究基因的功能，研究基因的产物即蛋白质，模拟和预测蛋白质的空间结 构，分析蛋白质的性质，最终为基于靶分子结构的药物分子设计和蛋白质分子改性设计 提供依据。具体来说，就是从核酸和蛋白质序列出发，分析序列中隐含的结构功能的生 物信息。大规模测序工具的相继问世使得大量的分子生物数据快速涌现出来。这些原始 的序列数据中包含大量的未被注释的功能信息，对基因组功能的注释已经成为基因组时 代的一个重大挑战，其算法设计和实现极为重要，已经广泛受到生物、计算机、数学等 相关领域科学家的关注，同时也带动了医学、化学、数学、计算机、网络等一大批相关 科学和产业的发展。 随着人类基因组计划的实施和推进，生命科学领域的研究步入了后基因组时代。 在后基因组时代，生命科学的主要研究对象之一便是功能基因组学，其中包括结构基因 组研究和蛋白质组研究等。尽管现在已有很多物种的基因组的测序工作已经完成，但在 这些基因组中通常有一半以上蛋白质的生物学功能是未知的。因此，在未来的几年内， 人们研究的重点必将越来越多的从序列研究转到基因组功能方面的研究。 1 2 研究目的 基因组计划的实施刺激了测序工具的快速发展，伴随这些高性能测序工具出现的是 大通量的生物分子序列数据。如何对这些新产生的序列数据进行快速而准确的生物学功 能注释，进一步研究疾病产生的机理，从而为疾病的诊断和治疗提供依据，责无旁贷得 成为后基因组学时代的中心任务。 基因组功能注释就是对基因组中序列的功能进行预测注解，其研究对象是基因组序 列，而具体的研究内容可以分为三个层次脚：1 、基因组组成元素的识别，即预测基因 组的全部编码区或称“开放阅读框架( o p e nr e a d i n gf r 锄eo r f ) ；2 、注释所有0 r f 产物 的功能；3 、基因之间相互作用及比较基因组学研究。其中注释所有o r f 产物的功能是 当前最受关注的一部分，同时它也是本文所要重点讨论的核心问题。在对基因组中o r f 产物进行功能注释时，大体思路是这样的：对于已有实验证据的基因产物只需将功能描 2 东北师范大学硕士学位论文 述与相应的基因相连即可。而对于无实验证据的基因，从生物信息学的角度出发，目前 主要有两大类方法可用于大通量的基因组功能注释工作，即基于同源性的基因功能注释 方法和基于非同源性的基因功能注释方法。 基于同源性的方法和基于非同源性的方法的不同之处在于是否从进化的角度来分 析蛋白质之间的功能相关性。顾名思义，同源性方法是从蛋白质的同源性分析入手，考 察两条蛋白质之间存在着的同源关系，如果两条蛋白质是同源的那么认为它们具有相似 或相同的功能。但是这种方法也存在着问题，比如对于孤儿基因，就无法预测它们的功 能。此外，同源性方法的预测精确度并不高，已经不能满足人们的需求。因此，近些年 来，人们逐渐对非同源性方法重视起来。非同源性方法是从分析两条蛋白质之间的共进 化性来分析它们之间的功能关联。由于这种方法是着眼整个进化过程进行分析的，因此 往往预测出的结果比较可靠。 在非同源性方法中，系统发育谱方法是被人们研究最多的一种。这种方法已经在原 核生物的基因功能预测中得到了广泛的应用，并且取得了令人满意的效果。但是由于种 种原因，在真核生物中的应用并没有多大的成效，这一方面是由于真核生物自身组成结 构记为复杂，另一方面是因为系统发育谱方法虽然在近几年的时间里得到了快速的发展 和不同程度的改进，但是仍存在许多问题。 本文主要针对现有系统发育谱方法存在的问题进行分析，并提出了两处改进，力求 使算法的整体性能得到进一步的提高。 1 3 国内外研究现状 目前，在基因组功能注释研究领域，主要有两大类预测方法：基于同源性的方法和 基于非同源性的方法。在基于同源性的方法中，对功能的预测是通过比较蛋白质之间的 相似性口1 来完成的，这些相似性主要包含蛋白质的序列，域结构，甚至是蛋白质的二级 或三级结构。随着人们对测试结果要求的不断提高，基于同源性功能注释方法的缺点就 不断暴露出来：比如结果的精确度不高，孤儿基因无法使用该方法进行功能预测等等。 由于同源性方法本身存在的不足，研究者越来越关注非同源性方法的研究。 非同源性方法是通过蛋白质的属性，而不是与其他蛋白质的相似性来对蛋白质进行 功能注释的。在诸多非同源性方法中，系统发育谱方法是目前在这一领域上应用的比较 成熟的方法之一。系统发育谱方法的基本思想是选择一定数量的全测序基因组，通过分 析目前蛋白质在这些基因组中的共进化模式来判断蛋白质之间是否存在着功能上的相 关性。系统发育谱法主要分为三个步骤：选取参照基因组集合、构造系统发育谱以及选 取相似度评价函数进行分析。目前，针对系统发育谱方法的这三个步骤都有学者做过专 门的研究。在参照基因组集合的选择方面，s u n 等人给出了基于进化关系_ 的参照基因组 的选择方法【1 2 ，1 8 ，1 9 】。这种方法通过考察参照基因组之间以及参照基因组和目标基因组之 间在进化上的距离来选择合适的基因组作为参照基因组。s u n 等人是最早提出一种系统 的方法来讨论这一问题的。但是这种方法也存在一种问题，那就是，随着测序基因组数 3 东北师范大学硕士学位论文 目的不断增加，考察这些基因组之间的进化关系将是一件巨大的工程，况且，找到一个 适合做参照基因组的合适的进化距离还需要重复的实验来完成，随着基因组数目的增 多，这同样是不可想象的。 系统发育谱的构造方法主要有两种：离散型的构造方法和连续性的构造方法。这两 种方法的思路是一致的，即通过分析基因蛋白质在物种间的共进化模式( 即同时存在 或不存在于某一物种中) 来判断这两条基因蛋白质是否存在功能上的相关性。具体的 做法是选择一系列全测序基因组作为参照基因组，并考察目标蛋白质在这些基因组中的 分布模式。不同之处仅在于离散型系统发育谱中的元素只包含0 和1 两个数字，而连续 性系统发育谱则将谱中的元素映射成o 到1 之间的连续数字。 在构造好系统发育谱之后，就需要对发育谱的相似性进行分析。现有的系统发育谱 的分析思路主要基本上都是一致的：即首先使用样本数据反复进行实验来确定阈值，然 后选择一个合适的距离公式或是相似性函数来计算两条发育谱之间的相似度，最后将这 些值和事先确定的阈值进行比较，距离小于( 或相似性大于) 给定阈值的发育谱对应的 蛋白质被认为具有功能上的相关性。由此可见，对系统发育谱的相似性分析主要是通过 实验方法来完成的，期间并没有将经典的算法如聚类算法应用其中。 1 4 本文的主要工作 系统发育谱方法是目前最常用的基因组功能注释的方法，同时也是被研究的最多的 一种方法，并已在原核生物基因组的功能注释中得到应用。由于系统发育谱法大致可以 分为三个主要的步骤，即参照基因组的选择、构造系统发育谱以及选取相似度评价函数 进行谱的相似性分析，所以国内外的研究人员在三个方面都有所研究。 在选择参照基因组集合时，本文主要对s u n n 2 1 吼1 9 1 等人的最新研究方法进行参考分 析，该方法的宗旨是选取进化距离较远的数目相当的物种作为参照基因组。经过大量的 实验，他们得出的结论是：要选择在进化上相距较远且数目适当的物种作为参照基因组 集合n 2 1 。 选好了参照基因组集合，接下来就要对每条待检测的蛋白质构建系统发育谱，最初 的系统发育谱是由p e l l e 酉陆等人随1 提出的，它是一种由0 和1 组成的二进制的离散谱： o 定义为某蛋白质的同源蛋白在给定的参照基因组中不存在；1 定义为某蛋白质的同源 蛋白在给定的参照基因组中存在。后来d a t e n 叫等人对离散谱进行了改造，从而提出了 连续的系统发育谱的构造，连续谱是将上述的最高匹配比值做相应的转化，转化成为o 和1 之间的数字，最终用这些数字构建谱。各自的实验证明，无论是离散谱还是连续谱， 都取得了较高的准确性和敏感性。然而，正如我们上面所说的，这些方法大多是基于实 验来完成的，因此，虽说实验结果还算令人满意，但是却大大限制了该方法的效率，。并 且随着待注释基因组的复杂度的增加，如此烦琐的操作几乎是不可行的。 在为待注释的蛋白质构建了系统发育谱之后，接下来就要对这些谱进行聚类。现有 的方法呻9 1 乏1 钔在对这一部分进行分析的时候，都是选择一个距离函数或是相似性函数来 4 东北师范大学硕士学位论文 计算任意两个蛋白质之间的相似程度，并且通过样本数据事先确定一个判断相似度的阈 值。但是，这个阈值并不具有通用性，也就是说，当使用不同的基因组做实验的时候， 需要选择不同的阈值。然而实际上，对蛋白质之间的相似性无需进行定量的分析，而只 需定性分析即可。 鉴于现有系统发育谱方法存在的一系列弊端和潜在的问题，本文在继承系统发育谱 ( 离散谱) 方法的基本思路的基础上，针对其存在的不足，对该方法进行了两处改进： 一是提出了一种基于权重的系统发育谱方法。该方法根据蛋白质在物种间的分布， 为不同的参照基因组设置了不同的权值。权值大的基因组被认为包含更多的关于目标蛋 白质的进化信息；反之，权值小的则包含较少的进化信息。这样一来，就减少了系统发 育谱的构建对于基因组选取的过度依赖，从而在一定程度上提高了系统发育谱方法整体 的效率。 二是使用经典的聚类算法对系统发育谱的相似性进行分析。本文分别使用k m e a n s 聚类方法、层次聚类方法及两者结合使用的聚类方法对蛋白质的系统发育谱进行聚类， 并对实验结果进行了比较和分析，最终显示本文方法在准确度上明显高于前两种方法。 1 5 本文组织结构 全文分为五章，主要内容如下： 第一章概述了本文的研究意义、研究目的、国内外研究现状、主要工作以及组织结 构等。 第二章详细介绍了研究的背景知识及研究现状，包括蛋白质功能注释方法以及经典 聚类算法的相关概念和应用。 第三章首先介绍了系统发育谱方法的基本原理，然后介绍现有方法对系统发育谱的 构造，在对现有方法进行分析后提出了构造基于权重的系统发育谱的构造。 第四章首先分析了现有系统发育谱方法对构造的系统发育谱的相似性分析，分析其 中存在的弊端，提出了使用聚类算法对系统发育谱进行相似性分析的思想，并给出了详 细的算法描述。 第五章主要是对实验过程的描述和分析以及算法性能的评价。为了验证本文算法的 有效性，还将本文的算法和现有的系统发育谱算法进行了比较，结果显示本文的算法具 有更好的性能。论文最后对全文进行了总结并指出了下一步的工作。 5 东北师范大学硕士学位论文 第二章背景知识简介 弟一早罔京刘以幅】丌 2 1 蛋白质功能注释方法介绍 生物体的基因组能够提供构建机体所需的全部信息，但其本身在建造机体时不担任 任何主动角色。而蛋白质则有的参与形成组织的部分结构，有的被赋予构建组织结构的 能力，有的负责知性生命必需的新陈代谢反应。可以说，蛋白质是生命活动的物质寄出， 几乎一切生命现象都要通过蛋白质的结构与功能而体现出来。因此，在分子生物学中， 深刻阐明蛋白质的结构和功能，是探索生命奥秘的最基本任务n 2 1 。 蛋白质的功能主要有以下几个方面：( 1 ) 酶的催化作用；( 2 ) 物质运载和储存 作用；( 3 ) 营养存储作用；( 4 ) 运动协调作用；( 5 ) 机械支持作用；( 6 ) 免疫保护 作用；( 7 ) 信号接受和传导作用；( 8 ) 生长和分化的控制作用。 蛋白质的种类繁多，每一种蛋白质在生物体内都起着非常重要的作用。早先，人们 认为每一种蛋白质单独的完成相应的功能，如图2 2 口( a ) 所示：蛋白质a 通过对s 产 生作用而合成p 。但是随着人们研究的深入发现在某一个具体的生物反应过程中，蛋白 质之间并不是独立工作的，而是由多种蛋白质共同参与完成的，如图2 1 乜1 1 ( b ) 所示： 蛋白质a 和细胞中的其他蛋白质共同作用完成一系列生命活动。也就是说，生命活动是 众多蛋白质同时作用的结果，相互作用的蛋白质系统是构成生命活动的基础。 a s _ p ( a ) x vz 图2 1 对蛋白质功能理解的两个阶段 预测蛋白质的功能一直是人们研究的重点，具体的预测方法也非常多，综合起来， 主要可以分为基于同源性的功能注释方法和基于非同源性的功能注释方法口1 。下面是对 这两大类方法的简要介绍。 2 1 1 同源性方法 基于同源性的蛋白质功能注释方法认为具有同源关系的蛋白质在功能上也有着高 度的相似性。在基于同源性的方法中，对功能的预测是通过比较蛋白质之间的相似性口3 6 东北师范大学硕士学位论文 来完成的，这些相似性主要包含蛋白质的序列，域结构，甚至是蛋白质的二级或三级结 构。因此，在使用同源性方法对未知功能的蛋白质进行预测时，需要将未知蛋白的上述 特征和已知蛋白进行比较，如果它们相似程度达到一定的阈值，则认为这些蛋白质是同 源蛋白质，功能未知的蛋白就可以由已知蛋白推测而知。 基于同源性的方法具有大通量与自动化的优势，曾在基因组测序时得到了广泛的应 用，并在各种基因及蛋白质的进化、结构、催化等特性的研究中取得了一定的成果。但 是随着人们对测试结果精确度要求的不断提高，基于同源性功能注释方法的一些缺点也 逐渐暴露出来：首先，比较常规的蛋白质功能注释的计算方法主要是基于序列的同源性 分析，而这种方法的局限性在于不能对大量的孤儿家族和孤儿基因进行注释；其次在研 究过程中也发现了这样的事实口1 ：序列或结构相似的蛋白质在功能上并没有明显的相关 性，反过来也一样，就是功能相关的蛋白质并没有序列或结构上的相似性。此外，对生 物数据的分析如果仅仅是利用相似性，而离开了生物进化的观点，那么就没有任何的研 究意义应用价值。所以近些年来，尤其是人类基因组计划完成后，人们开始把研究重心 转移到另一种基于生物进化观点的新方法一非同源性功能注释方法。 2 1 2 非同源性方法 基于非同源性的蛋白质功能注释方法是最近几年才逐渐发展起来的一种新方法 眵7 1 。该方法是通过蛋白质的属性，而不是与其他蛋白质的相似性来对蛋白质进行功能 注释的。这些属性啼7 3 包括距离复制起源的距离，在物种间的分布模式，对临近蛋白质 的分析，域模型以及密码子的使用或者核酸的成分组成。在基于非同源性的方法中，同 一物种内甚至不同物种间的蛋白质可以根据这些属性进行分组，同一分组中的蛋白质被 认为具有相同或相似的功能，这样，功能未知的蛋白质就可以根据和它同为一组的功能 已知的蛋白质推测出来。基于非同源性的蛋白质功能注释方法的最大特点是体现了生物 进化的观点，比起同源性方法其实验结果也就更为可靠。 目前基于非同源性的蛋白质注释方法主要有以下几种：系统发育谱、基因邻接、基 因融合事件、保守的蛋白质问相互作用、进化速率关联、镜像数、序列信号关联以及同 源结构复合物。其中前四种方法在实际研究中都有了不同程度的应用，我们对它们的基 本原理做简单的介绍。 1 系统发育谱( p h y l o g e n e t i cp r o f i l e ) 系统发育谱法是一种通过进化信息推测蛋白质功能的大规模比较基因组法。这个方 法基于如下假定：功能相关的( f i l n c t i o nr e l a t e d ) 蛋白质在物种间的分布是相同的或相似 的，即它们在一组完全测序的基因组中同时存在或同时不存在，这种存在或不存在的模 式被称作系统发育谱，假设有两个蛋白质，它们在序列上没有同源性，但它们的系统发 育谱一致或具有一定程度的相似性，则可以推断它们在功能上是具有相关性的。系统发 育谱方法最早是由p e l l e 鲥n i 等人提出的，选择了1 6 个完成全测序的细菌基因组，构建 大肠杆菌核糖体蛋白r l 7 ，鞭毛结构蛋白n g l ，和组氨酸合成蛋白h i s 5 等三种蛋白的 系统发育谱。结果显示，功能相关的蛋白能够很好地聚类在一起。这个方法提供了一种 7 东北师范大学硕士学位论文 为未知功能蛋白注释的方式。但是，它的限制是，不能判断功能相关的蛋白是否“物理” 上直接接触，只能注释非必需蛋白的功能；其准确性依赖于完成全测序的基因组的数 量以及系统发育谱方法的可靠性。 2 基因融合事件( g e n ef u s i o ne v e n t s ) 这个方法基于这样一个假设：在物种进化过程中可能发生基因融合事件，即一个物 种的两个或多个功能相关的基因，在另一个物种中融合成为一个基因。基因融合事件可 以作为基因功能关系指示。m a u f c o t t e 等人与e n r i g l l t 等人分别建立了这个方法。e d w a r d 等人搜索了4 2 9 0 个大肠杆菌基因序列，获得了6 8 0 9 个t r i p l e tc 蛆d i d a t e 。经过过滤步骤， 最后确定为7 4 9 个，明显增加了候选者属于物理上功能相关的几率。但是，这个方法受 到基因融合事件复杂性的影响，此外，基因融合的机制可能是复杂多样的，必然会带来 较高的假阳性率。 3 保守的蛋白质问相互作用( i n t e r o l o g s ) 该方法基于如下原理：功能相关的蛋白质，其功能关系的演化具有保守性，因此， 可以通过在一个物种中建立蛋白质相互作用网络，预测其它物种的蛋白质问相互作用。 w a u h o u t 等人首先提出了i n t e r o l o g s 这个新概念，随后由m a t t h e w s 等人利用酵母双杂交 法分析了1 1 9 5 个啤酒酵母相互作用蛋白质在线虫( c e l e g a n s ) 中的保守性，获得了1 6 到3 1 线虫保守相互作用蛋白质，它们主要集中在执行核心代谢过程细r em e t a b o l i c p r o c e s s e s ) 等功能的蛋白质中，并且，与其随着亲缘关系的远近，保守性有相应的变化。 4 进化速率关联( e v o l u t i o n a r 、rc o r r e l a t e d ) 该方法的原理是：蛋白质的进化速率由这个蛋白质同其它蛋白质发生相互作用的数 量决定，并呈负相关，即相互作用的数量越多进化速率越低。该方法不是通常设想的蛋 白质的进化速率由这个蛋白质对机体的重要性决定。这是一个极重要的概念。f r a s e r 等 人利用一组实验上证实的酵母相互作用蛋白质，量化分析了进化速率、适合度、合序列 共进化之间的关系。统计分析显示，在酵母蛋白质相互作用网络中，连接点越多的蛋白 质进化速率越低。可能的原因是，这些蛋白质需要与更多的相互作用体共同进化。 2 2 经典的聚类算法 数据挖掘( d a t am i n i n g ) m 1 是一种用于从大型数据库或数据仓库中探索和抽取隐 藏信息的新技术。它能从存有海量信息的数据库中识别出新颖有效的知识，并开采出具 有潜在效用的模式，最终找出可用来指导商业行为或辅助科学研究的最有价值的信息。 从技术上来划分，数据挖掘分为两大类m 1 ：探索型数据挖掘和预测型数据挖掘。探索型 数据挖掘包括一系列在预先未知任何现有模式的情况下在数据内查找模型的技术，如频 度分析、分群和关联分析等。预测型数据挖掘包括一系列在数据中查拢目标变量与其他 变量之间关系的技术，如分类、聚类、数值预测等。 聚类分析是模式识别和数据挖掘中普遍使用的一种方法，是基于数据的知识发现的 有效方法，特别适用于模式分类数不知道的情况。聚类分析是一种无监督学习方法，不 8 东北师范大学硕士学位论文 需要任何先验领域知识，它根据数学特征提取分类标准，对数据进行分类，这种数学特 征的例子有统计平均值、相关系数、协方差矩阵的本征值及本征向量等。聚类分析主要 有k 均值聚类算法、层次聚类算法、最近邻分类算法、b p 神经网络分类算法和自组织 特征映射网络等。 k - 均值聚类在数据划分上不考虑类的分层结构问题，该算法使待聚类的所有向量 到聚类中心的距离的平方和最小，这是在误差平方和准则的基础上得到的。聚类中心的 个数k 、初始聚类中心的选择、基因排列的顺序以及基因表达谱数据的分布影响聚类的 结果，当基因表达谱类别之间分离较远时，该算法可以取得令人满意的聚类分析结果。 层次聚类法在统计分析中也称为系统聚类法。该方法在基因表达谱聚类分析中是常 用的方法。它的优点是容易理解和实现，所得到的结果以树状图的形式表示，可以直观 地观察基因之间的相互关系，尤其是类与类之间的关系。但是基因表达谱的数量很多， 往往要多于系统发生树分析时的物种数量，而且基因之间相互关系的信息也没有物种之 间的多，所以，对聚类结果后续分析要比系统发生树分析复杂得多。对于表达谱聚类的 结果还需要进一步分析基因的功能或者基因的特征，一般通过剪枝的过程往往带有更多 的主观性，这会导致丢失一些重要的信息或包括一些无关的信息。此外，它还会导致聚 类结果与向量的次序，所以被认为是一种局部最优解的方法。 2 2 1k - m e a n s 聚类算法 基于距离的聚类算法采用距离作为相似性的评价指标，即认为两个对象的距离越 近，其相似性就越大。该类算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且 独立的簇作为最终目标。k - m e 粕s 算法是属于该类比较经典的算法。 k - 均值( k _ m e 观s ) 聚类是目前应用最广泛的划分聚类算法之一。适用于处理庞大 的样本数据。其基本思想是首先给定要构建的划分的数目k ，然后通过一定的规则创建 一个原始划分。之后再采用一种迭代的重定位技术，通过再分配类成员来使“类”内分散 度达到最小化，直到所有的样本都不能再分配为止。根据初始值、相异度、聚类平均值 计算策略上的不同，k - 均值方法有很多变种，对于数据分布比较接近球状的情况有很 好的聚类效果。 1 k - m e a n s 算法的基本原理 k - m e a n s 算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是 将数据点到原型( 类别中心) 的某种距离和作为优化的目标函数，利用函数求极值的方 法得到迭代运算的调整规则。k - m e 蛆s 算法以欧式距离作为相似性测度，它是求对应某 一初始聚类中心向量y 。以，k ，k ) 1 最优分类，使得评价指标，。值最小。 算法常采用误差平方和准则函数作为聚类准则函数，定义为乜1 ： 厂。一三忉一m r i l 2 ( 2 - 1 ) 9 东北师范大学硕士学位论文 其中，m ；是类c ；中数据对象的均值，p 是类c ；中的空间点。 分析误差平方和准则函数发现：k - m e a i l s 算法是一个最优化求解问题，目标函数存 在着许多局部极小点，只有一个是全局最小点。目标函数的搜索方向总是沿着误差平方 和准则函数减小的方向进行。不同的初始值使得聚类中心向量y 沿着不同的路径使目标 函数减少。如图2 2 所示，目标函数分别沿着圪、圪、诈三种不同的初始值向量的路 径逐步减小，分别找到各自对应的最小值。其中，只有曰点对应的最小值才是全局最小 点，而4 、c 两点对应的最小值是局部极小点。k m e 卸s 算法是一种爬山算法( h i l l c l i i n b i l l g ) ，算法终止时往往找到的是局部极小值。 吆 b 图2 - 2 目标函数的局部极小和全局最小 k m e a n s 算法采用迭代更新的方法：在每一轮迭代中，依据七个聚类中心将周围的 点分别组成七个簇，而重新计算的每个簇的质心( 即簇中所有点的平均值，也就是几何 中心) 将被作为下一轮迭代的参照点。迭代使得选取的参照点越来越接近真实的簇质心， 所以目标函数越来越小，聚类效果越来越好。 2 k - m e a n s 算法思想及算法框架 k m e a n s 算法是一种典型的基于划分的方法，目标是根据输入参数七，将数据集划 分成七个簇。该聚类方法用到的数学工具不多，但被经验证明是一种很有效的方法。 算法首先随机选取七个点作为初始聚类中心，然后计算各个样本到聚类中心的距 离，把样本归到离它最近的那个聚类中心所在的类；对调整后的新类计算新的聚类中心， 如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数j ，已经收 敛。 该算法属于动态聚类法( 也称逐步聚类法) ，其迭代过程采用按批修改方法，即在 每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部样本调整 完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确 分类，则不会有调整，聚类中心也不会有任何变化，这标志着，已经收敛，算法结束。 1 0 东北师范大学硕士学位论文 该算法框架如下： ( 1 ) 给定大小为忍的数据集，令，一1 ，选取七个初始聚类中心z ，( ，) ，j 一1 ，2 ，七； ( 2 ) 计算每个数据对象与聚类中心的距离d ；，z ，( 呦，f l 2 ，3 ，万， j 一1 ，2 ，3 ，七。如果满足 d ( 五，互( 功一i i l i n d ( 五，z ，u ”，j f - 1 2 ，棚) ( 2 2 ) 则五哌5 ( 3 ) 计算误差平方和准则函数，： 加) 一毫弘 引刮i c 2 渤 ( 4 ) 判断：若恤( ，) 一儿( ，一1 ) | 多则算法结束；否则，一，+ 1 ，计算七个新的聚类 中心，z ) 一三罗x f d ，j 一1 ，2 ，七，返回( 2 ) 。 万爿 从上面的算法思想和算法框架，我们不难看出，七个初始聚类中心点的选取对聚类 结果具有较大的影响，因为在该算法第1 步中是随机的选取任意七个点作为初始聚类中 心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各 个簇中心的距离，将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代 运算完成，新的聚类中心和，。值也计算出来。如果在一次迭代前后，j 。值没有变化， 说明算法已经收敛，即准则函数j 。作为算法是否结束的依据。在迭代过程中，- ，。值逐 渐减小，直到它的最小值为止。 在算法的每次迭代中，把每一个数据对象分到离它最近的聚类中心所在类。这个过 程的时间复杂度为d ( n 材) ，这里的刀指的是总的样本点的个数，七是指定的聚类数，d 是样本点的维数；计算新的聚类中心，这个过程的时间复杂度是d ( 以d ) ；计算聚类准则 函数值所需的时间复杂度和计算新的聚类中心所需的时间复杂度一样，都是d 0 d ) 。 因此这个算法所需要的总的时间复杂度为d d ) ，其中f 是算法循环的次数。一 般地，七 疗，f c 厅。 3 k _ m e 锄s 算法的优缺点 k - m e a n s 算法的优点是：简单易行，不必确定距离矩阵，具有高效性，时间复杂性 接近线性，适合对大规模数据的挖掘。这就是k - m e a i l s 算法之所以被如此广泛地应用 东北师范大学硕士学位论文 的原因。但k m e a n s 算法存在着不少缺点，主要的问题有以下几个方面： ( 1 ) k - m e a n s 算法中聚类个数k 需要预先给定。 聚类结果严重依赖于用户参数的合理选择，然而这个k 值的选定是非常难以估计 的。特别当不知道数据的分布形态时，给用户带来了很大的困难。有的算法通过类的自 动合并和分裂，得到较为合理的类型数目k ，例如i s o d 觚a ( i t e r a t i v es e l f b r g a n 讫i n gd a t a a n a l y s i st e c h i l i q u e s 舢g o r i t l l i n ) 算法。使用的是一种称为次胜者受罚的竞争学习规则， 来自动决定类的适当数目。并针对“聚类的有效性问题”提出了一种新的有效性指标： 吃 ) 一砌加 ) + 砌幼 ) 伽研 一) ( 2 4 ) 其中七。是可聚类的最大数目，目的是选择最佳聚类个数使得有效性指标达到最小。 ( 2 ) 算法对初始值的选取依赖性极大以及算法常陷入局部极小解。 不同的初始值，结果往往不同。k - m e 锄s 算法首先随机地选取七个点作为初始聚类 种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效 果的不稳定。并且，k - m e 觚s 算法常采用误差平方和准则函数作为聚类准则函数( 目标 函数) 。目标函数在空间状态是一个非凸函数，由前面介绍的k - m e 锄s 的基本原理得知， 非凸函数往往存在很多个局部极小值，只有一个属于全局最小。由于算法每次开始选取 的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过 迭代运算，目标函数常常达到局部最小，得不到全局最小。 ( 3 ) 由于将簇的质心( 即均值点) 作为聚类中心进行新一轮聚类计算，远离数据密 集区的孤立点和噪声点会导致聚类中心偏离真正的数据密集区，所以k - m e a n s 算法对 噪声点和孤立点很敏感。 如何修改这个算法来消除这种敏感性就成了需要考虑的一个问题。考虑不采用簇中 对象的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点。这样的划分方 法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的，这是 k - m e d o i d 方法的基础。p a m ( p a n i t i o n i n ga r o u n dm e d o i d ，围绕中心点的划分) 是最早 提出的k - m e d o i d 算法之一。它试图对忍个对象给出七个划分。最初随机选择七个中心 点后，该算法反复地试图找出更好的中心点。所有可能的对象都被分析，每个对中的一 个对象被看作是中心点，而另一个不是。对可能的各种组合，估算聚类结果的质量。一 个对象被可以产生最大平方误差值减少的对象代替。在一次迭代中产生的最佳对象的集 合成为下次迭代的中心点。其执行效率不及七均值算法。 ( 4 ) k - m e a n s 算法一般只能发现球状簇 k - m e 锄s 算法常采用误差平方和准则函数作为聚类准则函数( 目标函数) ，而且是 基于欧氏距离的相似性度量。考察发现：如果各簇之间区别明显且数据分布稠密，则基 于欧氏距离的误差平方和准则函数比较有效；但是如果各簇的形状和大小差别很大，为 使误差平方和j ，值达到最小有可能出现将大的聚类簇分割的现象。 以上介绍了k m e a l l s 算法的许多改进方法，它们在初始聚类中心的选择、迭代过 1 2 东北师范大学硕士学位论文 程中聚类中心的选取、处理的数据类型、相似性的度量等策略上各有不同。 2 2 2 层次聚类算法 层次聚类算法( h i e r a r c h i c a lc l u s t e r i n gm e t h o d ) 是发展比较早、应用比较广泛的一 大类聚类分析方法。层次聚类算法又称之为树聚类算法。它是无监督学习方法中最重要 的一种，它