基于基因本体的基因功能相似性度量——毕业论文

Error! No text of specified style in document.摘要基因本体通过条目注释为不同物种间的基因产物提供统一的功能描述，为研究基因的功能提供了有效的途径，目前已经有很多基于基因本体衡量基因相似性的算法，但均存在条目间的共享语义被重复计算的缺陷。本文以两个基因注释集合的交集的信息量作为该对基因的共享语义，并结合继承语义和拓展语义的概念，在此基础上提出一种新的衡量基因功能相似性的算法注释的语义重叠比（Semantic Overlap Ratio of Annotation，SORA）。此外，考虑到基因本体中存在多重继承，本文对原始SORA算法做出修改，在计算继承信息量时乘以由被拓展集合中的条目数量和拓展条目的祖先数量确定的比例因子。最后，本文以致病基因作为测试数据，对原始及修改后的SORA算法进行了验证，实验结果说明本文实现的算法能有效刻画基因的相似性。关键词：基因本体 语义相似性 注释的语义重叠比ABSTRACTGene ontology can provide a common schema for describing gene function among genes in different species, which means that there would be an effective approach to compare the functional aspects of genes. Up till now, many algorithms based on gene ontology for measuring gene semantic similarity have been proposed, most of which have the defect that the shared semantics of terms are added repeatedly.In this paper, the information content of the intersection of the annotation sets of two genes to be compared is considered as the shared semantics of this pair of genes. In light of this, a novel gene similarity measurement, Semantic Overlap Ratio of Annotation(SORA), is proposed, combined with the inherited and extended semantics. In addition, considering the multiple inheritance present in gene ontology, some modifications that the extended information content is multiplied by an index determined by the number of terms in the extended term sets and that of the ancestor terms of the extending term are made to the original SORA.Finally, both original and modified SORA are evaluated using some genes related to disease as the test data and the experimental results show that the algorithms implemented in this paper are reliable to characterize gene functional similarity.Keywords: Gene Ontology Semantic Similarity Semantic Overlap Ratio of AnnotationError! No text of specified style in document.i目录第一章 绪论11.1 引言11.2 研究现状11.3 研究内容和目标21.4 论文章节安排3第二章 GO与基因相似性度量52.1 GO概述52.2 基因的相似性度量52.2.1 成对比较62.2.2 成组比较7第三章 注释的语义重叠比算法93.1 条目信息量的计算93.2 继承信息量和扩展信息量103.3 计算集合的信息量113.3.1 算法描述113.3.2 算法示例133.4 基因的功能相似性度量163.5 算法改进17第四章 实现与评估194.1 实验环境及所用到的包194.1.1 R语言简介194.1.2 存储GO条目信息的包194.1.3 存储各物种基因信息的包204.2 SORA算法实现214.3 实验验证244.3.1 数据准备244.3.2 实验结果分析25第五章 结论与展望29致谢31参考文献33第一章 绪论3第一章 绪论1.1 引言在生物信息学中，比较基因及基因产物的相似性在多种应用上都起着关键的作用，如蛋白质交互作用的分析1、致病基因预测2、基因聚类3等，最直接的方法是基于基因序列进行比较，然而这种方法只考虑到基因的内部结构，忽略了基因在生物过程中表现出的功能。而生物学家们在实验中发现，结构相似的基因并不一定在功能方面也具有很高的相似性，反之亦然4。这种现象虽然并非俯拾即是，不能因此否认基因结构作为一种相似性衡量方法的可靠性，而是应该在结构的基础上，辅助以功能相似性的比较。比如当研究与细胞增殖活动相关的基因时，除了分析哪些基因与少数从实验中已经得到验证的基因的结构相似外，或许还可以考虑那些参与了类似细胞增殖活动（如细胞分裂）的基因，后一种方法显然与基因的结构无关。基因的功能不像基因序列或结构，有客观的表示形式和可以测量的属性，且随着生物数据的海量增加，更需要有一种统一的模式来描述基因的功能，以便进行比较和数据的共享，基因本体（Gene Ontology，GO）应运而生。通过GO中条目对基因的注释，将基因转化为一些GO条目的集合，通过条目间的语义关系，可以推断出基因的功能相似性。由于通过实验验证基因的功能是一个非常耗时且代价高昂的过程，因此通过GO注释来预测基因功能一直是生物信息学的研究核心，同时生物学家们也在致力于探索如何能更准确地表达出GO条目、基因的语义。1.2 研究现状尽管语义相似性应用于生物信息领域的时间并不长，但目前已经有许多基于语义相似性进行比较的方法可为研究者使用，这些方法从比较的内容上可分为条目比较和基因比较。用于条目的比较方法大致可分为两类：基于边和基于结点。基于结点的方法常用信息量（Information Content，IC）这一概念来量化条目的语义，条目的IC值主要依赖于条目在GO这个有向无环图中的位置或是当前的注释情况。基于边的方法则常常使用距离（distance）的概念，距离完全依赖于条目在GO图中的位置，并不一定只是通过所要比较的条目之间的路径的边数来衡量相似性，也可借助于深度（depth），比如Pekar和Staab5提出的借助于两个条目的最大的公共祖先深度，即所比较的两个条目在GO图中的最低公共祖先条目到根条目的最长路径的边数。由于基因注释为多个条目，因此基因的功能比较依赖于条目集合，而非单个条目的语义衡量，用于基因的语义比较方法仍可分为两类：一类以条目对的方式比较，即不考虑同一注释集合中的条目之间的关系，首先对不同注释集合中的条目进行语义比较，然后基于条目间的语义相似结果得出基因的功能相似度，这一步可采取不同的策略，Lord等人6采取求所有条目对的相似度的平均值的策略，Wang等人7采取的策略是求最匹配条目对的相似度的平均值，等等。这类方法非常依赖于条目间相似性的比较效果。另一类是以成组方式比较，这类方法将同一注释条目集合中的条目看做一个整体，因此并不依赖条目间的语义相似性，目前成组比较的方法多考虑基因的表示方式，Lee等人8将基因表示成其注释条目的集合，Chabalier等人9将基因表示成由条目构成的向量，此外还有其他表示方式。根据每种不同的形式可采取相应的相似性比较方法，然而这些方法大都忽略了注释条目本身的信息量，这也意味着基因的很多隐藏在GO中的语义还未被发掘出来，本文将着重讨论如何在成组比较基因相似性的方法中，结合信息量更准确地发掘出基因的语义。1.3 研究内容和目标在比较基因的功能相似性时，成组比较的方法更注重同一基因的注释集合中的条目间的关系，目前人们对条目的信息量做了很多研究，但对条目集合的信息量却讨论较少，只将集合中的条目的信息量进行简单求和，以此作为集合的信息量，这显然并不合理。GO条目之间存在“is-a”或“part-of”的关系，当一个条目“继承”自另一条目（两者存在“is-a”关系）后，子条目会获得父条目的所有语义，此外在继承父条目语义的基础上，子条目还会拓展出属于自己本身特性的语义。一个条目可以产生若干子条目，如果两个条目之间存在共同的祖先条目，那么这两个条目必然会有共享语义。在计算条目集合的信息量时，如果只是将条目元素的信息量相加，那么条目成员间的共享语义无疑会被重复计算。本文提出一种新的以成组形式来衡量基因功能相似性的算法注释的语义重叠比（Semantic Overlap Ratio of Annotation，SORA），通过组合条目的继承信息量和拓展信息量，可避免集合中条目间的共享语义被累加。不管是GO条目，抑或是基因，在衡量其相似性时都要考虑如何计算共享语义，Resnik10方法借助信息量最多的公共祖先，DiShIn11方法借助分离公共祖先信息量的平均值，而SORA方法中将以两个基因的注释集合的交集的信息量作为该对基因的共享语义。GO条目可以通过IC值体现其具体程度，基因通过GO注释转化为条目集合后，也具备了特定的信息量，本文在SORA算法中考虑到基因本身的信息量以及浅注释的问题对衡量基因相似性产生的影响，提出一种新的方式来比较基因相似性。此外，考虑到GO条目并非是以“树”的形式构建，而是以有向无环图的方式，这意味着GO条目间会有多重继承，因此本文还将对SORA算法提出一些修改，使其更加合理。之后通过以致病基因为测试数据进行实验，验证了SORA算法的合理性。1.4 论文章节安排本文剩余章节安排如下：第二章介绍了本文需要用到的基础知识，包括GO概述、基因注释，并对目前基因功能相似性的衡量方法进行分类叙述，其中介绍了几种经典的算法，并分别进行了分析。第三章详细介绍SORA算法，首先讨论单个条目的信息量的计算方法，接着阐述该算法之所以提出所针对的问题，继而引出继承和拓展信息量的概念，再以此为基础，提出计算条目集合信息量的算法。由于这一部分是SORA算法的核心，所以将以较多的篇幅进行详细叙述，并通过一个具体的例子展示算法的执行流程。最后以集合信息量为基础，提出衡量基因的功能相似性的方法。第四章叙述SORA算法的实现以及对该算法的测试评估。首先对实现语言R和算法实现过程中使用到的包进行介绍，然后对算法实现时所划分的各个模块进行详细叙述，最后通过以致病基因为测试数据进行测试，验证了算法的合理性。第五章对整篇论文进行总结，提出了SORA算法可以被其他算法借鉴的地方，以及后续可改进的方面，最后展望了基因功能相似性衡量方法的前景。第二章 GO与基因相似性度量7第二章 GO与基因相似性度量2.1 GO概述GO是一个受控的、有结构组织、独立于物种的词汇集合，其提出的初衷在于为不同数据库间的基因产物的功能提供一致的描述12。基因本体由三个互不重叠的本体组成，分别为分子功能（Molecular Function，MF）、生物过程（Biological Process，BP）、细胞组分（Cellular Component，CC），每个本体内部都有代表不同含义的条目。GO中的每个条目都有唯一的标识符来区分，条目以不同的关系相连构成一个层级图，大部分条目间的关系为“is-a”和“part-of”，所描述的功能相近的条目在图上的位置更加接近。MF本体内的条目主要描述与基因的功能相关的特性，比如基因的功能范围，BP本体内的条目主要与基因的交互有关，因此可用来预测基因功能和分析共同表达数据，CC本体内的条目主要用来验证与基因在细胞中的位置密切相关的过程和活动。一个基因或基因产物可映射为与之相关的若干GO条目集合，这一过程称为GO注释，通过GO注释得到的条目集合的语义相似性可作为基因功能相似性的一种度量。在GO有向无环图中，存在如下性质：下层的条目比上层的条目更为具体，即从父条目到子条目，含义是逐层丰富的，条目的深度越大，可提供的信息越多，因此，应该尽可能选择下层的条目来注释基因产物。此外，由于子条目继承了父条目的语义，因此基因如果被某个条目注释，则也将被此条目的所有祖先条目注释，前者称为直接注释，后者称为间接注释，这也称为GO注释的真路径法则。目前由基因本体联合会（GO Consortium）负责开发和维护GO条目及其关系、对基因的注释方面的工作。2.2 基因的相似性度量两个实体的语义相似性可被定义为一个具有以下特性的函数，当向该函数传入注释这两个实体的本体条目集合后，此函数会返回一个数值来显示这两个实体在含义上的接近程度13。两个基因被一些GO条目注释后，其功能相似性可以由其注释条目间的语义相似性推断，如果注释条目的语义相似，那么可以认为该对基因具有相似的功能。因此，研究者们提出了很多基于语义相似性分析基因的功能相似性的方法，这些方法从比较方式上可以分为两类：成对比较和成组比较。2.2.1 成对比较在此类方法中，每一个基因表示成其直接注释条目的集合，两个基因的功能相似性通过组合一个注释集合中的条目与另一注释集合中的条目之间的语义相似性来得到。给定两个基因G1、G2，其注释条目集分别为S1、S2。成对比较方法的第一步是将基因G1的注释集合S1中的每一个条目与基因G2的注释集合S2中的每一个条目进行语义相似性比较，假设S1中有m个条目（即基因G1被m个条目注释），S2中有n个条目（即基因G2被n个条目注释），那么在对所有条目对进行比较后，可以得到mn个结果。第二步根据不同的需求，对上一步得到的mn个数值采取相应的策略得到基因G1、G2的功能相似性。可以看到，成对比较方法的一个关键在于条目对的语义相似性的比较，此时常常借助IC这一概念，一个条目的IC是一个可以量化该条目能够提供多少信息的数值，含义越具体的条目，其IC值越大，由于本文所提出的算法中对信息量有较多的讨论，故此处不详细叙述。下面只介绍几种常用的条目相似性的比较方法。Resnik方法借助两个条目信息量最大的公共祖先（Most Informative Common Ancestor，MICA）来衡量两个条目的相似度，如式（2-1）所示。simRest1,t2=IC(tMICA) 式(2-1)在图结构中，两个结点的公共祖先可代表这对结点的共享语义。Resnik方法虽然能刻画出两个条目的共有的信息量,却无法体现出条目间的差异性,Lin14和Jiang&Conrath15在Resnik方法上做出一些改进，考虑到所比较的条目与MICA的距离,定义分别为式（2-2）和式（2-3）。simLint1,t2=2IC(tMICA)ICt1+IC(t2)式(2-2)simJCt1,t2=1-ICt1+ICt2-2IC(tMICA)式(2-3)在成对比较方法的第二步中采取的策略通常有三种：取最大值（MAX）、取所有对的平均值（AVG）、取最匹配对的平均值（BMA）。AVG策略对第一步得到的结果不加选择，取所有条目对的相似度的平均值作为基因G1、G2的相似性。这种策略可能会低估基因的相似性，若两个基因的注释条目集合完全相同，则AVG策略的计算结果是该对基因的相似度为0.5，而实际上，由于其注释条目完全匹配，相似度应该为1。MAX策略取第一步所得结果中最匹配的条目对的相似度来衡量基因G1、G2的相似性。显然，这种策略会高估基因的相似性，若两个基因的注释集合中有相同的条目，则MAX策略认为该对基因的相似度为1，这完全忽略了其他不同注释条目的影响。但是在某些应用中，可能需要判断两个基因是否有共同的方面，而不在乎相似的程度，这时可以使用MAX策略。BMA策略在第一步得到的结果中，每一个条目只选取与其最匹配的条目，即相似性最大的条目，如此将结果的数目缩小为m+n，计算这m+n个结果的平均值，作为基因G1、G2的相似性。这种策略是AVG和MAX两种策略的折衷，往往能较为准确地衡量两个基因的相似性。2.2.2 成组比较成组比较的方法并不依赖两个注释集合中条目之间的相似性，而是将同一注释条目集合看做一个整体，这些方法从基因的表示形式上大致可分为三类：基于集合、基于图和基于向量。基于集合的方法将基因表示成其完整的注释条目集合，常会用到条目重叠（Term Overlap，TO）16这一概念，即借助两个注释条目集的交集来比较基因的相似性，如Lee等人提出的方法借鉴Jaccard指数，以TO中元素的数目来衡量基因的相似性，集合A、B的Jaccard指数定义如式（2-4）所示。之后又在TO的基础上结合条目的IC，引入图信息量（Graph Information Content，GIC）17这一概念，注释条目集分别为S1、S2的基因G1、G2的相似性计算如式（2-5）所示。JA,B=AB|AB|式(2-4)simGICG1,G2=cS1S2IC(c)cS1S2IC(c)式(2-5)基于图的方法将基因表示成由其注释条目构成的GO子图，然后使用图匹配技术衡量基因的相似性。然而由于图匹配算法往往具有很高的计算复杂度，所以这种方法并不常用。基于向量的方法将基因表示成各个维度对应一个条目的二值向量（只有0和1），如果该维度为1，则表示基因被该条目注释，反之则反，这种方法通过计算两个向量的余弦相似度或者条目共同出现的概率来衡量两个基因的相似性。向量A和B的余弦相似度CoSim定义如式（2-6）所示。CoSimA,B=ABA2+B2-AB式(2-6)第三章 注释的语义重叠比算法19第三章 注释的语义重叠比算法3.1 条目信息量的计算信息量是一个衡量条目含义的具体程度，或言之，条目可提供多少信息的数值。很多相似性比较的算法都需要借助信息量，然而其计算方法并没有一个统一定论，因为在不同的环境下，人们对条目的具体性（specificity）有不同的理解。常用的计算信息量的方法有两种：一是基于语料库，二是基于GO的图结构。在基于语料库的方法中，条目t的信息量需要借助条目的注释频率，定义如式（3-1）所示。ICcorpus(t)=-logpt式(3-1)其中p(t)是条目t及其后代在特定GO注释语料库中的出现频率，假如一个语料库中有50个被注释的基因，其中有10个基因被条目t注释，则条目t的注释频率p(t) = = 0.2。当注释语料库中的基因数量变化时，条目的注释频率会受到影响，因此这种计算方法使得条目的信息量依赖于它所注释的基因数目在整个语料库中的比例，无法客观地反映出该条目所含信息的多少，且会受到研究偏见，显然那些处于研究热点的基因，其注释条目的信息量会显著增加。另一种方法基于GO图结构，不考虑条目与基因的注释关系，而只考虑条目自身的特性，如有多少后代条目，这种方法下条目t的信息量定义为式（3-2）。ICstructuret=logdesct+1total_termslog1total_terms=1-log(desc(t)+1)log(total_terms) 式(3-2)其中desc(t)是条目t的后代数目，total_terms是条目所在的本体（BP、MF、CC之一）中的条目总数。这种方法对同一条目在不同的注释语料库间可以产生一致的IC值，使信息量不会受到注释的影响，这比基于语料库的方法显得更合理，但对于叶子条目（没有后代的条目）而言，式（3-2）计算得到的结果为1，这意味着所有叶子条目的信息量是相同的，显然有悖于事实，因为位于GO图上层的叶子条目并不如处于下层的叶子条目具体，所以其信息量也应有所差异。3.2 继承信息量和扩展信息量在GO概述中已经介绍，条目的信息量与其深度成正相关，在GO图结构中，越处于下层的条目，其含义越具体，换言之，其信息量越大。但是如果限定条目的信息量只与深度一个因素有关，那么同一深度的条目的信息量的差异则无从体现。借鉴上文中提到的基于GO图结构计算信息量的方法，引入条目后代的数目这一因素，当一个条目的后代数目越多时，此条目扩展的语义便越多，也意味着这个条目越不具体，即信息量越小。结合深度和后代数目两个因素，本文提出一种新的计算条目信息量的方法，定义如式（3-3）。ICt=SpecificitytCoveraget=Specificityt(1-log(desct+1)log(total_terms)式(3-3)其中Specificity(t)要用到条目t在GO图中的最大深度，考虑到整个图的结构，故用该条目的深度与条目所在本体子图的最大深度之比作为Specificity(t)的值，而条目的Coverage则使用式（3-2）。这种计算方法可以避免条目的信息量受到注释语料库的影响，而且考虑的因素更加全面，更能客观而准确地反映出条目的语义。上文提到过在GO注释中的真路径法则如果基因被一个条目注释，那么该基因也将被此条目的所有祖先条目注释据此可以推断，祖先条目的语义是其后代条目语义的概述，而后代条目的语义则是在祖先条目的语义的基础上扩展得到的。当两个条目之间存在父子关系时，子条目会获得父条目的所有语义，同时扩展出自己的语义，因此，一个条目的语义可以分成两部分：继承语义和扩展语义，继承语义是从父条目继承下来的语义，而扩展语义则是该条目的自身属性，相应地，使用继承IC和拓展IC分别用于量化继承语义和拓展语义。如果条目t1是条目t2的祖先，则条目t2从t1的继承信息量等于条目t1的信息量，即ICinherit(t1 t2) = IC(t1)，而t2对t1的扩展信息量定义为条目t2与t1的信息量之差，如式（3-4）所示。ICextendt1 t2= ICt2- ICt1式(3-4)类似地，给出一个条目ti的祖先条目集合AS(ti)，ti从该集合的继承信息量为此集合的信息量IC(AS(ti)，而ti对该集合的拓展信息量定义为ti与集合AS(ti)的信息量之差，如式（3-5）所示。ICextend(AS(ti) ti) = IC(ti) - IC(AS(ti) 式(3-5)3.3 计算集合的信息量计算一个条目集合的信息量时，现有方法是将其成员条目的信息量直接相加，但是GO本身含有“继承”的内在特点，条目之间存在“is-a”或“part-of”的关系，因此条目之间可能会共享信息量。假设条目集合S中有条目t1和t2，这两个条目有一个公共祖先条目tc，则条目t1和t2从条目tc继承的语义是相同的，但拓展语义有所差别，如果采用以往的方法，则条目集合S的信息量的计算结果如式（3-6）所示。IC(S) = IC(t1) + IC(t2)= IC(tc) + ICextend(tc t1) + IC(tc) + ICextend(tc t2)= 2IC(tc) + ICextend(tc t1) + ICextend(tc t2)式(3-6)从式（3-6）中可以看到使用通常方法计算条目集合S的信息量，会使条目间的共享信息量tc被重复计算，而实际应该只计算一次。下面介绍一种方法，通过合并集合中条目的继承和拓展信息量能够有效地避免上述问题。3.3.1 算法描述对于一个条目成员之间存在“继承”关系的集合而言，由于后代条目已经涵盖了祖先条目的语义，因此祖先条目对整个集合表现出的语义实际并没有贡献，因此在计算一个条目集合的信息量时，首先要在集合中去掉后代也存在于集合中的条目，然后将剩余条目的信息量“相加”，这里所谓的“相加”意指对已经求出信息量的集合，在要加入新的条目时，只需加入该条目的拓展信息量。为言简意赅之便，下列叙述中将使用以下简称：CET(X)代表由集合X中后代不存在于X中的条目构成的集合，即t | tX m mdesct mX，textend表示在每一轮循环中从CET(X)中选出用于拓展集合X的条目，ESextend表示由textend及其祖先条目构成的集合，ESi (X)表示第i轮循环结束时X的拓展条目集，OSTi表示第i轮循环过程中X当前的拓展条目集中所包含的textend的祖先条目。算法的简要步骤如下：1. 根据输入X计算CET(X)2. 用式（3-3）计算CET(X)中每个条目t的信息量IC(t)3. 在CET(X)中选择textend来拓展ESi(X)4. 产生ESextend和OSTi5. 计算ICextend(OSTi textend)6. 在CET(X)中去掉textend，并更新ESi (X)7. 返回第3步直到CET(X)为空上述步骤中的一些具体操作方法，如怎样在CET(X)中选择textend，ESextend和OSTi的计算方式等用文字叙述较为晦涩，下面以伪代码的形式详细展示算法的执行流程。输入：条目集合X=t1,t2,.,tn计算CET(X)为每一个CET(X)中的条目ti计算其信息量IC(ti)IC0(X) 0ES0 n | CET(X) |i 1 while i=n textendti| tj tjCETX ICtjICti ESextendtextendAncestor(textend) OSTiESextendESi-1X if OSTi ICi(X) ICi-1(X) + ICextend(OSTi textend ) elseICi(X) ICi-1(X) + IC(textend) end if ESiESi-1ESextend CET(X) CET(X) textend i+end whileIC(X) = ICn(X)输出：条目集合的信息量IC(X) 3.3.2 算法示例以下通过一个例子阐述算法的执行流程。基因Q9BPW9在MF本体中的注释条目集为GO:0004022，GO:0004745，GO:0047035，GO:0016854，由于此集合中每个条目之间都没有继承关系，故CET集合与原始输入一致，n=4，利用式（3-3）计算集合中条目的信息量，结果如表3.1所示。表3.1 CET集合中条目的IC值条目GO:0004022GO:0004745GO:0047035GO:0016854信息量(IC)0.29010.37500.43750.1373执行算法的过程中，本文在文字叙述的基础上辅助以相关条目构成的GO子图，图3.1至3.4分别展示了每一轮循环中涉及到的条目在GO图中的位置和关系，每幅图中圆角矩形中的条目代表该轮循环中的textend，有灰色阴影的条目构成OSTi集合，每一幅图中包含的所有条目构成该轮循环结束后的ESi集合。此外，表3.2也展示了每一轮循环中关键变量的值以及集合信息量的变化。表3.2 每轮循环中关键变量的值循环1st2nd3rd4thtextendGO:0047035GO:0004745GO:0004022GO:0016854OSTiGO:0003674 GO:0003824 GO:0016491 GO:0016614 GO:0016616GO:0003674 GO:0003824 GO:0016491 GO:0016614 GO:0016616GO:0003674 GO:0003824ICi0.43750.69770.87301.0046在首轮循环中，拓展条目为GO:0047035，图3.1中所有椭圆中的条目为GO:0047035的祖先条目，由于ES0为空集，故OST1为空集，所以IC1 = IC0 + IC(textend) = 0.4375，即此时集合的信息量为条目GO:0047035的信息量，CET集合中去掉GO:0047035，为GO:0004022，GO:0004745，GO:0016854。GO:0004745GO:0003674GO:0003824GO:0016491GO:0016614GO:0016616GO:0016229GO:0033764GO:0047035GO:0003674GO:0003824GO:0016491GO:0016614GO:0016616GO:0016229GO:0033764GO:0047035 图3.1 首轮循环拓展的条目集合 图3.2 次轮循环拓展的条目集合在第二轮循环中，拓展条目为GO:0004745，其祖先为图3.2中有灰色阴影的条目，同时构成OST2集合，此时如果要在集合ES1中加入条目GO:0004745，则整个集合的信息量只需在IC(ES1)的基础上加入条目GO:0004745从OST2拓展出的信息量。因为此时IC(OST2)代表着条目GO:0004745与ES1的共享语义，所以不应该再次加入到集合的信息量中，而要计算ICextend(OST2 textend)，则需要知道集合OST2的信息量。从图3.2可以看到，OST2集合的条目成员之间存在“继承”关系，其余条目成员均是GO:0016616的祖先，所以集合OST2的信息量即为GO:0016616的信息量，通过式（3-3）计算得IC(GO:0016616)为0.1148，故IC(OST2) = 0.1148，所以ICextend(OST2 textend) = IC(GO:0004745) IC(OST2) = 0.3750 0.1148 = 0.2602。此时在IC1的基础上加入GO:0004745从OST2拓展出的语义，则完成第二轮循环，IC2 = IC1 + ICextend(OST2 textend) = 0.4375 + 0.2602 = 0.6977，而ES2为ES1与GO:0004745的祖先条目的并集，即图3.2中的所有条目，CET集合为GO:0004022，GO:0016854。在第三轮循环中，拓展条目为GO:0004022，图3.3中有灰色阴影的条目为GO:0004022的祖先条目，构成OST3集合，从图3.3中可以看出本轮循环中的拓展条目GO:0004022与上一轮循环中的拓展条目GO:0004745有相同的祖先条目集合，所以GO:0004022与集合ES2的共享语义和GO:0004745与集合ES1的共享语义是一致的，本质原因在于被拓展的条目集合OST3与OST2是相同的。同理，要在集合ES2中加入条目GO:0004022，只需加入GO:0004022由OST3拓展出的语义，因为OST3与OST2相同，计算OST3信息量的方法与前文一致，此处不再赘述，故IC(OST3) = IC(OST2) = 0.1148，则拓展信息量ICextend(OST3 textend) = IC(GO:0004022) IC(OST3) = 0.2901 0.1148 = 0.1753，第三轮循环结束时IC3 = IC2 + ICextend(OST3 textend) = 0.6977 + 0.1753 = 0.8730，此时ES3为ES2与GO:0004022的祖先条目的并集，即图3.3中所示的所有条目，CET集合中只有GO:0016854。GO:0004022GO:0003674GO:0003824GO:0016491GO:0016614GO:0016616GO:0016229GO:0033764GO:0004745GO:0047035图3.3 第三轮循环拓展的条目集合在第四轮循环中，拓展条目为GO:0016854，其祖先条目为GO:0003674，GO:0003824，GO:0016853，图3.4中有灰色阴影的条目为textend的祖先条目集合与ES3的交集，即OST4。如果向集合ES3中加入条目GO:0016854，而GO:0016854自OST4的继承语义已经包含在IC3中，那么只需在IC3中加入GO:0016854由OST4拓展出的语义即可。既然要求拓展信息量，须得知道被拓展的条目集合OST4的信息量，集合OST4只有两个成员，从图中可以看到为父子条目关系，通过式（3-3）求得条目GO:0003824的IC值为0.0057，所以IC(OST4) = IC(GO:0003824) = 0.0057，则GO:0016854从OST4拓展出的语义ICextend(OST4 textend) = IC(GO:0016854) IC(OST4) = 0.1373 0.0057 = 0.1316，此时IC4 = IC3 + ICextend(OST4 textend) = 0.8730 + 0.1316 = 1.0046。IC4即为基因Q9BPW9在MF本体内注释的条目集合的信息量。GO:0016854GO:0003674GO:0003824GO:0016853GO:0016491GO:0016614GO:0016616GO:0016229GO:0033764GO:0004745GO:0047035GO:0004022图3.4 第四轮循环拓展的条目集合由上面的算法流程可以看出，SORA算法在计算一个条目集合X的信息量时，采用的思路是从一个空集合ES开始，用CET(X)中的条目不断拓展ES，每向ES中加入一个条目后，便更新集合ES的信息量，方法是在原有IC(ES)的基础上，加入该条目的拓展信息量，重复此过程，直到CET(X)中的条目全部加入ES中，从图3.4中可以看到集合ES最终包括X自身的全部条目以及每个元素的祖先条目。3.4 基因的功能相似性度量给定两个基因G1、G2，其注释条目集分别为S1、S2，在以往衡量两个基因的功能相似性的方法中，常会使用两个注释集中共有的条目的数目，如simUI方法，该方法定义基因的功能相似性如式（3-7）所示。FSsimUIG1,G2=S1S2S1S2 式(3-7)其中.代表集合的元素个数由于基因可表示为其注释条目的集合，那么注释集合的交集可用来衡量基因的共享语义，但如果只考虑交集中条目的数量，并不能准确地刻画基因的相似性，因为即使共享相同数量的条目，共享条目彼此之间也会有差异性。本文从GIC受到启发，引入信息量的概念，考虑以注释集合的交集的信息量来衡量基因的共享语义，如果交集的信息量较大，意味着该对基因的共享语义较多，说明其相似性程度较高。在衡量两个元素的相似性时，不应顾名思义只刻画其相似的部分，同时应该考虑到元素之间的差异性，故而需要引入所要比较的基因本身的特性。信息量不仅可以用来反映GO条目的具体性，同时也适用于基因，通过上文计算集合信息量的方法，一个基因在某一本体内也可以对应一个信息量，即该基因的注释集合的信息量。此外，虽然以式（3-3）计算条目的信息量，可以避免其受到注释语料库的影响，但对基因而言却无法做到这一点，因为基因要通过GO注释映射为一些条目的集合，而不同条目的具体程度往往有较大的差异，所以不可避免地会出现浅注释的现象某些基因只被若干含义较为广泛（即信息量较少）的条目注释。在这种情况下，两个功能相似度较高的基因，或许因为浅注释而导致计算出的共享信息量的数值并不高。鉴于以上两点，SORA算法以共享信息量占两个基因的信息量的比重的平均值来衡量该对基因的功能相似性，如式（3-8）所示，其中采用上文所展示的方法计算条目集合的信息量。FSG1,G2=12IC(S1S2)ICS1+IC(S1S2)ICS2式(3-8)3.5 算法改进GO结构并非是“树”，而是有向无环图，很多条目不止有一个父条目，而是“继承”自多个父条目，即多重继承的现象，一些算法专门为此而设计，如GraSM算法18、随机游走算法19等，SORA算法并没有考虑到多重继承的问题。如图3.5所示的一种情况，条目t3有两个父条目t1和t2，则条目t3的信息量可分解为两部分之和，其中一部分为从条目t1的继承信息量加上t3从t1拓展的信息量，另一部分为从条目t2的继承信息量加上t3从t2拓展的信息量，如果按照上述拓展信息量的计算方法，则条目t3的信息量如式（3-9）所示。然而这里出现了问题，式（3-9）中等式左边表示的是一份IC(t3)，而等式右边则是两份IC(t3)。IC(t1)+ICextend(t1t3)+IC(t2)+ICextend(t2t3)=2IC(t3) 式(3-9)问题的根源在于使用上述拓展信息量的计算方法时，IC(t3) IC(t1)不仅仅包括ICextend(t1 t3)，还包括了部分ICextend(t2 t3)和IC(t2)，换言之t3与t1的信息量之差不仅仅包括t3从t1拓展出的信息量，还有部分t3从t2继承、拓展的信息量，二者的比例划分要根据条目t1和t2的关系确定。鉴于此问题，对SORA算法进行一些修改，这里使用一种比较简单的策略：在原始SORA算法中，拓展信息量以拓展条目与被拓展条目（或集合）的信息量之差求得，修改为在其基础上辅助以比例因子，比例因子由被拓展集合中元素的数目除以拓展条目的所有祖先条目的数目确定。在本例中，t3从任一父条目拓展出的语义修改为t3信息量的一半与父条目信息量的差值，如式（3-10）所示，这样可以保证一个条目的所有继承信息量与拓展信息量之和与该条目的信息量保持一致。相应地，计算条目集合信息量的过程中，每轮循环计算拓展条目textend从集合OSTi拓展出的语义如式（3-11）所示。ICextend(t1 t3) = 12IC(t3)IC(t1)式(3-10)ICextend(OSTi textend) = OSTi AStextendIC(textend)IC(OSTi )式(3-11)t1t2t3图3.5 多重继承的一种形式 第四章 实现与评估29第四章 实现与评估4.1 实验环境及所用到的包4.1.1 R语言简介R是一种用于数据计算、绘图的编程语言，被广泛应用在数据分析、数据挖掘、机器学习、生物信息学等研究领域，R使用命令行操作界面，同时也有RStudio等第三方的可视化开发工具。R语言的最大优势在于有大量官方和第三方的包（package），可以在/中通过下载、安装而直接使用，过程非常方便。这些包均为开源发布，所以每个包的实现代码也可供开发者学习和借鉴。包中不仅仅包括实用的函数，还有大量数据，可以帮助研究者更方便地进行相关工作以及交流最新的研究成果、共享知识。4.1.2 存储GO条目信息的包GO.db是一个注释数据包，涵盖了关于GO的最新信息，该包每半年更新一次，包中提供若干对象来存储条目间的关系，SORA算法在实现时使用到的对象如下：（xx为条目所在的本体名称，为MF、BP、CC之一）GOxxANCESTOR ：用于查找一个条目的祖先条目。GOxxOFFSPRING ：用于查找一个条目的孩子条目。GOxxPARENTS ：用于查找一个条目的父条目。GOTERM ：用于查找一个条目的详细信息，通过每个条目唯一的标识符便可查询到该条目的名称、描述、所在的本体及同义条目。以条目GO:0006631为例，在加载GO.db包后，在R提示符下输入语句GOTERM$GO:0006631，便可看到该条目的基本信息如下：GOID: GO:0006631Term: fatty acid metabolic processOntology: BPDefinition: The chemical reactions and pathways involving fatty acids, aliphaticmonocarboxylic acids liberated from naturally occurring fats and oils byhydrolysis.Synonym: fatty acid metabolism从上述信息中可看到该条目属于BP本体，与脂肪酸的代谢过程有关。如要获得其父条目，可在R提示符下输入以下两条语句：x - as.list(GOBPPARENTS)和xGO:0006631，便可以获得如下结果：is_a is_a GO:0032787 GO:0044255返回结果说明条目GO:0006631有两个父条目，分别为GO:0032787和GO:0044255，此外条目上的“is_a”表明了父子条目之间的关系。4.1.3 存储各物种基因信息的包基因不像GO条目有统一格式的编