资源描述：
《基于调控范围语义相似性的致病基因预测方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
摘要摘要随着高通量实验技术手段的不断发展和完善，多种类型的分子生物学数据也在迅猛增加。比如基因序列数据、基因表达谱、功能注释、蛋白质相互作用关系、代谢路径以及基因调控通路等。基于复杂网络对高通量生物数据建模，运用计算方法从中挖掘致病基因已成为当前生物信息学研究热点之一。近年来，基于功能相关的基因导致相似疾病的生物学假设，涌现出了很多致病基因预测方法。这些方法通过识别网络中的稠密子图达到致病基因预测目的，倾向于研究拓扑关系连接紧密的致病基因。然而，生物学研究表明在人类已经发现的致病基因中有77.6%的为非必需致病基因，它们大多分布在基因网络的外围区域，并不是网络中的核心节点。因此，如何刻画拓扑关系连接稀疏的致病基因之间的关系，是致病基因预测有待解决的问题。另外，生物网络数据存在高噪声和假阳性等问题，而且人类生物过程是有方向性的，比如基因调控过程，这些因素在许多致病基因预测方法中是被忽视的。本文采用网络可控性的思想，提出了基于调控范围语义相似性的致病基因预测方法。由于基因调控网络可以有效刻画基因在疾病状态下的异常调控过程，因此基于该网络预测致病基因更加准确。运用调控范围度量基因在网络中的影响力，结合语义相似性计算候选基因导致疾病发生的概率，最终依据概率得分对候选基因排序。实验结果预测出LRP1是阿尔茨海默病潜在的致病基因，PRCK1与EGF是卵巢癌潜在的致病基因，并且发现拓扑关系弱的致病基因在调控范围上具有相似的生物功能，这表明调控范围语义相似性能很好地刻画非必需致病基因之间的关系。留一交叉验证结果显示本文提出的致病基因预测方法相比于PRINCE方法准确率提升了7.95%。关键词：致病基因预测调控范围语义相似性基因调控网络 AbstractAbstractWiththedevelopmentofhigh-throughputtechniques,varioustypesofmolecularbiologydataareincreasingrapidly,suchasgenesequencedata,geneexpressionprofile,functionalannotation,protein-proteininteraction,metabolicpathwaysandgeneregulatorypathwaysandsoon.Modelingthehigh-throughputbiologicaldataandminingdiseasegenesbyusingcomputationalapproacheshavebecomearesearchfocusinbioinformatics.Inrecentyears,alotofdiseasegenespredictionmethodshavebeenproposed.Mostofthemarebasedonthebiologicalhypothesisthatfunctionallyrelatedgenesoftenleadtosimilardisease.Thesemethodspredictdiseasegenesbyidentifyingdensegraphandtendtostudydiseasegeneswhichconnectclosely.However,biologicalstudieshaveshownthat77.6%ofhumandiseasegenesarenon-essentialdiseasegenes,mostofthemtendtoavoidhubsandsegregateatthefunctionalperipheryofgenenetworks.Therefore,howtodescribetherelationshipbetweennon-essentialdiseasegenesisanewproblemtobesolved.Inaddition,biologicalnetworkssufferfromhighnoiseandfalsepositive.Humanbiologicalprocessisdirectional,suchasgeneregulationprocess.Theyareignoredinmanydiseasegenespredictionmethods.Inthispaper,amethodforpredictiondiseasegenesbasedonsemanticsimilarityofregulationrangeispresentedbyusingnetworkcontrollability.Generegulatorynetworkpredictsdiseasegenesmoreaccurately,sinceitcaneffectivelyreflectthederegulationbetweengenesindiseaseconditions.Wemeasuregene’sinfluenceinthenetworkaccordingtotheregulationrange.Combiningregulationrangeandsemanticsimilarity,wecanscoreandrankcandidategenes.TheexperimentalresultspredictthatLRP1isimportantpotentialdiseasegenetoAlzheimer’sdisease,PRCK1andEGFareimportantpotentialdiseasegenestoovariancancer.Wefoundthattheweaktopologicaldiseasegeneshavesimilarbiologicalfunctiononregulationrange.Therefore,semanticsimilarityofregulationrangecanwellcharacterizetherelationshipbetweennon-essentialdiseasegenes.Theleave-one-outcross-validationresultsdemonstratethattheaccuracyofourmethodisimprovedby7.95%comparedwithPRINCE.Keywords:diseasegenespredictionregulationrangesemanticsimilaritygeneregulatorynetwork 目录i目录第一章绪论.....................................................................................................................11.1研究背景及意义.................................................................................................11.2研究现状.............................................................................................................21.3本文工作及组织结构.........................................................................................3第二章致病基因预测研究概述.....................................................................................72.1相关生物数据.....................................................................................................72.1.1生物医学文献...........................................................................................72.1.2蛋白质相互作用网络...............................................................................82.1.3基因调控网络...........................................................................................82.1.4功能注释...................................................................................................92.1.5基因表达数据...........................................................................................92.2致病基因预测相关方法...................................................................................102.2.1基于分类的方法.....................................................................................102.2.2基于直接邻居的方法.............................................................................112.2.3基于模块的方法.....................................................................................112.2.4基于网络传播的方法.............................................................................13第三章致病基因预测方法...........................................................................................153.1节点的控制范围...............................................................................................153.1.1网络可控性概念.....................................................................................153.1.2结构可控性定理.....................................................................................163.1.3最少输入与最大匹配.............................................................................193.2基因的调控范围...............................................................................................223.3语义相似性.......................................................................................................233.3.1语义相似性定义.....................................................................................233.3.2语义相似性的计算.................................................................................243.4致病基因排序算法...........................................................................................263.5本章小结...........................................................................................................28第四章实验结果与分析...............................................................................................294.1实验数据...........................................................................................................294.2结果验证及分析...............................................................................................294.2.1实验结果.................................................................................................304.2.2交叉验证.................................................................................................32 ii目录4.2.3参数分析.................................................................................................344.3应用案例分析...................................................................................................354.3.1阿尔茨海默病.........................................................................................354.3.2II型糖尿病..............................................................................................374.3.3白血病.....................................................................................................384.4本章小结...........................................................................................................39第五章总结与展望......................................................................................................41致谢.................................................................................................................................43参考文献.........................................................................................................................45 第一章绪论1第一章绪论人类基因组计划的完成获得了大量的离散数据。对数据的采集、存储、分析本身就存在着很多难题，另外还需从中挖掘出有用的生物信息，从而使人们了解疾病发生的机理，提高人们对疾病的预防、预测和治疗水平。本章首先介绍生物信息学和致病基因预测的相关背景知识，然后描述本文的主要工作及组织结构。1.1研究背景及意义诺贝尔奖获得者杜伯克于1986年在美国《科学》杂志上发表了一篇“癌症研[1]究的转折点：测序人类基因组”的文章，这篇短文提出要了解癌症的发生、发展、侵袭和转移机制，必须对人类细胞的基因组进行全测序。随后几年美国政府就正[2]式启动了人类基因组计划，其主要工作是：对人类和模式生物体的基因组测序，绘制图谱以及对基因进行识别。此计划一提出就以惊人的速度前进。随着人类基因组计划的顺利进行，生物学伴随着数学、计算机科学、信息学等学科的交叉融入，不断发展形成一门独立学科——生物信息学。生物信息学先[3]后经历了三个发展阶段：前基因组时代、基因组时代和后基因组时代。后基因组时代的来临使得生物信息学研究的内容更加广泛、具体和深入，同时也使一些生物技术能在农业和医学方面得到广泛应用，进而造福于全人类。伴随着后基因组时代的发展，产生了一些新的生物学词汇和概念，例如功能基因组学、比较基因组学、结构基因组学、蛋白质组学和药物基因组学等等，对这些领域的研究有助于人类理解和掌握生命的奥秘。功能基因组学是当前研究的核心和热点，重点在于研究基因组组成元素和注释重要元素的功能。基因及其产物之间相互关联作用实现生物体的各种功能，比较基因组学主要是对同一物种不同个体的基因组以及不同物种的基因组之间进行比较，这不仅有助于揭示生命的起源、进化，而且潜藏着巨大的社会效益，比如通过研究人类和细菌基因组的不同，从中找出细菌独有的基因，将其作为新的抗菌素的药物靶标。药物基因组学是后基因组时代的一项重要课题，旨在研究基因多型性和变异性如何影响药物效果。对药物基因组学的研究可以使病人在治疗前进行基因检测，依据结果对症施药，使得治疗更加安全可靠。近几年多种有成效的致病基因的预测方法相继出现，相应的干预疗法减少了人们的患病几率。与人类健康密切相关的研究，比如“个人基因组图谱”、“基因药物”以及“个性化治疗”等，仍然是未来生命科学研究的一个热点。在将来，随着后基因组学的发展，对疾病产生机理的研究将使医疗领域进入一个全新时代， 2基于调控范围语义相似性的致病基因预测方法对癌症、糖尿病、高血压等疾病的治疗，将不断从患病后低疗效、高成本的治疗方法转向患病前以预测疾病为依据的预防式治疗，这不仅具有潜在的实用价值，而且将会带来巨大的经济效益和社会效益。1.2研究现状基因是遗传信息的载体，人类的肤色等个体特征通过基因在亲代与子代之间进行传递，除了一些外伤，人类疾病几乎没有一种是完全非遗传的。虽然有许多疾病受环境因素和个体行为等因素的影响，例如感冒等，但在相同的外部条件下，不同的人得病的机率以及得病后表现的症状严重程度仍然是不一样的，这是由于基因在这一过程中起着作用。一些疾病是由单个基因的突变引起的，有些则是由[4]多个基因相互作用导致的。大多数单基因病是相对罕见的，而多基因相互作用的疾病是最常见的遗传性疾病，而且人们对其了解最少。对于人类遗传性疾病，科学家希望找出每种疾病的发病机制，寻找致病基因，并且制定出相应的药物，从而进行诊断、预防和治疗疾病，使人们摆脱疾病的痛苦。要从根本上防治疾病的产生，关键在于找出导致疾病发生的致病基因。依据人类基因组测序联盟的最新数据，人类大约总共有25000个基因，其中约七千个是致病基因，但目前已经发现的致病基因只有二千个，所以大部分的致病基因还[5]有待去发现。最早出现的致病基因预测方法，如连锁分析和关联研究，取得了显著的成效。然而，这些方法最后得到的关联基因组区域中基因的数量很大，大约在几百个左右，生物学家利用生物实验的方法来识别这些基因，即浪费时间，而且技术难度也很高。近几年随着基因组测序的发展，基于生物信息学分析的方法极大地降低了实验的成本，并且可以快速识别出候选基因，很大程度上减少了需要用生物实验逐一识别的候选基因数量。功能相关的基因往往导致表型相同或者类似的疾病，这是目前普遍接受的生[6]物假设。这些导致相同或类似表型疾病的基因，通常位于同一个生物模块中或[7][8]者位于同一个蛋白质复合体中，或者是在同一个代谢通路上。因此，模块性表示基因之间的关系与表型之间的相似性两者存在着正相关关系。基因和表型之间的这种二元关系为致病基因的预测提供了生物学依据，基于此生物学家研究了一系列有成效的致病基因预测方法。致病基因预测问题中广泛使用的数据有生物医学文献、蛋白质相互作用网络、基因调控网络、功能注释、基因表达数据等。由DNA控制蛋白质的合成来实现基因的表达，所以普遍认为基因和蛋白质是一一对应的关系。运用蛋白质相互作用关系以及基因-疾病的关联关系可以构建预测模型，对候选基因集进行打分排序，从中筛选出最有可能导致疾病发生的候选基因，进而为生物学实验提供精简的候 第一章绪论3选基因列表。致病基因预测方法的基本框架是：对于给定的某个疾病以及N个候选基因，通过某种模型计算所有候选基因与这个疾病的关联关系得分，再依据得分对候选[9]基因进行排序，排序越靠前的越有可能导致这个疾病发生。例如Lage等通过集成多种蛋白质相互作用网络，计算出表型相似性得分矩阵，由此达到致病基因预[10]测目的；Franke等基于构建基因相似性网络，结合蛋白质相互作用网络与疾病[11]表型网络，提出基于贝叶斯分类器的预测方法；Wu等整合蛋白质相互作用网络、表型相似性网络和疾病基因关联关系网络，建立了线性回归模型，利用向量相关性分析为每个候选基因计算得到一致性得分，最后依据打分对候选基因排序[12](CIPHER)；Köhler等考虑了整个网络的全局信息，提出从特定疾病的致病基因[13]开始在蛋白质相互作用网络中随机游走的预测方法；Vanunu等对随机游走算法进行了改进，提出了另一个基于网络传播的方法(PRINCE)。相比较于以前只考虑局部的算法，全局网络的相似性度量方法在致病基因预测方面更有优势。这些预测方法不仅有效提高了致病基因预测的准确率，而且加快了疾病研究的进程，为将来个性化治疗的发展奠定了基础。针对这些致病基因，医学家们可以研究出相应的治疗药物及措施，降低疾病的发生概率，减少疾病给人们带来的痛苦。1.3本文工作及组织结构目前的致病基因预测方法都或多或少存在一些缺陷，其中大部分是基于蛋白质相互作用网络的方法，而人类生理反应过程本身就是有方向性的，是动态变化的、不可逆的。许多复杂疾病的产生正是由人类正常的生理过程发生紊乱导致的，所以这种方向性是不可以忽视的。如图1.1所示为致病基因和必需基因的分布，能够接受转录因子插入的基因称为非必需基因，反之则为必需基因。如图a所示人类大约有25000个基因，其中有1665个必需基因和1777个致病基因，而在这些致病基因中有1379个非必需致病基因，即77.6%的为非必需致病基因。图b显示了致病基因与必需基因在基因网络中的分布情况，必需基因倾向于分布在网络中心，致病基因通常不是网络[14]中的核心节点，一般分布在网络的外围区域。 4基于调控范围语义相似性的致病基因预测方法[14]图1.1致病基因和必需基因的分布图1.2肺结核致病基因调控网络一个基因的表达出现异常会影响其他基因的正常表达，使人体生理过程发生紊乱，最终导致疾病的产生。基因调控网络是由各基因之间相互作用，相互制约的关系构成的复杂网络。如图1.2所示为肺结核致病基因的调控网络，其中深灰色节点表示的基因IFNG与IFNGR1为肺结核的致病基因，由图可以看出它们之间没有直接关联关系，而且相互之间是不可达的，运用以前的致病基因预测方法，很难识别出类似这种关系的致病基因。但是，可以发现它们调控的子网络中有5个公共基因，即图中浅灰色的节点，这5个基因都参与了小细胞肺癌的代谢通路。也就是说，IFNG和IFNGR1虽然相互之间没有任何直接关联关系，但它们调控的子网络具有相似的功能。本文在此分析的基础上，基于功能相似的基因导致相同或类似的疾病这一生物假设，提出了运用基因调控范围语义相似性的致病基因预测方法。首先基于复杂网络可控性思想，计算出基因调控网络中每个基因的调控范围。然后利用基因调控范围上的语义相似性计算得到基因之间的相似性，最后依据候选基因与已知致病基因的相似性预测其导致相同或类似疾病发生的概率，即为候选基因打分，最终根据打分进行排序。实验结果及分析表明调控范围语义相似性能更准确地刻画致病基因在网络中的关系，留一交叉验证结果显示该方法相比于PRINCE方法预测结果更加可靠。 第一章绪论5本文的组织结构安排如下：第一章为绪论部分，简要介绍本文的研究背景和意义，致病基因预测方法的研究现状以及论文的主要工作及结构。第二章是对致病基因预测研究的概述，主要介绍致病基因预测方法中经常用的生物数据及相关的预测方法。第三章详细阐述了基于基因调控范围语义相似性的致病基因预测方法，首先介绍基因调控范围的概念及计算方法，其次介绍语义相似性的概念及计算方法，最后给出具体的算法步骤。第四章为实验结果与分析，首先描述了实验中用到的生物数据，然后对实验结果进行分析与验证，最后对三种复杂疾病进行了案例分析。第五章为总结与展望，对本文的研究工作及存在的一些问题进行了总结，并明确后续所要进行的工作。 6基于调控范围语义相似性的致病基因预测方法 第二章致病基因预测研究概述7第二章致病基因预测研究概述致病基因预测问题的总体框架是：对于给定的疾病及候选基因集，其中候选基因集中包含已知的致病基因，通过某种模型赋予每个候选基因一个得分，尽量使得致病基因的得分最高，最后依据得分为候选基因排序，排名靠前的候选基因是潜在的致病基因。预测模型中使用的数据和算法都对实验结果有着重要的影响，最后由模型筛选出来的得分较高的候选基因，可以通过生物实验来验证。本章首先介绍致病基因预测中经常使用的生物数据，然后介绍一些相关预测方法。2.1相关生物数据致病基因预测方法是将有关表型特征的知识信息与基因之间直接或间接功能关系信息相结合，选出最有可能与疾病相关的候选基因。这些候选基因通常依据关联规则选出，有时也称之为“种子基因”，也就是说它们在某些方面与给定的疾病表型是相关的。利用生物信息学方法，可以应用不同的数据计算分析出最有可能的候选基因，例如生物医学文献、蛋白质相互作用网络、基因调控网络、功能注释以及基因表达数据等。这些生物数据已成功应用在致病基因预测的问题上，下面将详细介绍这几种不同的数据。2.1.1生物医学文献[15]无论是提供数以百万计的生物医学文摘的检索系统PubMed，还是包含数以千计的表型与致病基因描述的人类孟德尔遗传在线数据库OMIM(Online[16]MendelianInheritanceinMan)，都可以通过文本分类、信息抽取与自然语言处理技术从中挖掘出大量有用的知识信息。事实上，最早提出的致病基因预测方法就是采用生物医学文献的文本挖掘。这种类型的数据与基因/蛋白质之间的功能信息相结合，遗传学家可以手动评估出候选基因集，但这需要花费大量的时间。相反，如果利用计算的方法，只需要很少的时间就可以处理数百万的数据。这些全文本资源缺少对关键概念统一的组织或者描述，同样的一个概念可能会描述或命名为多种方式。例如，对于一个基因可能会有好几个别名。因此，对于文本数据处理需要依赖于受控词汇表，例如MeSH、UMLS、eVOC等将全文本的数据信息映射到定义明确的生物术语。虽然像PubMed这样的数据资源包含了有利于致病基因预测的、丰富的综合知识，但是这些信息偏向于功能研究充分的基因。 8基于调控范围语义相似性的致病基因预测方法2.1.2蛋白质相互作用网络蛋白质相互作用网络PPI(Protein-ProteinInteraction)代表网络中蛋白质之间的物理相互作用关系，是致病基因预测问题中最常用的数据。因为有相互作用的蛋白质之间通常有相同或类似的功能，只要其中的一个蛋白质发生了突变，就有可[6,17]能导致相似表型的发生。然而，大多数蛋白质网络只有少部分可靠的、已经充分研究证实的相互作用关系，大部分的相互作用关系都是通过实验技术得到的，例如质谱分析和酵母双杂交的方法，而这些实验方法依旧存在灵敏度和特异性的问题。另外，有时运用跨物种的蛋白质相互作用网络对实验推断的结果进行补充。目前广泛使用的，并且可公开获得的蛋白质相互作用数据包括人类蛋白质参[18]考数据库HPRD(HumanProteinReferenceDatabase)、在线预测人类蛋白质相互[19]作用数据库OPHID(Onlinepredictedhumaninteractiondatabase)以及检索基因/蛋白质相互作用的搜索工具STRING(SearchToolfortheRetrievalofInteracting[20]Genes/Proteins)，后两者不但包含已经验证过的相互作用关系，而且还包含预测的相互作用关系。但是，当前可用的基于实验方法得到的哺乳动物的蛋白质相互作用网络存在数据不完善、可靠性低的问题。2.1.3基因调控网络[21]基因调控网络是潜在的有利于致病基因预测的数据，但它同蛋白质相互作用网络一样，存在着数据的不完整和低质量的问题。图2.1基因之间调控关系示例基因调控网络是由基因之间有向调控关系组成的网络，如图2.1所示，基因a转录生成转录因子A,基因b转录生成转录因子B,转录因子A与B一起调控基因 第二章致病基因预测研究概述9c，那么在调控网络中基因a与基因b都和基因c有一条有向连边。基因调控网络可用于致病基因的预测，例如，一个转录因子调控几个已知的致病基因，那么生成这个转录因子的基因是致病基因的可能性较大。因为目前实验所证实的基因调控关系是比较少的，所以基因调控网络可以从其他类型的生物数据中得到，比如基因表达信息或者调控序列信息等。目前已有一些工具，运用调控序列信息，依据转录因子与mRNA的存在或缺[22-24]失来推断与疾病相关的知识信息。总之，在利用调控网络进行致病基因预测时，应该注意调控信息的确切来源以及它的可靠性。2.1.4功能注释广义上来讲，功能注释包括分子功能、生物进程、细胞元件，也是一个经常用来预测致病基因的数据。与2.1.1节中描述过的生物医学文献类似，这些信息也是偏向于功能研究充分的基因，而在这些数据库中仅仅小部分功能注释是被实验验证过的。虽然如此，如果一些预测的功能注释可以被模型物种所验证，那么它们也是可以利用的。在功能注释和代谢通路数据库中使用最广泛的分别是基因本[25]体论GO(GeneOntology)和京都基因和基因组百科全书KEGG(Kyoto[26]EncyclopediaofGenesandGenomes)。对差异表达的基因进行GO分析可以帮助研究人员对这些基因进行生物解释，探索基因的功能信息及基因之间的调控关系。除了已经提到过的数据库(GO,MeSH,UMLS,eVOC)，还有其他一些可用于致病基因预测以及注释基因与蛋白质的本体论。比如哺乳动物表型本体论[27]MPO(MammalianPhenotypeOntology)以及最近的人类表型本体论HPO(Human[28]PhenotypeOntology)。HPO不仅提供了超过1万条目的异常表型的受控词汇表，规范了有关疾病描述的概念，而且还解决了OMIM中层次结构不能反映条目间相[29]似性的问题。另外，基于UMLS的疾病本体论DO(DiseaseOntology),也常用于致病基因预测问题中。2.1.5基因表达数据基因表达数据反映的是直接或间接测量得到的基因转录产物mRNA在细胞中的丰度，利用这些数据可以分析得到表达出现异常的基因，基因之间存在哪种相关性以及在不同的条件下基因的活动是如何受影响的。通常利用基因表达系列分析SAGE(Serialanalysisofgeneexpression)、cDNA微阵列、寡核苷酸芯片等高通量实验技术，可以检测出细胞中mRNA的丰度。基于微阵列实验的基因表达数据在互联网上是公开发布的，到现在已经有很多研究机构建立了公共微阵列数据库。目前，最有影响的收集微阵列基因表达数 10基于调控范围语义相似性的致病基因预测方法[30][31]据的数据库有GEO(GeneExpressionOmnibus)、ArrayExpress和SMD(Stanford[32]MicroarrayDatabase)。表2.1为这三种数据库的简要介绍。表2.1基因表达数据库介绍数据库名称网址简介美国国家生物技术信息中心开发的目前最大且完全公开的高通量分子丰度GEOhttp://www.ncbi.nlm.nih.gov/geo/数据库，其中包含了12284个平台,1037304个样本,43254个系列。美国生物信息研究院EBI研究和开发的主要存储被充分注释的数据，包括ArrayExpresshttp://www.ebi.ac.uk/arrayexpress/多个基因表达数据集和与实验相关的原始图像集。数据库支持MGED组开发的MIAME的各种技术指标。斯坦福大学的微阵列数据库，主要存储微阵列实验的原始数据、归一化数据和SMDhttp://smd.stanford.edu/对应的图像文件，提供数据获取、分析和可视化的界面。不过SMD的实验数据大部分已加入GEO。基于基因表达数据的方法就是识别出对疾病有鉴别力的特征基因，这不仅可以揭秘疾病的发病机制，还可以提高对疾病的分类算法。但这类方法也存在一定的缺陷，一方面由于表达数据非常有限，其完整性和准确性存在着一定的问题；另一方面致病基因是由于其表达出现异常，导致整个代谢通路发生变化，。单纯依据表达数据的预测方法主要适用于与基因表达密切相关的畸形综合症类疾病，还不能对代谢类疾病等发病机制复杂的致病基因进行有效的预测。2.2致病基因预测相关方法上一节主要介绍了致病基因预测中常用到的生物数据，下面将分类阐述各种致病基因预测方法，分别是基于分类、直接邻居、模块以及网络传播的方法，这些方法的不同之处在于其用的生物假设及方法的具体实现。2.2.1基于分类的方法这类方法依据致病基因和非致病基因在部分特征上有很大的不同来预测致病基因，是典型的数据挖掘领域的算法，也就是二分类的问题。该方法的主要思想 第二章致病基因预测研究概述11是根据已知致病基因和非致病基因的差异特征训练得到一个分类器，然后用这个分类器对不确定的候选基因进行预测。[33]PROSPECTR方法选取的基因特征为基因长度、信号肽及cDNA长度，依据这些特征构建交替决策树，然后对测试数据集进行分类，预测其是否为致病基因。PROSPECTR方法分类的准确率达到了65%，这表明其分类效果是可靠的。基于分类的方法比较依赖于选取的基因特征，如果特征的选取不够准确，那[34]么预测的结果就不可靠。后来Xu又集成了功能注释，蛋白质相互作用数据等特征，训练得到K近邻分类器，结果从5262个基因中成功预测出178个可能的致病基因，更进一步提高了预测的效果。2.2.2基于直接邻居的方法这类预测方法的生物假设是：导致相同或者相似疾病的致病基因在网络中是直接相连的。基于这一假设，直接邻居的方法将已知致病基因的一阶邻居作为候选致病基因。这实质上是一种数邻居的策略：如果一个基因的附近有很多已知的致病基因，那么该基因就很有可能也是致病基因。[35]Oti等基于直接邻居的方法结合蛋白质相互作用网络及遗传疾病的遗传基因位点来预测致病基因。首先从某种疾病连锁区间中提取出候选基因，其挑选的依据是该候选基因是否与给定疾病的已知致病基因在蛋白质相互作用网络有连边。然后将这些候选基因映射到Ensembl数据库中查找其编码的染色体位点，如果位于遗传基因位点上，那么这个候选基因就是潜在的致病基因。最后作者应用OMIM数据库中包含至少两个致病基因的疾病对方法进行验证，结果在其预测的300多个致病基因中，有10%的致病基因可以被文献证据支持。然而基于直接邻居的方法具有一定的局限性。一方面，两个功能相关的基因在蛋白质相互作用网络中并不一定是直接相连的，它们可能在不同时刻参与同一个生物过程，但导致相同或者类似的疾病。另一方面，蛋白质相互作用网络存在很多噪声，有些遗传疾病的遗传基因位点是通过不完善的连锁分析得到的。基于直接邻居的方法更适合于预测在同一个蛋白复合体中的致病基因。2.2.3基于模块的方法模块性通常指的是复杂网络“内紧外松”的结构，也就是说，在一个模块内的节点彼此之间连接紧密，相反在模块外的节点相互之间连接比较松散。功能相关的基因导致相同或者类似的疾病，并且这些功能相关的基因通常在同一生物模块中。基于这一假设生物学家们提出了许多致病基因预测方法。1.贝叶斯分类器方法 12基于调控范围语义相似性的致病基因预测方法[9]Lage等创建了一个表型相似性网络来预测和疾病相关的基因。作者整合多种蛋白质相互作用网络数据，计算得出疾病之间的相似性分数，以此来进行与疾病相关的蛋白质复合物的识别以及致病基因的预测。对于一个给定的目标疾病，首先挑选出疾病连锁区间中的候选基因；然后将这些候选基因映射到蛋白质相互作用网络中，查找它们的网络邻居并设定一个阈值，将大于该阈值的关联关系保留下来，否则删除；最终构成了候选基因的复合体模块，如果它们的网络邻居是导致相似疾病的基因，那么根据贝叶斯模型计算得到的分数就较高。这类方法可以有效地提高致病基因预测的准确率，并且可以识别出以前未知的，潜在的和疾病相关的基因。但是，该方法存在一定的缺陷：一方面，如果一个候选基因是一个潜在的致病基因，但它却没有和任何一个已知的致病基因有相互作用关系，运用此方法就不能识别出来。另一方面，如果包含可能致病的候选基因复合体模块中不存在已知的致病基因，那么就不能预测出新的致病基因。2.回归模型方法[11]CIPHER方法基于导致相同或者相似疾病的基因通常位于相同的生物模块中这一假设，集成了蛋白质相互作用网络、表型相似性网络和疾病基因关联关系网络。该方法的步骤如下：1）将蛋白质相互作用网络、表型相似性网络、基因-疾病关系网络集成为一个单独的网络；2）从表型相似性网络中得到所有表型之间的相似性，构成表型相似谱；3）计算候选基因到蛋白质相互作用网络中所有已知致病基因的拓扑距离，得到基因之间的特征值向量；4）利用线性回归模型，计算表型相似谱与特征值向量的相关性，为每个候选基因计算出一致性得分；5）根据得分对候选基因排序。CIPHER方法从1444个连锁区间内成功预测出了709个致病基因，在计算基因之间相似性特征值时依据的是基因在网络中的拓扑距离，CIPHER方法提出了两种计算距离的方法，分别是直接邻居算法(CIPHER-DN)和最短路径算法(CIPHER-SP)。在候选基因组中，大多数的基因并没有与任何致病基因有直接关联关系，因此并不是所有的一致性得分可以通过CIPHER-DN算法计算得出。然而CIPHER-SP算法可以弥补这个缺陷，并且能够发现很少研究到的潜在的致病基因，所以主要用CIPHER-SP方法来预测致病基因。3.聚类方法[36]Sun基于模块性的假设提出了运用聚类算法来预测与疾病相关的基因簇。[37]作者首先分别采用了马尔科夫聚类算法MCL、模块发现算法MCODE、派系过[38]滤算法CPM识别出稠密的簇，并将其作为与疾病相关的候选基因簇，然后应用 第二章致病基因预测研究概述13多种生物特征（包括表型相似性，生物过程，分子功能及细胞组件）建立了一个对数似然模型，最后对每个候选基因簇打分，结果显示CPM的方法要优于MCL现MCODE方法。Sun提出的方法适用于识别包含在蛋白质相互作用网络模块中的致病基因，而对于那些存在于模块外的致病基因是无法预测的。2.2.4基于网络传播的方法以前的致病基因预测方法中忽视了一些未知的基因或功能不确定的基因，这些方法考虑的仅仅是候选基因或致病基因在当前网络中的局部信息。近几年基于传播或者随机游走的算法考虑到了这点，相比于以前的基于直接邻居或者最短路径的预测方法，全局网络相似性度量方法更适合用于预测候选基因与疾病之间的关系。基于网络传播的方法主要思想是从给定疾病的已知致病基因出发，在蛋白质相互作用网络中进行传播，最后状态达到稳定后根据候选基因的得分进行排序。1.GENEWANDERER方法[12]GENEWANDERER方法代替了以前的局部距离的方法，考虑了整个网络的全局信息，提出了在蛋白质相互作用网络中随机游走的算法。算法的思想是在网络中从已知的致病基因出发释放一个随机游走粒子，以一定概率游走到其邻居节点或者以一定的概率返回到自身，经过多次迭代达到收敛后，得到每个基因与已知的致病基因之间的拓扑相似性，最后根据这个相似性来预测候选基因与该疾病的关联关系。GENEWANDERER方法的形式化描述如下：tt10Pr(1)WPrP式(2-1)t其中W表示对蛋白质相互作用网络归一化后的马尔可夫概率转移矩阵，P表0示随机游走粒子在走了t步后，停留在候选基因上的概率，是个列向量，P表示t在初始时已知的疾病与基因的关联关系，即为先验知识。经过多次迭代使得P最终收敛，最后得到的就是候选基因与已知致病基因的相似性，得分高的排名靠前。2.PRINCE方法[13]PRINCE利用网络传播的算法对致病基因进行预测，对随机游走算法做了进一步的改进。对于给定的一个疾病，首先查找与其表型相似的疾病，将该疾病的致病基因和查找到的相似疾病的致病基因作为先验知识，在蛋白质相互作用网络中从这些基因出发传播到与其有相互作用的邻居节点，同时从邻居节点接收回网络流，重复这个过程直到网络中的每个节点接收的网络流收敛。最后根据接收到的网络流对候选基因进行打分排序。PRINCE方法的形式化描述为：tt1FWF(1)Y式(2-2)其中F表示候选基因与已知致病基因的相似性，Y是先验知识，W是蛋白质相互作用网络规范化后的矩阵。 14基于调控范围语义相似性的致病基因预测方法图2.2所示为PRINCE方法示意，给定需要预测的疾病Q，d1、d2、d3、d4、d5是与疾病Q表型相似的疾病，边的粗细代表相似程度的高低，边越粗表示其相似程度越高。p1~p11表示蛋白质，它们共同组成了蛋白质相互作用网络，连边越粗表示其相互作用关系更可靠。图中的虚线表示目前已知的蛋白质与疾病的关联关系，这样就将蛋白质相互作用网络与疾病相似性网络通过这些已知的关联关系构建成了疾病-基因网络。运用迭代的网络传播方法计算候选基因的得分，从已知的致病基因出发进行传播，在每一迭代中，蛋白质传播到其邻居节点，并接收来自邻居节点的网络流，蛋白质颜色越深代表其接收的网络流越高。图A表示网络初始状态，即先验知识。图B表示经过多次迭代之后，每个蛋白质接收到的网络流的情况，其中p5的颜色最深，表示它得到的致病信息最多，因此p5疾病Q最佳的候选基因。[13]图2.2PRINCE方法示例PRINCE方法与GENEWANDERER比较类似，但先验知识不一样，PRINCE增加了与疾病表型相似的致病基因。另外，这两种方法对蛋白质相互作用网络数据的处理方式也不一样，GENEWANDERER方法对矩阵中的每一列进行了归一化，而PRINCE方法规范化方式为：WWD/(i,i)(Djj,)式(2-3)ijij式(2-3)中D(,)ii表示节点i的度。相比较于以前的直接邻居或者最短路径等局部的算法，全局网络的相似性度量方法在致病基因预测方面更有优势。 第三章致病基因预测方法15第三章致病基因预测方法第二章详细介绍和分析了致病基因预测中常用到的生物数据和相关方法，这些方法能够有效刻画拓扑关系连接紧密的致病基因，然而对于拓扑关系稀疏的致病基因之间的关系模式有待进一步研究。基于此，本文提出了基于调控范围语义相似性的致病基因预测方法。基因调控范围的概念，是基于网络可控性思想提出的。本章首先阐述网络可控性及控制范围的相关知识，其次介绍基因调控范围的计算方法，然后介绍基因之间语义相似性的计算方法，最后描述具体的致病基因排序算法。3.1节点的控制范围现实中许多系统大多是非线性的，基因调控网络就是一个非常复杂的非线性系统，但非线性系统的可控性在结构上的许多方面是类似于线性系统的。因此通常将线性时不变系统的可控性理论应用于复杂网络控制中。3.1.1网络可控性概念给定一个线性时不变系统，如式(3-1)所示。dXt()AXtBUt()()式(3-1)dtT其中向量Xt()((),xt,xt())表示在t时刻系统中N个节点的状态，比如1Nx()t可以表示为通信网络中一个节点i在t时刻的通信量，或者是基因调控网络中i的转录因子浓度。Aa{}是系统矩阵，表示系统中各对象之间的连接关系以ijNN及它们之间相互作用的强度，比如通信链路上的流量或者调控关系的强度。Bb{}()MN是输入矩阵，表示节点与外部信号的连接关系，是控制量参ijNMT数。Ut()((),ut,ut())表示M个输入节点在t时刻的状态，b1表示信号1Mijut()施加到节点i上，b0表示信号末施加到节点i。jij方便起见，这里把原始的包含N个状态节点的网络记为GA()，在这个网络上再加入M个输入节点，新构成的这个网络称之为被控网络GAB(,)。如果对于任意给定的初始状态X(0)X和终止状态X都存在控制输入Ut()和有限时刻T使0f[39]得XT()X，那么就称式(3-1)描述的系统是可控的。依据卡尔曼可控性判据，f系统是结构可控的当且仅当其对应的可控性矩阵C是满秩的，即rankC()N。C的定义如式(3-2)所示。21NCB(,,ABABAB,,)式(3-2)如果至少存在一条从某个输入节点指向一个状态节点的边，那么这个状态节 16基于调控范围语义相似性的致病基因预测方法点就称为被控节点。不具有相同的输入节点的被控节点就是驱动节点，显然，驱动节点的数目就等于输入节点的数目，即为M。如果希望控制整个系统，首先需要确定输入节点集合，通过给这些节点输入不同的信号，就可以达到控制整个网络的目的。若原网络中的每一个节点都是驱动节点，那么就有MN，系统显然是可控的。现在的问题是：能不能找到最少的输入数N或者最少的驱动节点数，D使得整个网络系统是可控的。显然，对于大规模网络而言，采用蛮力方法直接检[40]验每一种控制方案是行不通的，而需要找到基于原始网络结构的有效算法。3.1.2结构可控性定理若矩阵A和矩阵B中的参数存在一组非零元素值，使得系统GAB(,)是可控的，那就称系统GAB(,)是结构可控的。若对于任意非零的参数取值，系统GAB(,)都是可控的，那么就称系统GAB(,)是强结构可控的。u1uuu111b1bbb111x1x1x1x1aa31a21a31a21a31a2121xa323x2xxx2x2ax23a32333x3图3.1判断结构可控性的简单示例为了对结构可控性有更加直观的认识，图3.1给出了一个包含3个状态节点和一个输入节点的简单的例子，并且假设输入只直接作用在一个状态上。下面分别列举出了这四种情形所对应的系统矩阵A、输入矩阵B和可控性矩阵C：系统(a)：000b1100Aa00;B0;Cba00式(3-3)211210000aa0a323221系统(b)：000b1100Aa00;B0;Cba00式(3-4)21121aa000003131 第三章致病基因预测方法17系统(c)：000b1100Aa00;B0;Cba00式(3-5)21121aa000aaa3133313331系统(d)：000b1100Aaa0;0BC;0baaa式(3-6)21231212331aa000aaa3132313221由此可以看出，在图3.1中，系统(a)和系统(c)，对于任意给定的非零参数，对应的可控性矩阵都是满秩的，因此它们是强结构可控的。对于系统(d)，当参数22选取满足aaaa时，系统是结构可控的。对于系统，它是不可控的，因为32212331不管参数如何选取，其所对应的可控性矩阵的秩都是为2。虽然系统(c)只比系统(b)在状态节点x处多条自回路，但这网络结构上的变化导致了系统可控性的改变。3为了深入了解控制理论中经典的结构可控性定理，这里引入一些图论的概念。[41]定义3.1不可达：有向图G中的一个状态节点称为不可达的，如果不存在从输入节点到达该状态节点的有向路径。[41]定义3.2扩张：有向图G包含一个扩张当且仅当存在有向图节点集合的一个子集S，使得指向集合S的节点的数目小于集合S中的节点数目，即TS()S。这里的TS()定义为直接有边指向集合S的节点的集合，即有TS(){|(vvv)EGvS(),}。显然，源节点（即输入节点）不允许属于集jjii合S，但可以属于集合TS()。[41]定义3.3干：是指源自于输入节点的一条简单路径，即经过的节点各不相同的路径。干的起点称之为根，终点称之为顶。[41]定义3.4芽：是指一个有向的简单圈C以及一条指向C中某一节点的边e。边e也称为芽的显著边。[41]定义3.5U根因子连接：是指一群节点不相交的干和基本圈的集合：如果这些干和圈的并可以生成网络G，那么就称这样的一个集合为U根因子连接。当且仅当有向图G没有扩张时，才存在U根因子连接。[41]定义3.6掌：掌是一个递归定义的子图。一个干是一个掌；给定一个干S0和一些芽B,,,BB，如果对每一个iil(1)，B的显著边的始点不是干S的12li0顶点，而是唯一一个同时属于B和SBBB的节点，那么i012i1SBBB是一个掌。节点不相交的掌的集合称为掌群。012l掌或者掌群，是既不包含不可达节点又不包含扩张的最小结构。换言之，去除一个掌中的任意一条边都会使其变为不可达或者扩张。 18基于调控范围语义相似性的致病基因预测方法x6x2xx45x3x1u1u2u3(a)原网络G(A)(b)被控网络G(A,B)xx66xx22x4x5x4x5xx33xx11u1u2u3u1u2u3(c)U根因子连接(d)掌群图3.2原网络、被控网络、U根因子连接和掌群图3.2为原网络、被控网络、U根因子连接和掌群的示意图。图中(a)是一个由20个状态节点所构成的网络；(b)是对应的被控网络，它在(a)的基础上增加了3个输入节点，这个网络中有5个被控节点，分别是x,,,,xxxx，3个驱动节点12345x,,xx（也可以取为x,,xx或者x,,xx）；(c)为被控网络的U根因子连接，其145245345中包括7个互不相交的干或圈；(d)为基于U根因子连接所得到的掌群，左边的掌由1个干和4个芽所组成，中间和右边的掌都是干。以上给出了图论中的一些基本概念，下面引入结构可控性定理。[42]定理3.1（结构可控性定理）以下三个陈述是等价的：(1)线性控制系统(,)AB是结构可控的。(2)有向图GAB(,)既不包含不可达节点也不包含扩张。(3)有向图GAB(,)是由掌生成的。对上述定理的直观解释如下：如果在一个系统中存在无法从外界输入到达的不可达节点，那么这个系统是不可控的，因为这说明外界输入无法影响这些不可达的节点；如果一个系统存在扩张，那么它也是不可控的。简单来说，一个扩张就是由相对较少的其他节点所“统治”的包含相对较多的节点的子图。在被控网络中，如果两个节点只能共享一个上级节点，那就无法独立地控制这两个节点。因此，为了完全控制一个网络，需要去除所有可能的扩张而且要保证每个状态节点都是从外界输入可达的。也就是说，每个状态节点必须有自己单独的“上级 第三章致病基因预测方法19节点”，这个“上级节点”可以是输入节点也可以是状态节点。3.1.3最少输入与最大匹配对于复杂网络来说，要验证卡尔曼可控性条件，需要知道每条边的权重，即a，ij但许多真实的网络边的权重是未知的（比如调控网络）或者只是近似知道（比如N互联网流量）。即使所有边的权重是知道的，但要计算可控性矩阵C的秩有21[40][42]不同的组合，对于大规模的网络，这个计算量相当大。Liu等应用Lin的结构可控论和最小输入理论进行分析，将网络中驱动节点的求解问题转化为有向图的最大匹配的求解问题。[41]*定义3.7匹配：有向网络GA()的边的子集M中任意两条边既没有公共的**始点也没有公共的终点，那就称M为一个匹配。如果一个节点是M中一条边的终点，那么该节点就称为匹配节点；否则，就称该节点是未匹配节点。[41]定义3.8最大匹配：匹配节点数最多的匹配称为最大匹配。如果网络中所有的节点都是匹配节点，那么称这个匹配为完全匹配。[41]定理3.2（最少输入定理）：完全控制网络GA()所需要的最小输入数目(N)t或者说驱动节点数（N）为：D*NNmax{NM,1}式(3-7)tD*其中M为网络GA()的最大匹配所对应的匹配节点数目。具体地说，如果网络GA()存在完全匹配，那么NN1，此时可选取网络中的任一状态节点为驱动tD*节点。另一种情况，如果网络GA()不存在完全匹配，那么NNNM，tD即为网络的任一最大匹配所对应的未匹配节点数目，此时驱动节点就是未匹配节点。对定理的证明如下：**第一种情形：如果网络GA()不存在完全匹配，即有M个匹配节点和NM个未匹配的节点。由匹配的边构成了基本路径和圈，将其称之为匹配路径和匹配*圈。对每一个未匹配节点都添加一个指向该节点的输入，从而构成NM个干。所有其他的状态节点都是由匹配圈生成的，对一个匹配圈C，如果存在一条边e，它的起点属于一个干而终点属于圈C，那么eC就构成了一个芽。对于那些不能以这种方式构成芽的匹配圈，可以用一个输入节点与其相连从而构成芽。无论怎样，匹配圈都不需要额外的输入节点来形成芽。所以，最终得到了一组不相交的*包括NM个输入节点的掌集。依据结构可控性定理，这样的系统是结构可控*的，并且驱动节点的数目为NM。*第二种情形：如果网络GA()存在完全匹配，那么就有MN。此时网络中所有的节点都是由一个或多个匹配圈构成的。只要额外引入一个输入，并把它与所有的圈相连以形成芽，然后将其中的任意一个芽改为干就得到一个掌，并且驱 20基于调控范围语义相似性的致病基因预测方法动节点的数目为1。对上述定理的理解可以概括为以下三点：(1)如果要完全控制一个网络，那么网络中的每一个节点都应该有指向它的“上级节点”。所以，输入节点的数目不应少于网络中不存在“上级节点”的数目，而最少输入的节点数是由网络的最大匹配所决定的。简单来讲，匹配节点都有“上级节点”，因此只需要对每一个未匹配节点施加控制就可以了。所以，原始网络的驱动节点集合就是未匹配节点的集合。(2)如果一个有向网络是强连通的，并且驱动节点的数目N为1，那么依据D结构可控性定理可以知道此网络中存在有向生成树，也就是说至少具有一个根节点的有向树，而其他的任一节点都可以从这个根节点沿着树的边到达。但是，即便是一个强连通网络具有有向生成树，并不能确保N1。因为强连通网络中可D能有多个扩张，从而需要多个驱动节点，而扩张的存在性与有向生成树的存在性是无关的。(3)添加更多的连边不会减弱系统的结构可控性。因此，最少输入定理对于有可能会丢失部分连边的实际网络（比如生物网络或者社会网络）也是有意义的，因为它给出的是所需要的最少输入的上界。有向网络GA()的最大匹配求解的一个有效方法就是将其转化为二分图的最[43]大匹配问题，而求解二分图的最大匹配可以采用经典的匈牙利算法。对于有向图GAGA():()(,)VE，其中Vxx{,,}表示有向图的节点集合，Ex{(,x)}AAN1ij表示有向图的边集，将其转换为二分图HAHA():()(,,)VV，其中AAVxx{,,}，Vxx{,,}，分别表示状态矩阵A的N行和N列的状态节A1NA1N点集合，{(x,x)}表示有向图的边集。根据匈牙利算法，求出有向图GA()的ij*最大匹配集M，其中最大匹配边指向的节点为匹配节点，没有指向的节点为未匹配节点，最终求得的未匹配节点即是网络中的驱动节点。表3.1给出了匈牙利算法的具体流程。表3.1匈牙利算法流程匈牙利算法输入：二分图的邻接矩阵G输出：最大匹配M算法步骤：1）置M为空2）从一个未匹配节点出发，找出一条增广路径P（即一条连通两个未匹配节点的路径，并且属于M的边与不属于M的边在P上交替出现），将P与M进行异或操作获得比原匹配边数更多的新匹配M，然后用M替换M。3）重复步骤2）直到将所有节点遍历完并且找不到新的增广路径为止。 第三章致病基因预测方法21如图3.3所示为求解驱动节点的简单例子，方便读者对其有更直观的认识。网络中包含16个节点。其中(a)图表示原始网络；(b)图表示将原始网络转换为二分图后的形式；(c)图表示运用匈牙利算法求出的二分图HA()的一种最大匹配；(d)图是将(c)图求得的最大匹配转化到原始网络中的子图，其中非匹配节点为VA节点集合中没有边指向的节点，即{,,}vvv，这三个节点即为驱动节点。11112v4vv159v10v3v16vv1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v1614v13v2vv87v12v11vvvvvvvvvvvvvvvv12345678910111213141516vv56v1(a)有向图GA()(b)二分图H()Av4vv159v10v3v16vv1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v1614v13v2vv87vv12vvvvvvvvvvvvvvvv1112345678910111213141516vv56v1(d)有向图GA()的一种最大匹配(c)二分图H()A的一种最大匹配图3.3有向图的驱动节点求解过程举例[44]定义3.9最少输入控制结构：最少输入控制结构是有向图GA()的子图，*记为CF:CF(,VMAL)，它的节点集合V同GA()的节点集合相同，边集为AA**MALE，是由有向图GA()的最大匹配集M和一些附加边集AL组成的，这些附加边的始点是除了干上的顶节点的其他节点，终点是芽上的节点。最少输入控制结构就是在求得有向图的最大匹配后，再增加一些从干（除去干上的顶节点）到芽的有向边。由最少输入控制结构组成的网络是结构可控的，其中既不包含不可达节点，也不包含扩张。图3.4为图3.3中有向图的一个最少输入控制结构，图中实线箭头表示的有向边是原网络的一个最大匹配，虚线箭头表示的有向边是附加边，节点vvv,,为驱动节点同时也是干上的节点。图3.4所11112示的有向图是结构可控的。 22基于调控范围语义相似性的致病基因预测方法v4vv159v10v3v16v14v13v2vv87vv1211vv56v1图3.4最少输入控制结构示例根据最大匹配算法可以求出有向图的最少输入控制结构CF，在一个CF中，每个节点都对应一个控制范围，下面给出具体的定义。[44]CFCF定义3.10控制范围：节点i的控制范围记为CR：CR{}{|ijjCF,ii且i到j是可达的}，是节点i与其在最少输入控制结构CF中可达的所有节点所组成的集合。控制范围是一个节点的集合，可以用它度量一个节点在有向网络中所影响的子网络的大小。3.2基因的调控范围上一节详细讲述了网络可控性的知识以及节点的控制范围概念，本文将其应用于基因调控网络中，并定义了基因的调控范围这一概念。基因调控网络中，每个节点代表一个基因，节点之间的连边代表基因之间的调控关系，根据网络可控性理论，可以求出每个基因的控制范围，它表示该基因调控子网络的大小。但是，对于一个有向图，它的最大匹配的边的数目是确定的，*但最大匹配的个数却不是唯一的。一个最大匹配M就对应一个最少输入控制结k*构CF。这些不同的最少输入控制结构组成一个集合，记为R。对于不同的最少k输入控制结构CF，节点i就有不同的控制范围CRCFk。基因调控网络中需要知道ki每个基因能够调控子网络的最大集合。基于此，下面给出基因调控范围的定义。*定义3.11调控范围：基因i的调控范围记为CR，它满足：i||CR*max{||CRCFk}式(3-8)ii*CFkRCRCFk表示基因i在第k个最少输入控制结构其中||CF中所调控的基因个数，也ik*就是集合的模，同理||CR。i图3.5为求解基因调控范围的简单示例，GA()表示包含13个基因的调控网 第三章致病基因预测方法23络，CF和CF表示两个不同的最少输入控制结构。在CF中基因g的控制范围为1211图中的虚线部分以及它本身，基因g的控制范围为它本身及它所指向的节点；而2在CF中两个基因的控制范围发生了很大的变化，基因g的控制范围变为它本身21及它所指向的节点，基因g的控制范围变为虚线部分以及它本身。因此最终求得2的基因g与g的调控范围，分别为CF和CF中的虚线部分再加上它们本身。可1212以看出，对于不同的匹配就有不同的最少输入控制结构，基因的调控范围就是在所有最少输入控制结构中基因控制范围最大的集合。gg2g2g11GA()CF1CF2图3.5基因调控范围的简单示例3.3语义相似性根据本章前两节的描述，可以计算出每个基因的调控范围，但这无法用来预测致病基因。调控范围大的不一定是致病基因，还需要根据候选基因与已知致病基因之间功能关系来进一步判断，而基于本体结构的语义相似性作为一种相似性的度量标准，能够很好地刻画基因之间的功能关系。3.3.1语义相似性定义基因本体(TheGeneOntology,GO)是基因本体协会提供的用于规范化地描述[25]所有基因以及基因产物属性的一个结构化标准词汇表。GO是一系列术语集，主要用来诠释真核生物体内的基因或者蛋白质在细胞中所扮演的功能角色，还有一些生物医学方面的知识。随着生物信息学的发展，GO术语也在不断累积、更新和改变。[25]GO由三大独立的本体构成：生物进程、分子功能以及细胞元件。例如，基因的产物色素c可以用分子功能术语氧化还原酶活性，生物进程术语氧化磷酸化和诱导细胞凋亡，细胞元件术语线粒体基质和线粒体内膜来描述。如图3.6所示为GO的结构示意图，GO采用有向无环图(DirectedAcyclicGraphs,DAG)的树状结构，它将每个本体相互关联起来，然后再以树状分层显现本体之间的关联关系，和分类树有些类似。在DAG中，节点表示术语，节点之间的连边表示术语 24基于调控范围语义相似性的致病基因预测方法之间的相似关系，包含“is-a”和“part-of”两种关系。“is-a”表示简单的包含关系，例如A“is-a”B表示A是B的一个子集。“part-of”关系则相对比较复杂，例如C“part-of”D表示如果C出现，那么它就肯定是D的一部分，但C不一定总会出现。GO本体适用于原核与真核生物，单细胞与多细胞生物。[45]图3.6GO结构示意在DAG中，从上到下，即从父节点到子节点，含义更详细更深入，换句话说，越往下层，术语表示更具体，节点所包含的信息量就更多。同时父节点包含了其所有子节点的含义。因此在利用GO注解时，应尽可能选择下层的术语。GO自建立到现在，对基因及其产物功能的研究具有深远的影响，被应用于生物信息学的各个领域，利用基因之间的功能相似性可以预测潜在的致病基因。GO结合其注入每个注解的特有结构特性，为基因产物功能比较提供了背景，基因产物之间的比较类型称之为语义相似性。3.3.2语义相似性的计算基因语义相似性通常是通过计算注解基因的GO术语间相似性而来的。每个基因产物可以由多个GO术语进行注解，通过计算注解每个基因产物中的术语对的相似性，然后把术语对相似性结合起来用于整体上测量基因之间的相似性。本[46]文采用的是Wang方法和BMA(Best-MatchAverageapproach)方法计算基因之间的相似性。Wang方法是Wang于2007年提出的术语语义相似性度量方法，BMA方法是最佳匹配平均方法。首先依据Wang方法计算得到基因术语对之间的相似性，其次运用BMA方法得到基因之间的语义相似性，下面具体介绍计算方法。首先利用Wang方法计算GO图中两个术语之间的语义相似性，GO术语A表示为DAG(,)TE，其中T表示术语A和它的所有祖先术语，是DAG中所有AAAAA 第三章致病基因预测方法25GO术语的集合，E为DAG中所有边的集合，即语义关系。Wang定义术语的语AA义值的计算方法为：SVASAt式(3-9)tTA其中SVA()表示GO术语A的语义，St表示的是每个祖先术语对A的语义A贡献。St的计算公式如下：ASAA1式(3-10)SAetmaxwSAt|tchildrenoftiftA其中01w表示两种术语关系的语义相似程度，childrenoft表示术语te的直接孩子节点。Wang通过大量实验得出“is-a”关系取值为0.8，而“part-of”则取值为0.6或者0.7。因此两个术语之间的语义相似性定义为：StStABtTTABSAWang,B式(3-11)SVASVB下面给出术语语义值与术语间语义相似性计算的实例。图3.7为GO术语IntracellularMembrane-boundOrganelle：0043231的有向无环图，其中包含7条术语和8个语义关系，图中的数字表示术语的编号，方便起见，下面用编号表示术语。[46]图3.7GO术语IntracellularMembrane-boundOrganelle：0043231的有向无环图为了计算术语0043231的语义值，首先根据式(3-10)计算出每个祖先术语对它的语义贡献，则S(0043231)1，由于术语0043231与术语0043229是“is-a”0043231关系，因此S(0043229)max{0.81}0.8，以此类推。表3.2列出了术语00432310043231的祖先术语对其的语义贡献值，根据式(3-9)术语0043231的语义值SV(0043231)为所有语义贡献值的和，即4.52。表3.3表示术语0043229的祖先术语对其的语义贡献值，因此根据式(3-11) 26基于调控范围语义相似性的致病基因预测方法可以求出0043231和0043229两个术语之间的语义相似性，即S(0043231,0043229)0.7727。Wang表3.2术语0043231的祖先术语对其的语义贡献值GO术语0043231004322900432270005622000562300432260005575语义贡献值10.80.80.480.2880.640.512表3.3术语0043229的祖先术语对其的语义贡献值GO术语00432290005622000562300432260005575语义贡献值10.60.360.80.64以上给出了基于GO术语之间的语义相似性计算方法，其次利用最佳匹配平均BMA方法计算基因之间的语义相似性。给定两个注解基因g和g的术语集合12GO{,gogogo}和GO{,gogogo}，则基因g和g之间的语义相111121m221222n12似性计算公式为：mnmaxSwang(gogo12i,j)maxSwang(gogo12i,j)11jnimij11GOSim(,)gg式(3-12)BMA12mn3.4致病基因排序算法在3.2和3.3节中已经详细介绍了基因的调控范围和基因之间语义相似性的计算方法，调控范围可以反映基因在网络中的影响力，而语义相似性可以衡量基因在功能上的相似程度，本节结合这两个指标来进行致病基因的预测。定义3.12：基因调控网络GRN(GeneRegulatoryNetwork):GRN(,VE),其GG中Vggg{,,}表示基因集合，g表示第i个基因，N为基因的个数；12NiEg{(,gV)}V表示基因之间的调控关系集合，(,)gg表示基因g到基因GGijijig有一条有向边，即g调控g。jij定义3.13：疾病基因网络DGN(DiseaseGeneNetwork):DGN(,,VDE),DG其中V与GRN中的V相同，表示基因集合；Dddd{,,,}表示疾病集合，d12Mi表示第i种疾病，M表示疾病的种类；Eg{(,dV)}D表示已知的致病基DGij因与疾病之间的关系集合，(,)gd表示基因g导致疾病d的发生，是无向的。ijij基因调控网络GRN是有向图，其中基因之间的关系是多对多的，一个基因可以调控多个基因，同时它也可以被多个基因调控。疾病基因网络DGN是一个无向的二分图，其中基因与疾病之间的关系也是多对多的，一个基因可以导致多种疾病的发生，一种疾病的发生也可以由多个基因导致。下面给出方法的具体步骤。首先，根据式(3-8)，式(3-12)分别计算GRN中每个基因的调控范围和基因之 第三章致病基因预测方法27间的语义相似性，最后得到基因调控范围的邻接矩阵以及语义相似性的对称矩阵，*分别记为CR，GOSim。NNNN其次，结合基因的调控范围和基因之间的语义相似性，根据式(3-13)采用最佳匹配方法得出基因之间的相似性。max**GOSimgg(,ij)maxGOSimgg(ji,)gCR**gCjgR21gCRgCigRig12jgsimgg(,)式(3-13)12**CRCRgg12最后，在疾病基因网络DGN中，依据基因-疾病关系以及候选基因与已知的致病基因之间的相似性来计算其导致疾病发生的概率，即对候选基因进行打分，计算公式如下：p(,)max{(,)}gdsimgg其中(,)gdE式(3-14)ijikkjDG式(3-14)中基因g为候选基因，基因g为基因d的致病基因，由此得到候选基因ikj与疾病的概率矩阵Pg{(,d)}。对于每种疾病d，都有候选基因的得分排名，ijNMi根据得分对候选基因排序，从中筛选出排名靠前的候选基因即为可能的致病基因。表3.4给出了致病基因预测排序算法步骤。表3.4基于调控范围语义相似性的致病基因排序算法致病基因排序算法输入：基因调控网络GRN与疾病基因网络DGN输出：不同疾病候选基因的打分排名P算法步骤：*1)由式(3-8)与式(3-12)分别计算出基因的调控范围CR与基因之间的语义相似性NNGOSimNN2)结合调控范围与语义相似性由式(3-13)计算出所有基因之间的相似性3)由pg(,)max{(,)}dsimgg计算出候选基因导致目标疾病发生的概率，最后ijik根据概率值进行打分排序得到P如图3.8所示为致病基因预测方法的流程示意。首先，依据复杂网络的可控性概念，计算出基因调控网络中每个基因的调控范围，如图中虚线部分别为基因g和g的调控范围，并依据Wang方法计算得到基因之间的语义相似性；其次，12利用基因之间调控范围区域中的语义相似性计算得到基因之间的相似性，如图中第二步所示为计算公式；最后，依据候选基因与已知致病基因之间的相似性来预测其导致相同或类似表型疾病发生的概率，即为候选基因打分，最终根据打分进行排序。在本文工作中，运用调控范围度量基因在网络中的影响力，结合语义相似性可以有效地刻画致病基因之间的关系。 28基于调控范围语义相似性的致病基因预测方法图3.8致病基因预测方法流程3.5本章小结本章主要描述了基于调控范围语义相似性的致病基因预测方法，首先介绍网络可控性的基础理论知识，其次详细阐述了基因调控范围和语义相似性的计算方法，最后给出预测算法的具体步骤和流程。 第四章实验结果与分析29第四章实验结果与分析在第三章中详细介绍了基于调控范围语义相似性的致病基因预测方法，本章主要为实验部分。首先介绍实验仿真采用的生物数据；其次介绍实验结果，并分析验证算法的可行性与有效性；最后针对三种典型的复杂疾病分别做具体的案例分析。在实验中，算法的实现是由C++，MATLAB以及R语言共同实现完成的。4.1实验数据实验中用到以下两个数据作为算法的输入：(1)基因调控网络；(2)疾病与基因的关联关系网络。[47]基因调控网络：实验中的基因调控网络是由Backes等构建的KEGG人类调控网络，这个调控网络来源于生化网络数据库BNDB(BiochemicalNetwork[48]Database,http://www.bndb.org./)。BNDB集成了各种生物网络数据，在BNDB中，一条通路由一系列的事件组成，每个事件的参与者可以是基因或蛋白质，它们扮演不同的角色，可以是产物或者底物。作者将所有的参与者以及事件构建成调控网络，其中参与者也就是基因作为网络中的节点，基因之间的调控关系作为网络的边。由此得到由2010个节点（基因），10234条边（调控关系）组成的基因调控网络，它包含了像KEGG癌症代谢通路的所有KEGG调控通路。由于后续要计算基因之间的语义相似性，而2010个基因在GO中已经有功能注释的只有1579个，所以最终取得由1579个基因组建的基因调控网络，其中包含76307个调控关系。[49]疾病与基因关联关系网络：实验中的疾病基因关系网络来源于Goh等构建的疾病与基因的关联关系网络，作者将OMIM(http://www.ncbi.nih.gov/omim)中表型与基因的关系数据进行分类，将表型相似的疾病归为一类，最后得到疾病与基因的相互关系网络。根据Goh构建的这个网络，在上述基因调控网络中查找与疾病相关的致病基因，从找到的结果中筛选出符合一个疾病的致病基因多于两个的数据，最后选出了252个已知的致病基因，它们与112个疾病有366种关联关系。最终由252个基因与112个疾病构建了一个疾病与基因相互关系的二分图，即疾病与基因关联关系网络。4.2结果验证及分析本节将基因调控网络，疾病与基因的关联关系网络作为算法的输入，对实验进行仿真，最后得到致病基因的预测结果。下面首先介绍实验结果，其次利用致 30基于调控范围语义相似性的致病基因预测方法病基因预测中常用的留一交叉验证对算法进行评估，最后对算法中的参数作简要分析。4.2.1实验结果1.基因调控范围语义相似性计算结果对于4.1节中介绍的实验数据，计算出所有基因之间的调控范围语义相似性。如图4.1所示为最后计算所得的基因之间的相似性分布图。为了分析拓扑关系较弱的致病基因之间的关系，通过实验得到当取0.3为阈值时，选取出来的基因可以尽可能去除那些非致病基因，并且使得拓扑关系弱的致病基因最多。最终筛选出与20种疾病有关联关系的31个致病基因，它们在原调控网络中没有直接关联关系，但通过调控范围语义相似性可以刻画出它们在调控网络中的关系。图4.1基因相似性分布如表4.1所示为3种疾病致病基因的调控范围例子，其中第一列表示疾病，分别是血小板增多症、免疫缺陷以及分枝杆菌感染，第二列为三种疾病的致病基因，第三列为致病基因的调控范围，第四列表示致病基因调控的基因个数，第五列表示致病基因在调控范围上具有的相似功能。三种疾病的致病基因虽然在调控网络中相互之间不可达，但根据本文提出的方法计算出其各自的调控范围，再利用语义相似性的计算方法计算致病基因调控范围上的语义相似性，发现这些致病基因所调控的基因都存在着共同的功能，它们分别为Janus酶信号传导与转录活化因子的通路、先天性免疫缺陷疾病的代谢通路以及细胞凋亡。简言之，致病基因虽然在调控网络中拓扑关系比较弱，但在调控范围上却有相似的功能。运用以前的算法计算这类已知致病基因之间的相似性很低，而基于 第四章实验结果与分析31调控范围语义相似性的方法能够更准确地度量它们之间的关系。因此，该方法可以很好的刻画致病基因在网络中的关系模式，进而可以采用这种相似性有效地预测致病基因。表4.1三种疾病致病基因的调控范围疾病致病基因调控范围个数相似功能JAK3、STAT1、SOCS1、IL20RB、TPOTYK2、STAT4、SOCS4、9CSF2RB、BAX血小参与Janus酶信号传STAT1、SOCS1、JAK3、IL20RB、板增JAK27导与转录活化因子STAT2，SOCS7、CRLF2多症的通路JAK3、STAT1、SOCS1、IL20RB、MPLTYK2、STAT4、SOCS4、9CSF2RB、BAXZAP70、CD3D、CD3Z、NCR3、CD3EFCER1G、NCR1、FCER1A、9与先天性免疫缺陷免疫MS4A2、FCGR3疾病的代谢通路有缺陷ZAP70、CD3Z、NCR3、关CD3GFCER1G、NCR1、FCER1A、8MS4A2、FCGR3分枝IL20RB、TNFSF10、IFNGR25杆菌TNFRSF10B、CASP8、BID共同参与细胞凋亡感染IFNGR1IL20RB、FAS、FADD、CASP1042.预测结果对于给定的目标疾病，依据候选基因与导致该疾病发生的基因之间的相似性来为其打分，最后根据打分对候选基因进行排序。本文实验对112种疾病都做了预测，表4.2分别显示了阿尔茨海默病(AlzheimerDisease)，乳腺癌(BreastCancer)与结肠癌(ColonCancer)的预测结果，可以看出已经致病基因的排名都是靠前的，但也有候选基因排在已知致病基因前面的。112种疾病的预测结果中总共有5个候选基因的排名比较靠前，表4.3列出了这5个候选基因，它们所对应的疾病分别是阿尔茨海默病(AlzheimerDisease)、淀粉样变病(Amyloidosis)、结肠癌(ColonCancer)与卵巢癌(OvarianCancer)。这5个候选基因中基因低密度脂蛋白受体1(即LRP1)在水解β-淀粉样蛋白的过程中起着关键的作用，而β-淀粉样蛋白的累积、[58]聚集和沉淀是促使阿尔茨海默病产生的一个原因；基因PRCK1全称为proteinkinaseC-alpha,利用siRNA（小干扰RNA）降低PRCK1的表达可以克服卵巢癌的[50]化疗耐药性；基因EGF全称为epidermalgrowthfactor，可以在治疗COX-1阳[51]性卵巢癌时增强药物的治疗效果。 32基于调控范围语义相似性的致病基因预测方法表4.2三种疾病致病基因的排名情况（1）阿尔茨海默病基因排名基因排名基因排名APP7PLAU4A2M2NOS35PSEN13APOE1（2）乳腺癌基因排名基因排名基因排名CDH16TP534ATM2PIK3CA5PPM1D3RAD531（3）结肠癌基因排名基因排名基因排名CTNNB119PIK3CA16TP539AXIN22SRC3TGFBR24APC1NRAS7BAX18CCND15BRAF6PLA2G2A10EP30013DCC14FGFR317BUB112BUB1B11BCL108表4.3排名靠前的5个候选基因疾病基因排名阿尔茨海默病LRP16淀粉样变病APBB11结肠癌PECAM115卵巢癌PRKCA4卵巢癌EGF5实验结果中虽然有5个候选基因的排名比已知致病基因的排名靠前，但其中有3个基因已经被最新的文献验证它们与疾病的发生有直接或间接的关系。因此实验结果说明依据基因调控范围上的语义相似性来度量基因之间的相似性是可靠的，而且用这个方法来预测致病基因是有效的。4.2.2交叉验证为了定量的评估一个预测方法的效果，通常利用已知的基因与疾病的关系经[52,53]过交叉验证来实现。交叉验证亦称循环估计，是用来验证分类器性能的一种统计分析方法，其基本思想是对原始数据进行分组，将其中一组作为训练集，另一组作为验证集，首先用训练集对分类器进行训练，其次利用验证集来测试训练得到的模型，以此作为评价分类器的性能指标。常见的交叉验证方法有三种：Hold-Out验证、k折交叉验证(K-foldCrossValidation,K-CV)和留一交叉验证(Leave-One-OutCrossValidation,LOO-CV)。 第四章实验结果与分析33对人类疾病基因预测进行交叉验证时，常用的是留一交叉验证，即每次隐去一个已知的基因与疾病的关系作为测试，假设这部分关系未知，而使用预测方法来实现。由于本实验中已知的疾病与基因关系并不多，而且数据要求的是致病基因超过（包含）2个的疾病，所以采用留一交叉验证，另一方面，留一交叉验证也比较可靠。致病基因预测研究中最为常用的综合评价指标包括平均排名AR(averagerank)，浓缩率(foldenrichment)，AUC(AreaunderROCcurve,即ROC曲线下的面积)，以及准确率(Precision)与召回率(Recall)等。假设K个已知的致病基因与疾病的关系，为每一个关系构建一个测试基因集，包含已知的致病基因与相对应的N-1个其他的候选基因。这样进行交叉验证将进行K次测试，每次产生N个候选基因的排序。假设第i次测试中致病基因排在第r(0
