《基于本体与基因网络的致病基因预测研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
硕士学位论文基于本体与基因网络的致病基因预测研究RESEARCHOFDISEASEGENEPREDICTIONBASEDONONTOLOGYANDGENENETWORK白坤哈尔滨工业大学2015年12月 图内图书分类号：TP39学校代码：10213国际图书分类号：004.9密级：公开工学硕士学位论文基于本体与基因网络的致病基因预测研究硕士研究生：白坤导师：王亚东教授申请学位：工学硕士学科：计算机科学与技术所在单位：深圳研究生院答辩日期：2015年12月授予学位单位：哈尔滨工业大学 ClassifiedIndex:TP39U.D.C:004.9DissertationfortheMasterDegreeinEngineeringRESEARCHOFDISEASEGENEPREDICTIONBASEDONONTOLOGYANDGENENETWORKCandidate:BaiKunSupervisor:Prof.WangYadongAcademicDegreeAppliedfor:MasterDegreeinEngineeringSpeciality:ComputerScienceandTechnologyAffiliation:ShenzhenGraduateSchoolDateofDefence:December,2015Degree-Conferring-Institution:HarbinInstituteofTechnology 摘要摘要随着人类基因组计划的顺利完成，出现了许多高通量技术预测基因功能的方法，但是从这些方法产生的大量的候选基因集合中检测致病基因仍是一个十分艰巨的挑战，如果直接使用生物学实验验证则需要消耗大量人力物力。随着数据的积累，人们逐渐发现致病基因具有模块性，功能相同或者相似的基因编码的蛋白质，在蛋白质相互作用网络中相互靠近。利用已被证实的疾病和基因的关系，使用计算方法来预测候选致病基因通常能起到很好的效果，如计算候选基因和已知致病基因集合中的基因的相似性，然后根据相似性排名对候选基因进行排序，从而使生物学实验有针对的对基因进行实验验证，降低检测成本。本文主要以生物医学本体为中心，整合了九种不同生物医学数据库，构建了由78786个生物学实体或概念组成的一个双层异构网络，这个网络中包含本体术语之间的105875条有向边，以及术语到基因，基因和基因之间组成的398642条无向边。在构建网络时，使用超级叙词表等映射工具对九种数据库中不同类型的标识进行转换和去冗余；设计了一套整合不同关系证据类型的方案，根据边的关系证据集合的不同，为每条边赋予了不同的权值，最终构建的网络为带权的双层异构网络。依据网络中边的端点的不同，将边分为了七个大类，并验证了每一类的权值改变对基因预测最终的效果有直接影响，为每大类属于的边设置了一个特征向量，使用有监督的随机游走训练每个大类的特征权值，使得组合的权值能够更准确的进行致病基因预测，同时基于有监督随机游走算法，提出了拉普拉斯正规化的有监督随机游走，并在多次试验后验证了正规化的有监督随机游走在预测权值上优于有监督随机游走，针对正规化算法复杂度过高的问题，提出了简化版的正规化有监督随机游走。在构建的双层异构网络上分别进行随机游走，有监督随机游走，简化正规化随机游走的验证，最终有监督随机游走的AUC（AreaUnderrocCurve）比普通随机游走提高了0.8%，正规化随机游走AUC比普通随机游走提高了2.3%。关键词：本体；数据融合；致病因预测；随机游走；有监督随机游走；拉普拉斯正规化-I- AbstractAbstractAlthoughthehumangenomeprojecthasbeenaccomplishedandhasachievedgreatsuccess,andnewmethodsthatverifygenefunctionwithhigh-throughputhavebeenapplied,studyinggeneticproblemsthatinducediseasesisstilloneofthemajorchallengesfacinghumanity.Usingthebiologicalexperimentmethodtoidentifygenesassociatedwithdiseaserequiresalargenumberofhumanresourcesandcapitalsupport.However,thestudyofcandidateassociationworkswellbyusingasetofknowfunctionalcandidategenes,becausenewdiseasegenesclusterwiththesetofknowndiseasegenesintheprotein-proteininteractionnetworkinthemostofcases.Manycomputationalmethodsusethisruletocalculatethecandidategenesfunctionalsimilaritywithknowndiseasegenes,thenrankingthecandidategenewiththesimilarityscores.Guidingbythisrankinglist,biologicalexperimentcanuselessexpensetoachievelargeoutput.Inthiswork,weconstructatwo-layerheterogeneousnetworkwithbiomedicalontologiesandothersixdatabases.Thenetworkhas78,786vertexesofbiologicalconception,105,875directededgesfromontologyterms,and398,642undirectededgesfromontologytermstogenesandgenestogenes.Inordertogetlessredundancyinournetwork,weusemappingtoolssuchassuperthesaurustounifythedifferentidentifierindifferentdatabases.Sincetheedgeshavedifferentevidencecodesinmostcases,wedesignascoringmethodtocombinethedifferentevidencescodes.Finally,webuiltaweightedtwo-layerheterogeneousnetworktopredicteddiseasegenes.Basedontheedges’endpointshavedifferenttypes,wemanualclassifiedthembyseventypes.Changingeachedgetype’sweightcandirectlyimpactthefinallyrankinglist.Byusingsupervisedrandomwalk(SRW),eachedgetypecangetatrainingweight,whichcanimprovethegenepredictionresults.Thenwemodifythesupervisedrandomwalkbylaplaciannormalization(LN-SRW),duetothelongexecutingtimeofLN-SRW,asimplelaplaciannormalizationsupervisedrandomwalk(SLN-SRW)hasbeenputforward.Inthesyntheticscalefreenetwork,LN-SRW,SLN-SRWoutperformanceSRWwithlessabsoluteerrors.ThenwecomparetheoriginalrandomwalkwithSRWandSLN-SRWintheheterogeneousnetwork,theAUC(AreaUnderrocCurve)valueforrandomwalkis76.9%andSRWAUCvalueincreasedby0.8%,SLN-SRWAUCvalueincreasedby2.3%comparewiththeoriginalrandomwalkalgorithm.Keywords:ontology,datafusion,diseasegeneprediction,randomwalk,supervisedrandomwalk,laplaciannormalization-II- 哈尔滨工业大学工学硕士学位论文目录摘要...............................................................................................................................IABSTRACT....................................................................................................................II第1章绪论.................................................................................................................11.1课题研究背景及意义........................................................................................11.2国内外研究现状...................................................................................................21.3本文主要研究内容及组织结构...........................................................................41.3.1主要研究内容.................................................................................................41.3.2本文组织结构.................................................................................................5第2章致病基因预测方法概述...................................................................................62.1致病基因预测的主要流程...................................................................................62.2致病基因预测的主要方法...................................................................................72.2.1基于分子和网络特征分类的方法.................................................................72.2.2基于网络节点相似度排序的方法.................................................................82.3本章小结..............................................................................................................11第3章本体基因数据整合和网络构建.....................................................................123.1引言.....................................................................................................................123.2生物医学本体数据整合.....................................................................................133.2.1本体论概述...................................................................................................133.2.2生物医学本体格式和关系抽取...................................................................143.2.3本体注释.......................................................................................................183.2.4疾病表型与基因关系数据...........................................................................193.2.5基因与基因关系数据...................................................................................213.3本体与基因网络构建.........................................................................................213.3.1统一标识映射...............................................................................................213.3.2证据整合和网络构建...................................................................................233.4本章小结.............................................................................................................26第4章基于有监督随机游走的致病基因预测.........................................................274.1引言.....................................................................................................................274.2随机游走模型概述.............................................................................................274.3有返回的随机游走.............................................................................................284.4有监督随机游走.................................................................................................294.5拉普拉斯正规化的有监督随机游走.................................................................32-III- 哈尔滨工业大学工学硕士学位论文4.5.1基本原理.......................................................................................................324.5.2算法实现.......................................................................................................344.6加权有监督随机游走的致病基因预测.............................................................364.7本章小结.............................................................................................................38第5章实验结果与分析.............................................................................................395.1改进的有监督随机游走有效性验证.................................................................395.2实验环境与实验数据.........................................................................................415.3实验结果验证方法和正负例生成.....................................................................425.4实验结果.............................................................................................................435.4.1重启概率的选择...........................................................................................435.4.2实验结果对比...............................................................................................455.5本章小结.............................................................................................................47结论.............................................................................................................................48参考文献.........................................................................................................................49哈尔滨工业大学学位论文原创性声明和使用权限.....................................................53致谢.............................................................................................................................54-IV- 哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题研究背景及意义自1990年人类基因组计划启动以来，计算机处理能力不断提高、存储空间的不断变大，分布式系统被广泛应用，分子生物医学中下一代高通量测序、蛋白质互作网络、微小RNA测序、代谢产物和路径的识别和发现等技术愈加完善，相关的医学文献和医学数据资源正呈爆炸式增长。但是，大量的生物数据往往源自不同的研究者和组织机构，在不同阶段，为了特定的用途而建立的。由于数量庞大，数据存储方式迥异，且存在语法、语义、模式等异构现象，形成了一个个的信息孤岛，使生物学家搜索获取相关信息的时候遇到越来越多的困难。亟需定制统一的数据模型和语义关系，来方便科研人员查找和获取有意义的信息。为了解决这个问题，生物学家参照哲学中的本体理论（Ontology）和其它的规范，首先建立了基因本体（GeneOntology,GO）[1]和疾病本体（DiseaseOntology,DO）[2]等。而后建立了UniProKB[3]蛋白质数据库、蛋白质家族数据库、疾病数据库，基因变异数据库，药品和表型数据库等。考虑到这些人工制作的数据库因为制作人员地域和文化的不同，一个生物学概念（BiologicalEntity）的命名有可能出现多个别名。为了统一生物医学中概念的命名方式，美国国立医学图书馆（NationalLibraryofMedicine,NLM）设计了一体化医学语言系统（UnifiedMedicalLanguageSystem,UMLS）[5]，UMLS旨在通过帮助能够处理生物医学知识的软件系统的开发，加强对于这些文献和资源的获得和使用。在这些生物医学概念定义后，科研人员制作了更多的注释（Annotation），关联型的数据库，这类数据库主要记录的是本体和一些生物医学概念的联系。比如STRING（SearchToolfortheRetrievalofInteractingGene/Proteins）[6]蛋白质互作网络记录的是蛋白质之间的关系，GOA（GeneOntologyAnnotation）[7]记录的是基因功能和蛋白质的注释，KEGG（KyotoEncyclopediaofGenesandGenomes）[8]记录的是基因，化合物，蛋白质，代谢通路之间的关系。有了生物医学概念和他们之间的关系的数据之后，人们开始利用这些数据构建了一些复杂的网络模型，来帮助研究人员更好的获取信息。因人力所限，生物医学概念间的各种关系到现在为止被发现的也只是冰山一角，怎样根据已知的概念间的关系，来预测未知的关系，或者给生物学家一些线索，让他们在设计实验验证概念间的某种关系的时候有所倾斜，从而加快实验的进展，是当前生物信息学研究人员关注的方向之一。整合生物学数据库，构建蛋白质，基-1- 哈尔滨工业大学工学硕士学位论文因和生物学概念网络，使用来自多个数据源的数据，帮助研究人员发现疾病和遗传基因的关系，预测疾病相关基因，并解释发病机理，辅助基因诊断和帮助遗传类疾病治疗都具有重要意义。与此同时，新的致病基因的发现，对新药研发也起着推动作用，有较高的经济效益。目前具有致病基因的疾病占疾病总数的四分之一，多数疾病相关的致病基因还未能被人们发现，传统的致病基因检验需要花费大量的人力物力，利用现有的数据进行致病基因的预测，提高致病基因的检验效率是目前生物信息学研究的热门。1.2国内外研究现状遗传类疾病常常由单条或多条基因的某些突变引起，根据遗传病关联的致病基因的数目，可以将其划分为单基因病和多基因病[9]，超过4000种人类疾病，如杜兴氏肌肉营养不良症（duchennemusculardystrophy），多囊肾（ploycystickidney）和镰状细胞性贫血（sicklecellanemia）都是单基因突变引起的。然而多数单基因病并不常见，亨廷顿病（huntington’sdisease）的发病率只有1/15000。相反，多基因病如多基因和环境导致的癌症更加常见，发现这些致病基因能够帮助研究人员了解底层的基因相互作用机制，从而帮助疾病治疗和诊断。目前产生候选致病基因主要由两种办法，第一种是使用连锁分析找到当前基因相对于另外一个叫做遗传标记位点的DNA序列的相对位置，根据相对位置来标记候选基因。另外一种办法是使用全基因组关联分析（Genomic-WideAssociationStudies，GWAS）来帮助实现候选基因的筛选[10]。这两种方法通常筛选出的疾病基因有上千种，但是如何判断那种基因是最有可能的致病基因，对分子生物学家和遗传医学家来说都是一个大的挑战，由于实验耗时耗力，所以很需要使用一些计算方法来解决这个问题。目前的致病基因预测多数分为析已有生物学数据构建网络，如蛋白质相互作用（Protein-ProteinInteraction，PPI）网络，代谢通路网络，表型相似度网络等，然后根据这些网络使用共同邻居，随机游走和机器学习等方法来解决致病基因预测和排序的问题。生物医学概念之间的相互关系的数据存在于很多公开的数据库中，为了综合分析这些数据，需要将这些数据统一整合。现已知的类似的系统有ONDEX[11]，Biozon[12]，IBN（IntegeratedBio-entityNetwork）[13]，BioMyn[14]，BioGraph[15]和Biomine[15]。他们都是将不同的数据源整合在一个数据库中，并使用了图模型或关系型数据库来存储这些数据。所有的系统都是一张有节点和边组成的图，分别代表的是不同的生物医学概念和它们之间的关系。ONDEX和BioZon包含了一些根据蛋白质序列相似度和根据对文献摘要的挖掘生成的预测边。BioZon提供了几种查-2- 哈尔滨工业大学工学硕士学位论文询模式，可以根据图结构计算出来的重要度对查询结果进行排序。IBN在整合了GO，KEGG，DO等数据库后又抓取了PubMed中的文献摘要信息，从摘要中找出蛋白质和蛋白质的相互作用的关系。BioGraph在整合数据的时候首次考虑到不同数据库的相同概念可能有不同的命名，于是利用UMLS系统为每个生物医学概念赋予了唯一的ID，减少了数据冗余，并注意到一些概念并没有在UMLS中有确切的表示，BioGraph对这些概念根据它们的类型做了扩展的UMLS标识。STRING数据库整合了多个蛋白质数据源，并根据不同的证据，计算出一个综合的分数，同时也提供了根据相关算法预测出的蛋白质相互关系的分数。国内在这方面起步较晚，多数止于生物信息的数据集成，最早在2006年，陈坚[17]等人就发表了一篇综述性质的文章来介绍生物本体的数据集成，林毅[18]等人提出了一个分布式环境下基于本体的生物信息集成框架（MOBIB），并较好的解决了生物数据中的结构异构，语义异构和术语异构。隽立然[18]在整合不同数据库时，给予不同生物医学关系不同的权值，以此量化数据库间的关系，并认为它能够衡量网络中数据库之间关系的紧密程度，且基于此进行生物信息数据库检索，而且建立了一个名为Bio-DB^2的检索系统。生物医学数据集成方面最大的挑战就是不同数据源之间如何使用一种规范来整合，这点是很困难和繁琐的。首先，因为不同数据源对同一个生物医学概念的描述可能会相互矛盾，另外注释信息可能会有错误或者有本体在定义的时候具有二义性等不确定的因素。其次，生物医学概念之间的关联需要很强的注释，才能使“信息流”高效的在生物医学概念之间相互传递。比如蛋白质互作网络中，相互作用的方式不同，有抑制，调节，磷酸化等，不过这些信息往往没有很好的文档注释。其它的信息比如相互作用的方向，发生作用时所在细胞的位置和作用的功能也都很少标明，但是这些信息在理解和使用互作网络时非常重要。针对整合后的生物网络，科研人员根据这些数据主要围绕图的一些特性做链接预测，如致病基因预测，蛋白质相互作用预测等。在疾病基因预测方面，最简单的一个实现就是仅利用现有的疾病—蛋白质，蛋白质—基因关系来作为预测的候选[19]。Krauthammer等人[20]在预测老年痴呆病致病基因时根据已知的疾病基因，通过其到其它节点的最短路径计算出的分数，来给邻近的基因作候选排序，并取得了较好的效果。Kohler等人[21]除了使用邻近节点和最短路径外还应用了随机游走的办法来预测候选疾病基因。Vanunu等人[22]从更宏观的角度出发，依据各个疾病的表型相似度来寻找出相关的蛋白，并根据这些蛋白来预测候选疾病基因。在生物概念链路预测方面，许多依据节点邻近度的链路预测是基于无权重网络的，对于有权重的网络这方面的文章还不是太多。Asthana等人[11]第一次使用了有权重的网络来-3- 哈尔滨工业大学工学硕士学位论文预测蛋白质之间的关系。随机游走算法因可以直接把无权重网络转化成节点带权重网络，所以在致病基因预测时也经常使用到[15,21]。生物医学网络模型一般都是无向图，可以根据图中节点的度分布，功能相似性，卡方统计等来做功能关系预测。为了额外考虑全局信息，目前大部分使用随机游走模型，因为整个网络中存在着一些Hub节点，并满足小世界和无标度网络特性，这跟网页间的关联非常类似，而且使用随机游走可以方便的给每个节点赋予权值，继而得到沿着某条链接依次访问节点的概率，从而对节点排序。大量的信息的整合可能会导致很多假阳性，怎么对预测结果进行排序对链接预测和排序来说至关重要。目前多数的方法是人为的设定一个阈值，比如仅做生物医学概念间TopN条的链接发现[15]。近几年出现了整合多个不同类型网路的异构网络模型[24-26]，如表型相似度和蛋白质相互作用网络整合，GO和蛋白质相互作用网络整合等，在这些异构网络上多数使用的是经典的随机游走的变种，如限制在每个子网络上的步长，跳转概率来优化致病基因排序结果。还有基于不同数据源的机器学习方法，输入训练基因，抽取基因在不同数据源中的特征，如在PPI网络中的拓扑结构，关键字，DNA序列长度，相关的代谢通路等，使用这些模型训练模型，从而对致病基因进行排序。1.3本文主要研究内容及组织结构1.3.1主要研究内容现有方法主要依赖于蛋白质相互作用网络和表型相似性网络来计算候选基因和致病基因的功能相似性，或者计算疾病同候选基因在网络中的可达概率。没有充分利用不同的生物网络，有研究表明，基因功能注释和基因本体对[14]致病基因预测同样有重要作用。本文的主要研究内容如下：（1）在整合了疾病本体，表型本体和基因本体的基础上，利用本体注释和外部数据库提供的疾病和基因的关系，将三种本体和蛋白质相互作用网络链接起来，形成了具有七种关系类型的异构网络。（2）设计了整合不同证据特征的权值整合规则，本文认为不同的边关系对致病基因预测贡献不同，所以为七种关系分别设置不同的权值，使用有监督随机游走训练出每种关系的权值。（3）改进了有监督随机游走算法，考虑到整合的网络是一个无标度网络，具有中心节点，但是蛋白质相互作用网络中，中心节点往往不是致病基因，因此在有监督随机游走的基础上加入了拉普拉斯正规化，使算法在训练时能够同时考虑节-4- 哈尔滨工业大学工学硕士学位论文点的权值和度信息。该算法可以对候选基因进行预测和排序。1.3.2本文组织结构第1章中简单介绍了课题背景和意义，对生物医学本体的数据整合，致病基因预测排序等国内外现状进行分析，总结了基因排序的作用和原理，在现实应用中的意义。第2章中介绍了致病基因预测的基本流程和常用假设，按照先后顺序，概括了使用序列特征和机器学习的方法对致病基因预测的步骤和评价方法，另外又介绍了目前利用全局网络的随机游走方法或其变种进行致病基因预测的常见的几种算法。第3章介绍了主要用来整合的本体库和蛋白质相互作用网络，并给出了数据抽取的过程和本体概念如何和基因关联，利用统一标示来减少不同数据源的冗余数据，并对数据源之间的重合做了统计。建立了一套证据整合机制来整合不同数据源中提供的质量不一的证据，最后构建了一个围绕本体网络和基因基因网络的带权双层异构网络模型。第4章介绍了随机游走的基本概念，在有返回随机游走的基础上，引入有监督的随机游走算法，并提出一个改进的拉普拉斯正规化随机游走模型，和简化的拉普拉斯正规化随机游走，最说明了如何将该算法应用在致病基因预测上来提高预测效果。第5章简要介绍了评价数据集的选取，正负例的构建准则和评价方法，之后在随机生成的无标度网络上验证了拉普拉斯正规化随机游走的有效性。在构建出的带权网络中，对比了随机游走，有监督随机游走和简化的拉普拉斯正规化随机游走在致病基因预测排序中的效果，分别实验结果进行分析与总结。-5- 哈尔滨工业大学工学硕士学位论文第2章致病基因预测方法概述2.1致病基因预测的主要流程致病基因预测离不开数据集的构建，数据集的好坏直接影响算法的验证和测试，目前常用的疾病基因数据来自人类在线孟德尔遗传OMIM，和基因之间的关系来自蛋白质相互作用网络（protein-proteininteractionnetwork）。致病基因预测是建立在一些经过人们长期观察研究的假设之上的，这些假设包括：（1）中心蛋白（HubProtein）是指那些在PPI网络中具有较高的度的蛋白质，它们往往跟致病基因无关，只是蛋白质相互作用的功能中心。（2）相似的疾病表型关联的蛋白质在PPI网络中往往具有功能的相似性。（3）相互作用的蛋白质模块部分关系的改变会导致相似的疾病表型。（4）与同一种表型相关的致病蛋白在PPI网络中具有聚集性。（5）具有相似致病基因集合的疾病通常具有表型相似性。利用这些假设，使用生物网络的局部特性，全局特性，利用随机游走，共同邻居，网络流以及特征提取机器学习等方法等来预测致病基因。致病基因预测又叫候选基因排序，它的输入包括一个分子生物学网络，如PPI网络，或一个整合后的网络，例如整合了通路信息，本体信息和PPI的网络；一个和疾病相关的种子基因集合，代表的是特定疾病相关的先验知识，即已经被证实是该疾病的致病基因；最后放入高通量检验技术产生的候选基因；输出是对候选基因进行从高到低排序，得分越高，表明该基因越有可能导致某种疾病（图2-1）。PPI记录的是蛋白质和蛋白质相互作用网络，根据中心法则，基因编码蛋白质，可以将蛋白质之间的相互关系映射为基因网络转化为基因相互作用网络，方便基因预测。图2-1致病基因预测流程-6- 哈尔滨工业大学工学硕士学位论文多数致病基因预测流程都和这个框架类似，需要依赖于当前已知的疾病基因关系预测候选基因。致病基因预测本质上是对缺失信息的还原和预测，是链接预测在生物信息学中的具体化应用，将其抽象起来，就是对于任意的网络GVE,，V表示顶点集合，E表示边集合，给定一个链接预测算法，对每对没有直接边相连的VV1顶点共计最多条边直接计算一个分数值，这个分数值可以理解为相似度2或接近性。它与两个顶点之间的最短距离有关，离得越近的节点，它们之间的分数越高，将得到的分数从大到小排序，越靠前的表示相连接的概率越大。排序效果依赖于当前网络的拓扑结构，网络包含的信息越全面，效果越好。目前已经证实，人工筛选或者自动抽取的基因功能注释对预测疾病到基因和相关蛋白质的关系提供了强有力的证据[14]，许多致病基因排序不仅使用了蛋白质相互作用网络来寻找由致病基因和候选基因产生的基因产物的关系，而且额外使用了表型相似性来丰富那些注释基因很少的疾病表型。除此之外，基因序列数据，基因表达数据，分子通路和相关生物医学文献也经常被用来对提高致病基因排序和预测的效果。然而一个一致完备的基因排序预测评测数据集还没有被建立[28]，多数方法都是整合不同数据源后构建网络进行排序，缺乏统一的评价方法。2.2致病基因预测的主要方法2.2.1基于分子和网络特征分类的方法利用致病基因的分子特性来寻找致病基因是最早被使用的计算方法，研究人员使用蛋白质序列，基因序列和基因功能注释等特征，来标记致病基因，若一个基因和已发现的致病基因在这些特征上相似，那么就认为该基因导致疾病的概率比其他基因要高。Lopez-Bigas等人[30]从疾病基因产物的氨基酸序列中提取了一些重要的特征，通过对比其它人类基因编码的蛋白质，他们发现疾病蛋白质一般会更长，在无脊椎动物和有脊椎动物身上具有同源保守性，并将这些序列特性使用决策树来识别致病基因。Xu和Li等人[31]使用用来自从文献中提取的，实验生成的和利用蛋白质相互作用预测出的三个分子网络的拓扑特性，如节点的度，已知致病基因间的平均距离一阶邻居，二阶邻居，正拓扑系数等。利用这些特征使用KNN（K-NearestNeighbors）分类器对三种分子网络中存在的候选基因进行分类，使用留一交叉验证的结果准确率是76%，从5262个候选基因集合中成功预测出178个新的致病基因。Lage等人[27]还将将表型数据添加进来，每个候选基因和直接和它相互作用的基因构成候选组合，所有在候选组合中的致病蛋白质都会根据表型相似性计算出一个相似度得分，最后使用朴素贝叶斯来进行分类。该方法使用连锁分析确-7- 哈尔滨工业大学工学硕士学位论文定候选基因，然后将这些基因映射到蛋白质相互作用网络中，查找候选基因蛋白质和它们邻居之间的关系，接下来设定阈值删除低于阈值的关系，保留的关系和候选蛋白质构成组合。若候选基因的邻居相关联的表型和疾病具有很高的相似性，那该候选基因就会有很大可能成为致病基因。此方法提高了预测致病基因的能力，不过依赖于蛋白质相互作用关系网络的结构，若当前基因是致病基因，但并没有和已知的致病基因的蛋白产物有直接关系，那就预测不出该致病基因。图的拓扑特性，如频度中心性，流紧密中心性，最短路径间接中心，亲近中心等复杂网络的特征都可以用来训练分类器。除了拓扑结构特征，Jia等人[32]还使用抽取自GO本体中三个子本体的特性加上转录因子位点，基因列表的代谢产物，基因敲除小鼠的表型，微小RNA的靶目标，蛋白质结构域，中心蛋白，基因结构等11中不同的特征来训练3种不同类型的分类器。基因表达数据可以用来判定一个基因是否正常，Nitsch等人[33]结合不同的基因表达数据和PPI网络开发出一个基于网络的机器学习方法来对致病基因进行排序，他们认为疾病基因在PPI网络中被表达不正常的基因产物所围绕。Chen等人[34]利用蛋白质复合物的生化特性，表达谱数据，通路数据来生成马尔科夫条件随机场模型，之后又使用多元回归模型来发现疾病相关的基因，同时序列数据，表型特征和表达数据都可以作为分类特征。CATAPULT[35]使用了有偏的SVM模型预测致病基因，作者认为目前的文献中只包含了基因和疾病相关的信息，很少包含基因和疾病不相关的信息，在训练过程中，构建的负例中有可能在未来会被证实为致病基因，所以CPATAPULT设计了一个策略，对错分的负例惩罚变小，对错分的正例惩罚变大。机器学习方法的挑战是如何选择有用的分类特征[36]，整合来自不同数据源的数据能够提高预测的效果。不过在整合过程中，冗余的信息和无用的信息过多反而会降低学习效果。不同的学习算法可能适用于不同的训练数据，可以使用多模型训练提高整体的预测效果。2.2.2基于网络节点相似度排序的方法过去十几年，分子间相互作用网络变得越来越容易获取，在研究人类疾病方面是非常重要的数据来源之一。对于致病基因预测，蛋白质相互作用网络是除基因功能注释之外最重要的网络[37]。和基因蛋白质具有序列特性一样，致病基因具有的网络特性可以用来对候选基因进行排序，如分子间相互作用网络可以自然而然的用来做致病基因预测，对多基因遗传病，基因产物之间正是通过这种相互作用导致疾病的。通过网络预测致病基因主要包括利用局部网络信息，利用全局网络信息和使用异构的网络信息三个部分。早期的致病基因排序方法主要关注的是局部的网络信息，如致病基因在蛋白-8- 哈尔滨工业大学工学硕士学位论文质相互作用网络中相邻的邻居可能是致病基因，这种做法的依据是致病蛋白质倾向于聚集到一起相互作用[12]。如果候选基因和当前致病基因距离比较远，那么它是致病基因的概率很低。对基因的距离的计算需要将基因转化成它们编码的蛋白质，然后使用这些蛋白质在蛋白质相互作用网络中的距离进行衡量，不过有部分致病基因通常在同一个代谢通路起作用，这样直接通过物理的相互作用找到邻居节点并不能定位致病基因。针对这种问题，Zhu等人[38]提出了一个顶点相似度的方法，这个方法使用蛋白质在PPI网络中最短距离来度量顶点的相似性。基因，蛋白质功能和疾病特征如发病年龄有很强的相关性，Jimenez-Sanchez等人依据此现象，利用致病基因的功能注释来对候选基因进行排序[38]，Freudenberg等人[40]使用候选基因注释的GO术语集合和致病基因注释的GO术语集合的相似度来对致病基因进行预测。近期的文献表明表型相似的疾病常具有随着相似的分子机制和功能相关的基因，说以证实了基因的功能注释在致病基因预测是起着重要作用。值得注意的是，使用信息量的来度量基因功能注释的相似性能够提高致病基因预测的准确度。局部网络信息忽略了距离较远的节点的影响，使用全局网络信息能提高致病基因排序的效果[21]，尤其对于多基因遗传病，网络拓扑分析可以同时考虑多路径和全局的蛋白质相互作用信息。全局网络信息主要使用有返回的随机游走（RandomWalkwithRestart，RWR）算法，粒子从已知疾病出发，在向周围扩展时按照一定概率返回起始点。Kohler[21]等人依此来计算PPI网络中蛋白质和蛋白质的相似性。RWR算法比传统的局部算法要好，因为它考虑了全局的网络结构。Chen等人[41]借鉴社交网络和互联网链接分析的技术，使用了三种随机游走方法来进行致病基因排序，分别为PageRank[42],HITS（Hyperlink-InducedTopicSearch）和KSMM（K-StepMarkovMethod）[43]，所有这三种方法都取得了不错的效果。Navlaka和Kingsford[44]通过对比直接邻居，网络流，无监督图分割和RWR等几种算法，发现RWR算法的精度和召回最高。和其改进本文第四章有详细介绍。近些年，基于异构网络的方法被越来越多的人研究。研究表明表型相似通常意味着关联的基因功能上的相似，表型相似性关系，基因本体和通路信息都能用来构建特性的网络。Wu等人[45]以此假设提出了一个名为CHPHER的回归模型来预测致病基因，通过回归模型计算出候选基因和特定表型的分数，用这个分数作为衡量候选基因为致病基因的可能性。为了构建CHPHER回归模型，需要准备本体相似性网络，蛋白质相互作用网络和疾病和已知致病基因的关系网络。给定一个表型和其候选基因，CHPHER首先将三种网络整合为一个网络，当前表型和其它表型的相似度用表型相似性网络的值和两个表型关联的基因的拓扑距离组合而成。候选-9- 哈尔滨工业大学工学硕士学位论文基因与某一表型的相似性度量是计算当前基因到这一表型关联基因的拓扑距离。最后计算出候选基因和所有表型，特定表型和所有表型的的相似度向量，使用皮尔逊相关系数来度量候选基因致病的得分，按照这个得分对候选基因进行排序。根据计算基因间拓扑距离的方法不同，Wu又将CIPHER分为基于直接邻居（DirectNeighbor，DN）和基于最短路径（ShortestPath，SP）的CIPHER-DN和CIPHER-SP算法。CIPHER只利用了局部网络拓扑特征，没有考虑到全局拓扑特性，Yao等人[46]使用随机游走算法计算基因和基因之间的平均相遇次数（mean-HIttng-Time，HIT），使用平均相遇时间来改进CIPHER，并提出了CIPHER-HIT算法。PRINCE[22]算法是另外一个根据异构网络预测致病基因的算法，它只需要两个网络，表型-基因关系网络和PPI网络，没有使用表型相似度网络。通过图传播的方法计算疾病和候选基因的相关程度。事实上，PRINCE算法本质上是主题敏感的PageRank（Topic-SensitivePageRank），将与疾病表行相关的种子基因作为一个主题，随机跳转的列向量和PageRank不同的是只将致病基因所在的位置赋值为1，其它赋值为0，这样做的目的是希望粒子在随机游走的过程中能够有一定概率返回致病基因集合中的基因，重新开始游走。同时PRINCE算法在初始化转移概率矩阵时使用了拉普拉斯正规化的方法，这个方法能够保证迭代过程收敛，并提高预测的准确率。本文在构建拉普拉斯正规化的有监督随机游走时参考了这一做法。PRINCE算法最终生成的对候选基因的稳态概率作为候选基因的排序依据。异构网络上的有返回随机游走（RandomWalkwithRestartonHeterogeneousnetwork，RWRH）是扩展版的RWR算法，异构网络的构建使用了表型相似性网络，疾病基因关联网络和PPI网络。RWRH算法参考了coranking算法框架[47]，给定种子基因集合和疾病相关的表型，同时在疾病和表型网络上进行有返回的随机游走。RWRH算法将异构网络的邻接矩阵分为四个子矩阵式（2-1）：MMGGPM（2-1）MMPGp其中M表示基因相互作用的链接矩阵M表示表型和基因相关联的邻接矩GGPT阵，且MM，M为表型相似性邻接矩阵。RWRH使用一个参数来控制当PGGPp一个节点同时和基因表型相连时，跳转到两种网络的概率。当节点不跨层相连时，0，分别对每个子邻接矩阵按列归一化，设归一化后的四个矩阵为M,MM,,M则，则得到的概率转移矩阵M可表示为：GpGPPG(1)MMGGPM(2-2)MM(1)PGP注意到M不满足列和为1，再次对M进行按列归一化，得到最终的转移概率-10- 哈尔滨工业大学工学硕士学位论文矩阵。使用表型和表型关联基因构建跳转向量，类似于PRINCE的处理方式，这里的主题有两类，一类是疾病关联的表型，一类是表型关联的基因集合。为跳转概率向量设置参数，最终的跳转概率为Puv[(1),]，uv,分别表示表型和基因的0跳转概率，当表型和基因属于主题集合时，其值为1，设定好，再对改向量按不同的主题进行归一化，获得最终的跳转概率，整合后的RWRH算法可以表示为TPMP(1P)，为阻尼系数，P为第k1次迭代的概率向量，待迭代kk10k1向量稳定后，对基因节点通过收敛的稳态概率进行排序，最终获得基因对当前疾病的排序得分。2.3本章小结本章主要介绍了致病基因预测的主要步骤，并给出了致病基因预测中常用的一些假设，多数方法预测方法依赖于这些假设。分析了致病基因预测常用的数据来源，以及如何使用这些数据提供的局部网络特征，序列特征，使用机器学习的方法对致病基因进行分类，在全局的网络中使用类随机游走的方法进行致病基因排序。最后介绍了今几年研究比较多的，在多个子网络的构成异构网络上的致病基因排序算法。-11- 哈尔滨工业大学工学硕士学位论文第3章本体基因数据整合和网络构建3.1引言表型数据，基因功能数据，和蛋白质相互作用网络常用来预测致病基因，本文中使用的数据库主要包括生物医学本体相关的数据库，如基因本体，疾病本体和人类表型本体（HumanPhenotypeOntology，HPO）[48]；以及疾病表型关联的基因数据库，如OMIM，疾病和基因突变数据库（ClinVar）[49]和毒性与基因比较数据库（ComparativeToxicogenomicsDatabase，CTD）[50]，基因本体注释（GOA），人类表型基因注释（HumanPhenotypeOntologyAnnotation，HPOA）[48]，基因蛋白质功能相互作用网络（STRING）；为了整合不同来源的数据，我们额外使用了统一词汇表数据库UMLS，蛋白质ID基因ID映射数据库HGNC（HUGOgeneNomenclatureCommittee）[51]和SIDD[52]来将不同概念统一映射到UMLS中减少冗余和融合来自不同数据库的相同类型的节点。表3-1列出了本文使用的全部数据库。表3-1本文中使用的数据库缩写数据库描述作用/提供的关系STRINGSearchToolfortheRetrievalofInteractingGene/Proteins基因产物-基因产物CTD-DGTheComparativeToxicogenomicsDatabase-CuratedDiseae-疾病-基因GeneInteractionsGOGeneOntology基因功能-基因功能GOAGeneOntologyAnnotation(GOA)Database基因产物-基因功能OMIMOnlineMendelianInheritanceinManDiseaseSubtypes疾病/表型-基因DOHumanDiseaseOntology疾病-疾病HPOHumanPhenotypeOntology表型-表型HPOAHumanPhenotypeOntologyAnnotation表型-表型/疾病ClinVarClinicalVariantsandphenotypes表型/疾病-基因变异HGNCHUGOgeneNomenclatureCommitteeDatabase基因标识映射MeSHMedicalSubjectHeadings统一词汇表UMLSUnifiedMedicalLanguageSystem统一词汇表SIDDSemanticallyIntegratedDisease-associatedDatabase疾病名称映射以上数据库为我们构建的概念-基因网络提供了各种边和节点，其中GO提供了分子功能概念节点，生物过程概念节点，细胞组分概念节点，DO提供了疾病概念节点，HPO提供了表型和疾病概念节点，STRING间接提供了基因节点，OMIM-12- 哈尔滨工业大学工学硕士学位论文提供了部分基因节点和表型疾病节点，ClinVar提供的是基因位点变异和疾病表型的信息，CTD提供的是疾病和基因的关系，此外，本体数据中还提供了概念和概念之间的关系信息。整合这些数据库建立三种本体到基因的关系，最终构建出一个双层的异构网络，整合流程见图3-1。图3-1整合不同数据构建本体-基因网络的流程3.2生物医学本体数据整合3.2.1本体论概述本体（Ontology）是哲学用语，最早使用这一个词的是17世纪的德国学者郭克兰纽（1574-1628），本体论是由希腊文Ont加上表示“学问”，“学说”的后缀“ology”构成，描述的是Ont的学问，Ont在英文中代表Being，即描述存在论的学问。所-13- 哈尔滨工业大学工学硕士学位论文以本体论又称为存在论。具体来说，本体论是概念到概念的关系组成的原理系统。在计算机领域内，本体定义为对概念对象的表示和描述。早在20世纪90年代人工智能领域首先引入了本体的概念，随后成为包括知识工程，自然语言处理和等诸多团队研究的热门课题，在1993年，Cruber等人定义本体是概念模型的明确的规范说明，它取自于哲学，代表的是存在。Borst给出了本体的另外一个定义是“本体是共享概念的形式化规范说明”。2000年以后，随着互联网的快速发展，W3CWeb认为本体有利于构建基于互联网的语义网络，从而成立了本体工作组（WebOnt）小组，该小组将本体的结构分为：类（Class），属性（Property），类的实例（Instance）以及这些实例间的关系，同时还包含了一些公理（Axioms）和函数（Functions）。通常也把类写成概念（Concepts），其中类（概念）含义广泛，可以代表任何事物，关系表示概念之间的关系，一般是细化的概念的泛化的概念的“isa”关系，部分概念到整体概念的“part-of”关系，实例和概念的“instanceof”关系等，函数（Functions）表示的是一类特殊的前n个概念可以唯一的决定第n+1个概念，公理（Axioms）为用真断言，代表的是不言而喻的事实。实例（Instance）是类（概念）的具象化。目前的本体版本有很多种，对于不同问题和不同的工程应构造的方法也不同，所以实际应用中不一定完全按照上述五类元素来构造本体。而且概念和概念，实例和实例间的关系也不仅仅局限于上面的三种，应根据不同的应用场景，选择不同的本体构建方法。因当前对构建本体没有一个统一的评价标准，所以对于特定领域的本体构建，需要领域专家的参与和把控，这样才能保证构建的本体的质量。3.2.2生物医学本体格式和关系抽取生物学知识本身的复杂性导致产生的数据往往不能直接简单的集成到现有的生物数据库或者分子数据中，生物医学本体是对生物学知识的一种按照层级结构的抽象，本体是一个有向无环图，从根到叶子节点，概念从广到窄，越来越细化。通过对这些概念进行相应的注释，如使用基因注释疾病本体，使用基因产物注释基因本体，可以对生物学知识进行分类标记，方便研究者的理解和检索。基因本体（GO）是1998年在三种模式生物（酵母菌，小鼠和果蝇）数据库系统联合推导出来的。它提供了一个受控词汇表术语用于描述基因产物和功能，目前为止，GO包括了40000多个生物学术语，这些术语概念注释了来自超过100000篇文献中实验得到的基因功能和产物。GO中包含了描述基因，基因产物，基因功能的三个独立的本体：生物过程（BiologicalProcess，BP），细胞组分（CellComponent，CC）和分子功能（Molecular-14- 哈尔滨工业大学工学硕士学位论文Function，MF）。三个本体间相互独立，其中的本体概念称为Term，每个Term通过节点之间的关系，通过“isa”，“partof”，“regulates”，“positivelyregulates”，“negativelyregulates”和“haspart”连接在一起，这些关系没有数量限制，一个term可以指向多个和其有不同关系的父节点（图3-2），本研究中主要用到的是“isa”，“partof”，“regulates“这三种主要关系，因为它们的数量在GOterm中占据了96%的比例。图3-2GO中概念间常见的关系Isa是GO中最基本的关系形式，如果说AisaB那么代表的意思是A是B的子类型，例如有丝分裂细胞周期isa细胞周期，或者裂合酶活动isa催化性活动。不过需要注意的是isa并不同“instanceof”等价，如，猫isa哺乳动物，加菲猫是instanceof猫，而不是猫的子类，已知猫isa哺乳动物，所以可以说，所有的instanceof猫isa哺乳动物。GO和多数生物医学本体一样，不使用instanceof这种关系。要注意的是，isa关系具有传递性，若AisaB，BisaC，那么可以推导出AisaC（图3-3）。图3-3GO中isa关系传递性质示例Partof用来描述部分到整体的关系，在GO中partof具有特定意义，A和B之间具有partof关系，可以得出B必然是A的一部分，B的存在意味着A，但A存在时并不能推出B的存在。Partof关系也具有传递性，当ApartofB，BpartofC，则ApartofC，同时partof关系可以和isa关系组合，如ApartofB，BisaC，那么可以说ApartofC（图3-4）。图3-4GO中partof传递性质示例另一种在GO中常见的关系是regulates，代表的意思是一个分子过程直接影响-15- 哈尔滨工业大学工学硕士学位论文或调控后一个过程或条件，如一个过程regulates一个代谢通路或酶反应，还可以是PH值和细胞尺寸等条件regulates代谢通路和酶反应。同part-of关系类似，这个条件是必要条件，如果BregulatesA，不能总是保证A总是被Bregulates。一般regulates没有传递性，不过可以和isa,partof组合来完成传递性，如AregulatesB，Bisa/partofC，那么就可以说，AregulatesC(图3-5)。图3-5GO中regulates传递性质示例疾病本体是一个开源的集成生物医学中人类疾病相关数据的本体。它的数据来自各种医学词汇表和数据库，如UMLS，SNOMEDCT，ICD-9，ICD-10等，并通过DO节点的xref属性链接到来源数据库中。到目前为止，DO中共包含了近9000多种疾病，其中标记为已过时的有2000多种，剩余的6000多种疾病全部通过“isa”关系连接。DO节点之间只存在“isa”关系，这些isa关系组成了具有近7000多条边的有向无环图，如乳腺癌isa胸部癌症，胸部癌症isa器官系统癌症，器官系统癌症isa癌症，癌症isa细胞过度增殖疾病等，DO中的isa关系与GO中的isa关系类似，都具有传递性。人类表型本体（HPO）类似与疾病本体，不过表型本体集成的是表先型信息，如某种疾病表现出来的发热，头疼，皮肤红肿等。它的数据来源于OMIM，UMLS，ICD10，MeSH，PuMed，SNOMEDCT等数据库和文献。HPO提供了一个结构化了，定义良好的本体数据，其中包含了11000个描述人类疾病的概念。HPO被用来开发临床诊断算法，候选致病基因排序，推断新药症状等方面。HPO同DO一样，只包括了“isa”关系，共计14000多条记录。这些概念和概念的关系共同构成了表型本体。目前常用的本体表示格式有基于资源描述框架（ResourceDescriptionFramework，RDF）的网络本体描述语言OWL（webontologylanguage）格式，和基于开放生物医学本体（OpenBiomedicalOntologies，OBO）格式的生物医学本体数据。其中OWL主要由W3C定制，包括了三个子语言OWLLite/OWLDL/OWLFull。OWLLite对OWL语言的限制比较多，OWLDL次之，OWLFull的约束最少。他们分别适用于不同的应用场合下，是Web语义网络的重要组成部分。OBO的文件格式十分容易理解，生物学家可以方便的使用它来创建生物本体的知识结构，在生物信息学广泛使用。GO分别提供了OBO格式和OWL格式的本体下载，DO只提供了OBO格式的文件，HPO提供了OBO和OWL的格式的本体，为了统一起见，本文全部全用OBO格式的本体数据。-16- 哈尔滨工业大学工学硕士学位论文OBO文件描述一个生物医学本体，由一个头部（header）和多个节（stanza）组成，头部和节都有一些键值对，中间用冒号隔开。其中节又分为术语概念（term），属性的定义（typedef）和实例（instance）三种类型，同样的，概念之间的构成一个有向无环图，OBO格式具体的结构见图3-6。图3-6本体OBO文件格式针对OBO文件，本文实现了通用的解析程序（图3-7），OboDoc表示对整个OBO文件的抽象，OBOHeaderFrame表示对OBO文件的Header的抽象，OBOTermFrame表示对term的抽象，因OBO文件中每个term中的每一行按键值对保存，所以抽象出最底层的Clause类，这个类保存了tag和value这两个属性。数据整合时，因为本文最后要构建的是本体术语-基因，本体术语-本体术语，基因-基因三大类关系组成的网络，所以根据整合的数据库的特点，我们只关注term和term之间的关系和term的结构的存储，丢弃掉term中的其他属性，如Synonym和Subset，使用统一的表结构可以方便的整合不同本体数据，为此制定了基于关系数据库的本体存储表结构，见表格ER图（图3-8）。其中表ontology_term2term记录的是本体之间的关系，关系类型有“isa”,“partof”,“regulates”等。表ontology_term记录的是本体的term的一些详细信息，如当term的ID，定义，名称，是否已经弃用等，最后ontology_term_dbxref表，记录的是构建当前term时以依赖的外部数据源，是我们连接本体到基因注释的桥梁。其中xref_dbname表示的是引用的外部数据库的名称，xref_key即为外部数据库的字段ID。图3-7OBO解析器类图-17- 哈尔滨工业大学工学硕士学位论文图3-8本体映射到关系数据库表格的ER图3.2.3本体注释生物医学本体中的每个term描述的是一个概念，将这些概念链接到实际的实例上就是本体注释的工作。生物医学本体注释中数量最多，质量最高的是基因本体注释（GeneOntologyAnnotation，GOA），基因和基因产物，如蛋白质，RNA和酶可以通过GOterm注释起来，基因本体和其注释的基因产物提供的标准的生物学模型，可以方便的使用计算机程序进行分析，这种功能上的分类对进一步识别基因，研究基因的表达调控机制，研究基因在生物体中的代谢地位，分析基因和基因产物之间的相互做用，预测和发现蛋白质功能都具有重要意义。被GO注释的基因产物往往具有不同的证据代码（Evidencecode），这些证据标明了研究人员通过什么样的方法判定基因产物被GOterm注释的，在整合本体注释数据时，我们考虑到不同证据的重要性不同，而赋予这些证据不同的权值。目前GOA根据物种的不同，提供了不同的注释数据，本文中只考虑人类基因本体注释，经统计GOA中注释的不同Evidence数量如（表3-2）所示表3-2GOA中不同类型的证据代码统计证据代码证据描述数量IEAInferredfromElectronicAnnotation144066TASTraceableAuthorStatement95583IDAInferredfromDirectAssay73776IPIInferredfromPhysicalInteraction72170IBAInferredfromBiologicalaspectofAncestor46128ISSInferredfromSequenceorstructuralSimilarity18528IMPInferredfromMutantPhenotype14911NASNon-traceableAuthorStatement7583NDNobiologicalDataavailable1901ICInferredbyCurator1343-18- 哈尔滨工业大学工学硕士学位论文表3-2（续表）证据代码证据描述数量IEPInferredfromExpressionPattern956IGIInferredfromGeneticInteraction848EXPInferredfromExperiment313IKRInferredfromKeyResidues31IRDInferredfromRapidDivergence2人类表型本体HPO来源于疾病和词汇表等数据库，所以主要用来注释疾病，目前HPOA注释的疾病主要来源于DECIPHER（DatabasEofgenomiCvarIationandPhenotypeinHumansusingEnsemblResources），ORPHANET和OMIM（0nlineMendelianInheritanceinMan）。这些注释同样具有EvidenceCode，不同的Evidencecode和说明见表3-3。表3-3HPOA中不同类型的证据代码统计证据代码证据描述数量ICEindividualclinicalexperience25IEAinferredfromelectronicannotation59725PCSpublishedclinicalstudy4119TAStraceableauthorstatement548653.2.4疾病表型与基因关系数据在线人类孟德尔遗传（OMIM）是由美国国立生物信息技术中心（NCBI）提供的数据库，为研究遗传失调的医生，遗传学科研人员和生物信息学生提供有关基因、遗传和性状失调等方面的信息。OMIM包含了已知的单基因遗传病、多基因遗传病，遗传决定的表型和基因。OMIM的MIM号为全世界所公认，成为了研究遗传疾病的主要参考ID。截止2015年7月，OMIM中共有23034种实体描述，这些实体主要包含表型和基因，每个实体都使用OMIM的MIM号来统一标识。OMIMMorbidMap提供了遗传疾病到相关基因的关系，致病基因预测主要依赖于MorbidMap。本文中主要使用MorbidMap来提取基因和疾病的关系。毒性与基因比较数据库（ComparativeToxicogenomicsDatabase，CTD）主要的作用是为了帮助研究人员研究环境因素如何影响人类健康。它包含了人工审查的关系如化学药品-基因相互作用，化学药品-疾病的关系，基因-疾病的关系，还包括了通过某一个化合物计算出来的基因和疾病的关系，这种计算出来的关系都具有一个数值，数值越高，代表基因导致疾病的可能性越高。目前疾病-基因的关系在CTD数据库中有约3512万条，不过人工审核的基因-疾病数据仅有2万多条，并且部-19- 哈尔滨工业大学工学硕士学位论文分和OMIM中提供的疾病到基因的关系重合。因推导出来的基因-疾病关系数量庞大，在本文中，忽略了这种关系，只使用了人工审查过的基因和疾病的关系。CTD数据库对疾病的标识使用MeSHID，OMIM对疾病或表型的标识使用MIM号，本研究中使用SIDD来增加DO术语到MeSH和OMIM的疾病/表型的映射，利用这两个数据库中疾病和致病基因的关系来扩充DO术语关联的基因，SIDD将术语和MeSH，OMIM的映射分为以下三种：（1）通过本体中term的xref属性获取的同义词（MFR，mappingfromrefer）,（2）通过本体中term的synonym属性获取的同义词（MFS，mappingfromsynonym）,（3）通过本体中term和term之间的isa关系，子term可以获得离自己最近的父term同义词，因为isa代表的是父类和子类的关系，所以对于不存在前两种类型mapping的term可以通过寻找父类同义词的方法来构建mapping（MFI,mappingfrominferring）。由于疾病本体中的mapping多数和MeSH受控词表相关联，现举例说明MeSHmapping到DO的表现形式（图3-8），DOID:1378通过MFR映射到MeSH树中的Hypolipoproteinemias(D007009)，DOID:1390通过MFR映射到MeSH树中的Hypobetalipoproteinemias(D006995)，MeSH树中的节点D052476通过父节点D006995映射到DOID:1390。MeshTreeDOTreeDiseases[C]disease[DOID:4]HypolipoproteinemiasMFRhypolipoproteinemia[D007009][DOID:1387]MFRHypobetalipoproteinemiashypobetalipoproteinemia[D006995][DOID:1390]FIMHypobetalipoproteinemia,Familial,ApolipoproteinB[D052476]图3-8Meshmapping到DO[52]利用SIDD扩充DO到基因关系的具体流程见图（图3-9）,其中do-sidd-omim-gene-MFR表示的是DO到基因的关系是通过SIDD的MFR规则将OMIM的MIM号映射到DO上，并通过morbidmap数据表获取的对应基因的关系。do-sidd-mesh-gene-MFR表示的是DO到基因的关系是通过SIDD的MFR规则将CTD的MeSHID映射到DO上，进而建立DO到MESHID再到基因的关系，其他关系类似。最终使用SIDD为DO增加DO到Gene的关联关系的数量共计24684条。-20- 哈尔滨工业大学工学硕士学位论文图3-9疾病名称映射到DO的流程ClinVar数据库通过收集临床病人样本的基因突变信息数据，建立了人类基因突变信息和表型/疾病的关系数据，并且开放下载。ClinVar提供的数据中部分疾病名称可以对应到HPO，DO，OMIM，UMLS中去，这种映射关系方便我们把它整合到本体-基因网络中。本研究中通过映射，能够使用到的来自ClinVar的基因-疾病关系为21167条。3.2.5基因与基因关系数据基因和基因网络使用的是STRING数据库，它是研究基因编码蛋白质的数据库，它整合了13种蛋白质数据库如BIND,BioCarta,BioCyc,BioGrid,DIP,HPRD,INACT等，包括了PPI数据，蛋白质功能相似性数据，除了实验数据、从文献摘要中利用数据挖掘方法提取的结果外，还自定义了一套预测机制，使用基因在染色体的位置，和基因芯片得到的基因共表达数据来计算每一种关系类型的得分，并通过一个打分公式整合不同证据的权重，最终计算出一个综合的得分。本文中使用STRING提供的EnsemblID到GeneID的映射来实现蛋白质网络到基因网络的构建。STRING将权重分为三个种类，权重小于0.4为低置信度，权重大于0.4小于0.7为中等置信度，权重大于0.7为高置信度[6]。目前STRING数据库中包含人类蛋白质相关的数据有6800多万条，面对如此海量的数据，在整合STRING时只选用了存在实验支持且置信度大于0.4的关系，这种关系有20万条，考虑到蛋白质相互关系是一个无向边，STRING数据库按照有向边来存储，所以每条边都实际上使用的蛋白质-蛋白质相互作用关系应为10万条。3.3本体与基因网络构建3.3.1统一标识映射整合不同数据源需要考虑不同数据库的命名规范，根据文献[15]的经验，我们选用UMLS作为统一网络节点的工具。UMLS全称为统一医学语言系统，是美国国立医学图书馆（NationalLibraryofMedicine，NLM）于1986年开始建设的一体化医学知识语言，UMLS主要用于术语研究，术语映射，创建本地术语，信息标引和检-21- 哈尔滨工业大学工学硕士学位论文索，自然语言处理等。UMLS包括了超级叙词表（Metathesaurus）、语义网络（SemanticNetwork）、专家词典（SpecialistLexicon）和支持性的软件系统，其中超级叙词表是经常被使用的部分，约占总使用量的94%。在本研究中，我们仅使用超级叙词表来映射疾病本体，基因本体，基因和人类表型到UMLS的超级叙词表中的概念上，其标识符为CUI。目前，GO，OMIM，HGNCID都可以直接映射到UMLSCUI上面，DO，HPO通过Xref属性能够部分映射到UMLS上。但是，不是所有的HPO和DOterm都可以映射到UMLS中，我们额外使用了ClinVar的数据来补充HPOterm到UMLS的映射。HGNC提供了从NCBIGENEID到HGNCID的映射，故STRING数据库中的蛋白质ID可以由STRING提供的蛋白质到NCBIGeneID映射到HGNCID上，间接通过HGNCID映射到UMLS概念上。CTD数据库只提供了MeSHID到致病基因的关系，可以使用UMLS提供的MeSHID到UMLSCUI的映射来补充DO和HPO的术语到治病基因关系。对于余下的不能映射到UMLS的本体术语，使用自定义的UNMAPID来标示它，并作为该术语的全局唯一ID(图3-10)。经过统计，本体和基因映射到统一ID的统计见（表3-4）。图3-10不同数据库ID映射到统一标识的途径表3-4数据库ID映射到UMLSCUI数量统计数据源不能映射可以映射OMIM171022322HPO58545210DO11165674GO201339189GENE44335819总计11136395645-22- 哈尔滨工业大学工学硕士学位论文将所有的疾病，表型，基因等映射到统一ID系统上的文氏图（图3-11），可以发现HPO，OMIM，DO，MeSH之间，OMIMMIM号到基因之间都存在不同程度的重叠。图3-11各种数据ID转换成统一ID后的重合情况统计3.3.2证据整合和网络构建关系的证据合并时需要考虑不同数据来源的类型，为此本研究中综合考虑本体术语之间，本体注释，本体的Xref属性以及外部数据源提供的关联关系，将关联网络中的关系根据来源的不同分为了34种（表3-5），并赋予了不同的重要程度。表3-5整合的关系证据权值的权值列表数据来源证据代码证据简写数量重要度SIDD,CTDdo_sidd_mesh_gene_MFRDMR170720.8do_sidd_mesh_gene_MFSDMS10970.8do_sidd_mesh_gene_MFIDMI37560.6SIDD,OMIMdo_sidd_omim_gene_MFRDOR18720.8do_sidd_omim_gene_MFSDOS2570.8do_sidd_omim_gene_MFIDOI24720.6OMIMdo_xref_omim_geneDXM6661.0ClinVardisease_clinvar_geneDVG211670.8CTDdisease_ctd_gene_curatedDCG35590.8STRINGstring_geneSGG102962自带GOAgo_annotation_gene_EXPGEXP2211.0go_annotation_gene_IDAGIDA554691.0go_annotation_gene_IPIGIPI126041.0go_annotation_gene_IMPGIMP137811.0go_annotation_gene_IGIGIGI6791.0go_annotation_gene_IEPGIEP9291.0go_annotation_gene_IEAGIEA797720.4-23- 哈尔滨工业大学工学硕士学位论文表3-5（续表）数据来源证据代码证据简写数量重要度go_annotation_gene_NDGND18920.4go_annotation_gene_ICGIC12350.6go_annotation_gene_NASGNAS69350.6go_annotation_gene_TASGTAS479510.8go_annotation_gene_IKRGIKR290.6go_annotation_gene_IRDGIRD20.6go_annotation_gene_IBAGIBA135590.6go_annotation_gene_ISSGISS175730.6HPOhp_annotation_gene_IEAHIEA26370.4OMIMhp_annotation_gene_ICEHICE10.8hp_annotation_gene_PCSHPCS1050.8hp_annotation_gene_TASHTAS15000.8GOgo_is_aGOA724591.0go_part_ofGOP85270.8go_regulatesGOR32080.6DOdo_is_aDOA69191.0HPhp_is_aHPA147621.0本研究中对证据代码的重要度是根据证据的可靠程度进行设置的，比如GO的EXP，IDA，IPI，IMP，IGI，IEP是通过实验手段得到的，因此获得的重要度比较高，其他的证据是通过文本挖掘，数据作者的声明等方法获取到的，重要度相对较低。IEA类的证据和没有数据支持的证据ND设置的重要度最低。一条关系往往具有多个证据，已知的关系中存在多种证据的有GO-基因，DO-基因，HP-基因，当遇到多种关系时，对证据进行筛选排序，如果两种证据之间不是独立的，当前关系的重要度就取为最大值的重要度，如通过SIDD扩充的DO到基因的关系和通过DO的Xref属性扩充的DO到基因的关系就不是独立的，他们是一种证据的两种表示形式，代表的都是从OMIM的mobridmap获取的疾病到基因的关系，这里取最大的重要度，若关系的证据相互独立，则使用类似于[6]中整合不同来源的方法来计算最终的重要程度。目前不相互独立的证据主要来自从SIDD的映射，和CTD，ClinVar提供的HP，DO到基因的关系，我们定义如下规则：当关系的证据代码中部分证据在集合中，只取最大的重要度的证据代码，并删掉在集合中的其他证据，将不在集合中的证据的重要度和当前选出的证据利用公式3-1计算最后的关系的重要度。SS1(1i)(3-1)i-24- 哈尔滨工业大学工学硕士学位论文max{,SS,,}S,,ij,nNoIndijn其中S，ij,代表证据类型。iSiNoIndi通过对数据解析，本体术语和基因的全局ID映射和本体术语和关系的提取及证据整合，我们得到了包含基因，基因本体术语，疾病本体术语，表型本体术语共78786个顶点和本体术语之间的105875条有向边，以及术语到基因，基因和基因之间组成的398642条无向边。构建的双层网络结构如图3-12所示，由于部分HPO的术语和DO术语的数据有重合，这里将HPO和DO当做一个互连的网络。GO和HPO，DO无直接边相连。这个双层异构网络的度分布参见图3-13。看以看出，整合后的网络少数节点的度很高，具有很强的连接性，但是大多数的度较低，这种度分布满足，即幂律分布，其中表示节点度为的概率为，通常为2-3的常数，是典型的无标度网络。图3-12整合的本体-基因网络框架图图3-13本体-基因网络节点的度分布-25- 哈尔滨工业大学工学硕士学位论文3.4本章小结本章主要介绍了构建本体-基因异构网络的方法，包括对本体的结构分析和数据抽取；本体术语和蛋白质/基因想统一标识映射的处理方法；从CTD，OMIM，ClinVar数据库抽取疾病-基因关系，并映射到HPO和DO上，从而扩充表型/疾病到基因的关系数量的详细步骤；给出了一种整合不同数据源关系的带权证据整合方法，最后统计了映射到全局统一标识后各个实体术语间重合的情况，并统计了构建出的网络的节点和边的数量，针对网络的度分布做了简要分析，说明了构建的网络是一个无标度网络。-26- 哈尔滨工业大学工学硕士学位论文第4章基于有监督随机游走的致病基因预测4.1引言本体-基因网络是双层的异构网络，利用构建的网络对致病基因进行排序和预测是本研究的另一个重要部分。以往的方法在只利用了基因本体或表型本体相似度网络整合蛋白质相互作用网络来预测致病基因，往往不能推广到多个数据整合后的情况。研究表明，加权的蛋白质相互作用网络对蛋白质功能预测具有重要意义，主要原因是因为当前的高通量测序和实验技术产生的数据包含大量的假阳性和假阴性，蛋白质相互作用网络中不同的权重表明不同的置信度，权重越大，表示相互作用的可能性越高，反之越低。本文中直接利用了数据中自带的权值，对于无权重的边，根据不同的证据代码，给予人工赋予的权值。本章主要包含五个部分，首先对随机游走模型简单介绍，其次说明了如何利用有返回的随机游走模型来预测致病基因和对致病基因进行排序，然后利用LarsBackstrom等人[53]提出的有监督的随机游走（SupervisedRandomWalk,SRW）模型，来赋予不同数据来源以不同的权重，从而使权重有利于致病基因预测，并提出了拉普拉斯正规化的SRW模型（LaplacianNormalization-SupervisedRandomWalk，LN-SRW），和简化的拉普拉斯正规化SRW模型（SimpleLaplacianNormalization-SupervisedRandomWalk，SLN-SRW）算法，最后说明了如何使用SRW和SNL-SRW算法在加权的本体-基因网络上训练不同类型的边权重，并预测致病基因的过程。4.2随机游走模型概述随机游走（RandomWalk，RW）是物理学中描述布朗运动中粒子活动的规律。假设有一个粒子，按照不同的转移概率在网络中随机游走，这个概率可以看做两个节点之间的权重，对于无权重的边，从节点a到节点b的转移概率为a出度的倒数，对于有权重的边，a到节点b的概率为a到b的权重除以a链出边的权重和。对于网络中每个特定的节点的每条出边都具有一个概率值，每个节点的出边的概率和相加为1。在疾病预测中，可以利用转移概率的大小作为两个节点的直接相似度，两个节点通过随机游走计算出的概率越高，代表它们之间越有可能发生直接联系。在每一步的随机游走过程中，粒子的下一步的行动不受上一步行动的影响，这种行为又叫马尔科夫过程。马尔科夫过程满足两个基本条件，首先t1时刻系统状态的概率分布只与t时刻的状态有关，于t时刻以前的状态无关，其次t时刻到t1-27- 哈尔滨工业大学工学硕士学位论文时刻的状态转移与t无关，即随机过程的无后效性。下面对随机游走中的概念和定理做简单介绍。设XttT(),为一随机过程，E为状态空间，如果n1，tttT，12nxx,,xE，随机变量Xt在已知条件XtxXt,,x,Xtx下1231122nn的分布函数仅与Xtx有关，即满足nnFxtxx,,,,,,xt,tFxtxt,,（4-1）nn11n1nn或满足条件概率分布PXt()xXt(),,()xXtnnxn()PXtnxXt11x则称这个随机过程为马尔科夫过程。由离散参数集合T{,,}tt和离散状态12集合E{,aa,}构成的马尔科夫过程成为马尔可夫链。若马尔科夫链的状态空12间的转移概率与马氏链现在所在时刻无关，则称马氏链为齐次马氏链。设齐次马氏链Xnn(),1的状态空间为EN{1,2,,}若mNm,0，使ij,E，其m步概率转移矩阵都满足：()mPijE0,,ij（4-2）PijiE1jE则马氏链具有遍历性，已知稳态概率向量P，即NjiijpjN1,2,,（4-3）i1N具有唯一解，j0,1,2,jN,，j1。当随机游走的状态转移矩阵满j1足公式4-2时，总能够通过迭代获得最终的稳态概率。这也就是要求随机游走的每个节点的出边的权值和为1的原因。4.3有返回的随机游走有返回的随机游走，又称为带重启的随机游走（RandomWalkwithRestar，RWR）是PageRank算法的扩展，主要思想是假设粒子在进行随机游走过程中，按照某一固定概率，重新回到起始位置。最后得到的基于起始节点到网络中其它节点的概率。如果将RWR算法应用于致病基因排序和预测上，那么起始点可以是待预测的基因关联的疾病。RWR的形式化的描述如下：设GVE(,)表示一个图，E表示图中的边集合，V是图中的节点组成的集合。Q表示按行归一化后的邻接矩阵，q为矩阵元素，当q0时，表示从节点j到ijij-28- 哈尔滨工业大学工学硕士学位论文()k节点i存在一条边。s为RWR算法的返回点，p表示第k次迭代后粒子从s出发iT访问节点()k()k()k()ki的概率，Pp,p,,p表示第k次随机游走的概率向量，12n粒子以的概率回退到起始点s，则RWR算法可以表示为()k(k1)()sP(1)QPe（4-4）1is()s其中eiiE，RWR还有另外一种等价的描述0otherwise()kk(1)PQSP(1)（4-5）1is这里SijVij.,，代表的意义是网络中其余点生成了到起始s0otherwise的一条权重为的边。可以证明(1)QS中的每列求和仍为1，且都大于0，满足齐次马尔科夫链的收敛条件，所以最终P会收敛到某个稳态的转移概率向量。在无向图中，可以直接考虑基于单点的带重启的随机游走，但是在有向图中，设起始点为s目标点为t，sijt的路径和tijs的路径往往不相等，也就是说从s出发到节点t的所有路径的概率ppstpath和pathallstpptspath会有很大可能不相等，所以有向图的RWR算法计算节点s和节点pathalltst的相似性可以写成两者之和的平均即：ppsttsp（4-6）stts,2对无向图来说，如果最终P收敛于一个稳态向量，那么只计算st的概率即可。在对候选致病基因排序时，仅使用RWR往往还不够，因为网络中存在一些度比较高的节点，也就是通常所说的中心节点，或者Hub节点，这些节点在多数情况下并不是致病基因，所以在计算起始点节点s到其余节点的概率后还应该消除Hub节点对计算结果的影响，文章[15]使用了PageRank计算出了粒子随机访问节点t的全局概率pt，然后定义了变量pstscorets()（4-7）pt作为从s出发到其余各个节点的排序依据。4.4有监督随机游走带权的网络上进行随机游走需要考虑不同边的权值对结果的影响，特别是整合不同数据源后，不同类型节点间存在不同类型的关系。目前在进行筛选时主要是-29- 哈尔滨工业大学工学硕士学位论文随机选出一些测试集，固定其它类型的边的权重为1，逐步增加该边的权重，在网络上运行RWR算法，记录效果最好的权重，依次实验每条边，最终将记录出的所有类型的边的效果最好的权重整合在一起。这种方式找到的权值往往并非最优的，而且人工选择权值是十分耗时和枯燥的。有监督的随机游走（SupervisedRandomWalk，SRW）适用于链路预测，当网络中的边具有多个特征时，如何确定这些特征的在预测链路时的重要度是有监督随机游走模型要解决的问题。本研究中利用有监督随机游走模型来训练不同边类型的权重，定义边强度函数f其中wxwxwxwx，uvuvnn112233wi,1,n,为要学习的权重，xi,1,2,n,为当前边对应的特征。边强函数的值ii经过列归一化后成为当前边的转移概率矩阵，通过正负例的训练，使得权值偏向于特定的问题，从而提高预测效果。SRW对应的优化问题的目标函数如公式4-8所示：12min()Fww()hppld（4-8）w2dDlL,其中，D是正例集合，L是负例集合，w为要学习的特征权值，称为学习率，用于平衡模型复杂度和学习速度，值越大，说明对错分的惩罚越大，反之对错分的容忍越强。pp,分别为以s为起点使用RWR算法计算出来的节点ld,的稳态概ld率，h()为损失函数，满足当pp时，h0，当pp时，h0，在本文ldld中使用公式4-9作为损失函数。1hx（4-9）x1eb此损失函数又称为WMW（Wilcoxon-Mann-Whitney）损失，当b越小，错分的结果对损失函数的影响越大。图4-1表示在bbb1,0.01,2时的WMW函数的形状。b用来在梯度下降算法到的小步长情况下找到最优解，提高AUC（AreaUnderrocCurve）值。设Q为经边强函数f映射后按列归一化的邻接矩阵，边强函数定义为Logisticuv函数auvifuv(,)EQuvwauv（4-10）0otherwise1其中af。uvuv()xw1e-30- 哈尔滨工业大学工学硕士学位论文图4-1不同b值对损失函数的影响利用式4-10，定义QQS(1)，s为返回点则Q(1)Q1(vsuvV),（4-11）uvuv()kT又因Pppp12,,,n，是第k次迭代的概率向量()kk(1)PQP（4-12）对损失函数求导可得Fw()hp()pldwwwld,（4-13）h()ppldldwld.ldww其中ppQujjuQpjuj（4-14）wjwwff()()wjuwjkkkffwjkwjuQwwju(1)（4-15）2wkfwjkp式4-14中两端都包含要求的偏导u，在编程实现时需要递归计算，类似于w-31- 哈尔滨工业大学工学硕士学位论文矩阵迭代的幂法，给出初值，直到迭代收敛。在计算梯度时，对无约束问题，可以使用梯度下降算法更新偏导，最小化损失函数，也可以使用L-BFGS等快速算法计算。对于起始点有多个的训练集，需要设置多个起点进行训练，设起点集合为S此时损失函数为12min()Fww()hppld（4-16）w2sSdDlLss,多起点的损失函数各个起点的计算过程相互独立，可以根据起点并行计算，加快计算过程。同时应该注意到，SWR算法多数情况下并不收敛到最优解，需要设定多个权值向量的初值，进行多次迭代，选择一个使损失函数最小的解。4.5拉普拉斯正规化的有监督随机游走4.5.1基本原理图的边权的拉普拉斯正规化常用来处理有权重的网络的权值[55]，它将边的端点的度信息整合起来，在文[16]中又称为度惩罚，形式化的定义是：设AAij[],,N1,2,,，当ij有边相连时，A不为0，否则为0，D是对角矩ijji阵，DAiiji，Dijij0,。称jAijA（4-17）ijDDiijj为A的拉普拉斯正规化。在无标度网络中，对边的拉普拉斯正规化可以部分消除中心节点的影响。图4-2带权网络局部示例如图4-2所示，当粒子在a点时，设a有两条出链，权重分别为0.9和0.6，分别除以出度的权值和后为0.6和0.4，显然粒子选择c的概率更大，利用拉普拉斯正规化，使a的出度和为1，得到ab边的权值为0.524，ac边的权值为0.476，粒-32- 哈尔滨工业大学工学硕士学位论文子选择ab边到节点b的概率大于选择到节点c的概率。这种处理弱化了hub节点的影响，使得粒子在随机游走时能够同时考虑到目标节点的度和边的权重。本文提出了一种基于拉普拉斯正规化的有监督随机游走（LN-SRW）方法，使用正规化后的边权计算如式4-18，将边强函数计算的结果再进行拉普拉斯正规化。auvfuvaguvuv()（4-18）aauijvffuijviNu()jNv()iNu()jNv()正规化的转移矩阵Q为auvifuv(,)EQuvwauv（4-19）0otherwise对转移矩阵的每个元素求w的偏导，gg()()wjuwjkkkggwjkwjuQwwju(1)（4-20）2wkgwjk其中，ffuvuvg()wwffuvuvuv（4-21）2wfuvffuvfuijv()（4-22）iNu()jNv()fuifjvffjvuifuviNujNv()()ww（4-23）w2ffuijviNu()jNv()分析上述式子，可以发现，LN-SRW算法在计算每个有权边的偏导时将f函数替换成了g函数，计算每个权值的偏导的复杂度比SRW算法增加了OE，因SRW算法本身的复杂度就很高，在计算偏导的过程中需要进行两次幂法进行迭代计算pip和，直到它们收敛。为了简化计算复杂度，本文又提出了一种简化的LN-SRWiwi算法（SimpleLaplacianNormaliation-SupervisedRandomWalk，SLN-SRW），该算法将式4-18简化为-33- 哈尔滨工业大学工学硕士学位论文auvfuvaguvuv()（4-24）DuDv()()()DuDv()其中DiiV(),表示图G中节点i的度，和训练的参数无关。相应的，其他公式保持其他不变，除了函数g对w的偏导更改为f()uvg()wuv（4-25）wDuDv()()这样一来，式子中的分母和要训练的参数w无关，SLN-SRW计算复杂度和SRW的计算复杂度持平。4.5.2算法实现LN-SWR算法计算过程类似于SWR算法需要使用幂法迭代，迭代次数和要估计的参数个数有关，设w参数向量的个数为n，则需要幂法迭代次数为12n次才能完成一次参数估计，其中计算稳态概率需要一次幂法迭代，对每个待估计参数，pQju需要计算,,1in，所以需要2n次幂法迭代，见图4-5。故根据算法流程，wwii可以将训练过程分为有返回随机游走的实现和迭代计算偏导的实现，分别对应图4-5中的第二步和第四步。图4-5SLN-SRW估计参数流程有返回的随机游走的算法利用式4-5，首先对状态概率矩阵进行初始化，设返回点为s，按列归一化的状态转移矩阵为Q，计算公式(1)QS来生成新的状态转移矩阵，S为二维矩阵，大小同Q，重启点s所在的行全为1，矩阵其-34- 哈尔滨工业大学工学硕士学位论文余元素为0。具体算法参见算法4-1。算法4-1有返回随机游走算法（RWR算法）输入：图GVE(,)，起始点s，重启概率，停止误差eps，初始权值w输出：稳态概率向量P（1）根据图中的带权边，和初始边权值w，使用边强函数始化状态转移矩阵Q，和矩阵S，稳态向量P，迭代次数t10（2）计算Q(1)QS（3）whilePPepsdott1（4）PQSP(1)tt1（5）tt1（6）endwhile（7）reuturnPt计算权值偏导时，需要同时计算稳态概率和状态转移矩阵对待估计参数的权值偏导，此过程需要进行两次幂法迭代，具体过程见算法4-2。在第七步时需要利用公式4-23来计算边强函数对权值的偏导，SLN-SRW算法则利用式4-25来计算边强函数对权值的偏导。算法4-2LN-SRW权值更新算法输入：图GVE(,)，起始点s，重启概率，停止误差eps，初始权值w，通过算法4-1计算出的稳态概率向量P输出：更新后的权值w，1ini（1）根据图中的带权边，和初始边权值w，使用边强函数始化状态转移矩阵Q，和矩阵S，稳态向量P，迭代次数t10（2）fork=1ton()tt(1)pp（4）whileepsdowwii（5）foruVdo（6）forvVdo（7）计算u到v节点的边强函数a对w的偏导uvk计算Q对每个w的偏导uvk（8）endforp()tpQ(1)t(1)t（9）计算j(1)tjujpjwwwikk-35- 哈尔滨工业大学工学硕士学位论文算法4-2（续）（10）endfor（11）t=t+1（12）endwhileF（13）更新权值wwkkwk（14）endfor（15）returnw4.6加权有监督随机游走的致病基因预测据已有的双层异构本体-基因网络，本文按照边类型的不同定义7种不同的边权，分别为GO-GO，GO-GENE，DO-DO，DO-GENE，HPO-HPO，HPO-GENE，GENE-GENE，每种类型具有一个或多个子类型，每个子类型的边权值又由一个或多个证据代码通过式3-1计算出，如GO到GENE的边权值由15种证据代码组合而成，GO到GO的边由isa,partof,regulates三种类型的子类型组成。图4-6边权对RWR算法的影响为了验证不同边的权值是否对分类结果有直接影响，使用RWR算法，在双层异构本体-基因网络中随机选择100条边作为正例，任意选择两个端点，若这两个端点不在网络中且不在正例中，就将这两个端点组成的边加入负例集合，直到生成100个负例。在网络上删除正例集合内所有的边，针对7中类型的边设置不同的权值，固定其它6条权值为1，单独改变余下的一条边的权值，权值变化从0到5.8，-36- 哈尔滨工业大学工学硕士学位论文步长为0.2，固定重启概率为0.25，画出分类的AUC变化曲线，可以发现不同类型的权值对AUC有不同影响，DO-GENE最显著，其次是DO-DO，然后是HP-HP，GO-GO和GENE-GENE对致病基因预测的显著性最低，说明对边进行分类有意义。本文提出了一种方法，可以使用SRW将这7种权值计算出来，首先将7种不同的边类型作为特征放入边的特征集合中，每种类型的边都有一个权值对应，然后在特征向量中最后加入1作为偏置项。这8种特征，对应的要估计的权重为wdodowwwhpohpo,,w,,,w,,wgogowdogenehpogenegogenegenegenebias，DO-DO边类型的特征为score,0,0,0,0,0,0,1，HPO-HPO边类型的特征为{0,,0,0,0,0,0,1}score，GO-GO边类型的特征为0,0,,0,0,0,0,1score，DO-GENE边类型的特征为{0,0,0,,0,0,0,1}score，HPO-GENE边类型的特征为0,0,0,0,0,score,0,1，GO-GENE边类型的特征为0,0,0,0,,0,0,1score，GENE-GENE边类型的特征为0,0,0,0,0,0,,1score。需要特别注意的是DO-HPO部分节点重合，一条DO-GENE的关系可能也是HPO-GENE的关系，这里将特征向量设置为{0,0,0,,0,score,0,1}score，构建训练集和测试集，使用SRW，SLN-SRW对特征权值进行训练，使用训练后的数据在测试集上测试，对比传统的RWR算法验证算法的有效性。最后再使用训练出的权值来进行致病基因排序和预测。这种处理类似于RWRH算法，不过比RWRH算法多出了5种类型的“跳转概率”，表示为pi,1,,7。每种边类型的权值可以一定程度上转化成当前边类型在i网络上的跳转概率。与RWRH不同的是，这里的跳转概率是使用训练的方法得到的。将网络转化成矩阵表示的形式如式（4-26）所示TppM00M1do4dgT0M0Mpp2hp6hgM（4-26）00MMppT3go5gogep4pgdMp6pghM5gegoMM7gene其中，M,M,M,M分别表示四个子网络各自的邻接矩阵，每个邻接矩dohpgogene阵都有一个权值，MMM,,为三个本体之间的边组成的邻接矩阵，为了简化gogedghg表示方式，这里忽略了DO和HP重合的部分。在算法实现中，考虑到多个起始点sS的计算可以并行化，于是使用了多线程技术加快计算进度，另外前文讨论过b值可以用来控制损失函数，当b值越小，损失函数在小步长内更容易找到一个局部最优解，本文在实现时先使用L-BFGS算法在b值较大的时候快速找到一个近似局部解，然后使用较小的b值和较小的学习-37- 哈尔滨工业大学工学硕士学位论文率在小范围内进行固定次数的梯度下降计算，使得训练的参数进一步接近局部最优。具体实现框图见图4-6。图4-7权值训练实现框图4.7本章小结本章首先介绍了随机游走的基本原理，并根据马氏链的性质，介绍了齐次马氏链能求得稳定向量的基本条件，在此基础上给出了目前常用的疾病预测模型的有返回随机游走模型。并根据基本-本体异构网络的特性，引入有监督的随机游走模型，将本体-基因网络的边分为7大类，构建训练集和测试集，使用SRW算法估计不同类型的边权，同时考虑到中心节点对致病基因预测的影响，对边权做入拉普拉斯正规化处理，将SRW扩展为LN-SRW算法，针对LN-SRW复杂度过高，计算速度慢的问题，又提出了简化版的SLN-SRW算法，最后说明了如何将有监督随机游走算法应用于训练边权，来提高致病基因预测的效果。-38- 哈尔滨工业大学工学硕士学位论文第5章实验结果与分析5.1改进的有监督随机游走有效性验证为了验证提出的LN-SRW算法和SLN-SRW算法，本文随机生成了300个，节点数目为1000的无向无标度网络，生成网络的算法使用文献[53]提出的拷贝模型，具体为，首先生成有三个点相互连接的基本图，剩余的节点一个一个到达，假设到达节点为u，目前已经添加到图中的节点集合为Vvvv{,,,vn,},1000，u将123n要生成三条新边，新边生成的规则如下：（1）首先生成1,10的随机数rand；（2）当rand8时，在集合V中随机选择v，连接uv，作为一条新边；ii（3）当rand8时，以V中每个节点的度来进行选择，度越高，被选择的概率越大。在生成无标度网络时，本文为每条边生成了两个随机特征，这两个特征满足均1值为0，方差为1的正态分布。使用边权函数，损失函数同式4-9，学习率xw1e1，损失函数中b0.03，重启概率0.2，固定要预测的特征权值为w[1,1]。随机选择基本图的三个顶点的一个作为起始点s，使用w初始并归一化邻接矩阵A，在图上执行重启概率0.2的RWR算法，对除了s之外的其他节点i按照稳态概率p进行从大到小排序。选取前20个节点，且这些节点在图中不直接和s相i连，作为训练的正例集合D，其余的且不和s直接相连的节点集合作为负例集L。生成的无标度网络是无向图，在这些无向图上分别使用SWR，LN-SWR，SLN-SWR算法，计算训练出的权值w，计算训练出的权值和实际的权值w的差异程度，差异程度计算使用绝对误差（式5-1）和来评价，误差越小，表明模型在预测权值上越准确。2*errorwiiw（5-1）i1分别对三种算法重复100次试验，共计300次实验，三类实验中所有参数保持一致，且参数能够保证当前实验能够找到一个局部最优解。对实验结果，使用t检验检测试SRW算法的误差均值是否显著大于其它两种算法的均值，t检验的前提是样本满足正态性和方差齐性，所以首先应检测样本是否满足正态性，分别画出三个算法计算出的样本误差直方图的正态拟合曲线和PP图（图5-1），可以看到三张图中多数点都落在PP图的对角线上，说明三种误差样本符合正态分布。对于这-39- 哈尔滨工业大学工学硕士学位论文三种样本分别实施F检验，原假设为SRW，LN-SRW方差齐性和SRW,SLN-SRW方差齐性，p值分别为0.5092和0.4259，都大于显著水平0.05，故接受方差齐性的原假设。srwsrwln对三类样本进行单侧t检验，备择假设H为SRW误差均值大于1srwssrwlnLN_SRW误差均值，备择假设H为SRW误差均值大于LN-SRW误差均值，1结果表明两种单边检测的p值均小于0.05（见表），说明结果具有统计学意义的显著性，接受备择假设，拒绝均值无显著性差异的原假设。绝对误差和的最大值是2，最小值为0，三种算法的盒图见图5-2，LN-SRW的误差分布多数在0.5以下，这使得LN-SRW的误差低于SRW的误差和。SLN-SRW算法和LN-SRW算法并无显著性差异，不过在计算效率上SLN-SRW明显要优于LN-SRW算法。表5-1t检验验证LN-SRW和SLN-SRW的均值对SRW显著性程度备择假设P值T值说明SRW误差均值大于LN-SRW误差均值0.02002.0677SRW误差均值：0.5539LN-SRW误差均值：0.4853SRW误差均值大于SLN-SRW误差均值0.00402.6451SLN-SRW误差均值：0.4723图5-2SRW，LN-SRW，SLN-SRW三种算法的盒图对比-40- 哈尔滨工业大学工学硕士学位论文图5-1SRW，LN-SRW，SLN-SRW误差频数正态拟合和PP图5.2实验环境与实验数据本文中涉及的随机游走相关的算法全部使用Linux64位平台Java7实现，并使用了斯坦福大学的edu.stanford.nlp包中的L-BFGS库来更新计算梯度下降。当前网络中的节点共计78786个，105875条有向边，398642条无向边，有向边只存在于本体术语间的关系中。整合不同数据源的中间结果和最终结果都存储在MySql数据库中。计算过程中使用邻接链表方式，若使用邻接矩阵的形式，则需要50GB左右的内存空间，内存消耗太大。经统计，在本体与基因网络上运行单线程的SRW算法时，消耗的内存大约为18GB，其中每个待训练的边特征权值偏导都需要一个邻接链表存储，边的特征越多，需要的存储空间越大。当使用10个线程分别运行不同起始点的SRW算法时，消耗的内存约190GB，每次迭代收敛的时间在30-40-41- 哈尔滨工业大学工学硕士学位论文分钟。LN-SRW算法复杂度太高，实验时使用SLN-SRW算法替代LN-SRW。疾病和致病基因选取参考文献[15]的选取规则，抽取疾病本体术语到关联基因的边权在整合后的证据得分大于等于0.8，且筛选后基因总数大于5的16种疾病，见表5-2共计430个条关联边，本文中的所有试验的验证都是基于这430条疾病基因关系。表5-2实验使用的数据疾病名称全局标识本体标识关联基因数量AneimaC0002871DOID:235523HemolyticanemiaC0002878DOID:583,HP:000187814CardiomyopathiesC0878544HP:000163846Charcot-Marie-ToothDiseaseC0007959DOID:1059521DiabetesC0011849DOID:935120DystoniaC0013421HP:000133213LeukemiaC0023418DOID:1240,HP:000190932LymphomaC0024299HP:000266517MuscularDystrophyC0026850DOID:9884,HP:00035609MyopathyC0026848DOID:423,HP:000319827ParkinsonDiseaseC0030567DOID:1433072RetinitisPigmentosaC0035334HP:000051067SpasticParaplegiaC0037773DOID:247635UsherSyndromesNMAP12546DOID:005043912XerodermaPigmentosumNMAP12777DOID:00504278ZellwegerSyndromeC0043459DOID:905145.3实验结果验证方法和正负例生成目前的实验分为两类，一类是致病基因的预测，一类是致病基因的排序。对于致病基因的预测，分为无监督的致病基因预测和有监督的致病基因预测，有监督的致病基因预测是在无监督的致病基因预测的基础上加入训练的权值，需要将数据分为训练集合和测试集合。致病基因预测的评价需要构建正例和负例集合，ROC（ReceiverOperatingCharacteristicCurve）曲线和计算AUC值来评价算法好坏。致病基因排序可以看做是致病基因预测的变形，将测试集按照随机游走给出的稳态概率进行排序，按正例排名来决定排序效果的好坏。致病基因排序主要使用查全率来判断排序效果的好坏：TPRecall（5-2）P-42- 哈尔滨工业大学工学硕士学位论文其中，真正（TruePositive，TP）表示算法预测的基因为致病基因的个数，P表示所有致病基因的个数。设置一个k值，计算在前k%中包含致病基因的个数，最后画出查全率和k变化的曲线。致病基因预测可以看做一个分类问题。其评价标准使用ROC曲线，ROC曲线的纵轴是真正率（TruePositiveReate，TPR），横轴是假正率（FalsePostiveRate，FPR），TPR和FPR的定义如下：TPTPR（5-3）TPFNFPFPR（5-4）FPTN其中，假负（FalseNegative，FN）致病基因被预测为非致病基因的个数，真负（TrueNegative，TN）表示非致病基因被正确预测的个数，假负（FalsePositive，FP）表示非致病基因被预测为致病基因的个数。注意到TPR和Recall的公式一样，他们表达的意义相同，又被称作灵敏度。AUC曲线是ROC曲线下的面积是用来评价分类效果好坏的指标。致病基因预测的正例集是430个疾病-基因边的集合，首先将16种疾病关联基因的边从网络中全部删除，对这430条边随机选取一半边作为正例测试集，剩下的一半边作为正例训练集，随机选取16种疾病的一种作为一个端点，随机选取430条边中的一个基因作为另外一个端点，当这两个端点组成的边不在网络中，且不在原始的430条边中，就将这个随机生成的边作为负例。重复这个过程，直到最后生成数量和正例训练集和测试集数量相当的两个负例测试集和训练集。5.4实验结果5.4.1重启概率的选择对于RWR算法的重启概率，本文首先将本体之间的关系看做无向图，在训练集上运行无向图的RWR算法，然后又将本体之间的关系看做有向图，在训练集上运行有向图的RWR算法，使用每条边整合后的得分作为边的权重，同时按从0,1变化，步长为0.1画出AUC变化曲线（图5-2）。可以看到，当将本体术语间当作无向边时，计算出的AUC值显著大于将本体之间关系看作有向边的情况。所以本文余下的实验全部在无向图上进行。经分析，本体中虽然is-a关系是单向的，但是语意上的关系，若基因和A相关，AisaB，我们说基因也和B相关，当基因和B相关，AisaB，并不表示基因完全和A无关。为了简化这种语义关系，本文简单的将isa，partof，regulates当做无向边。当-43- 哈尔滨工业大学工学硕士学位论文取值为0.6时，得到的AUC值最大，所以RWR算法的重启概率取值为0.6。图5-2RWR算法在无向图和有向图的AUC曲线图5-3SRW，SLN-SRW，RWR算法在训练集不同时的AUC曲线对SRW和SLN-SRW算法，同样在无向图上按0.1的步长从0.1到0.9更改重启概率，计算在训练集上的AUC变化曲线（图5-3），可以看出SRW算法在训练集上的AUC值明显高于RWR算法，且SLN-SRW在训练集上比SRW算法稍好，对SLN-SRW算法，选择重启概率为0.2，对SRW算法，选择重启概率为0.6，-44- 哈尔滨工业大学工学硕士学位论文当越大，表明返回的概率越大，算法越倾向于找到离起始疾病距离比较近的基因，这种特性满足致病基因常常聚集分布的特性。不过注意到SLN-SRW算法的重启概率比较小，说明部分致病基因跟已发现的致病基因间聚集性并非那么强，位于致病基因聚集的边缘。另外在变化时，SRW和SLN-SRW的变化AUC值变化范围不大，说明有监督学习的随机游走对返回值变化不敏感。当重启概率为0.9时，节点倾向于在自己周围游走，所学习的权值特征有限，导致了三种算法在重启概率为0.9时AUC值相近。在重启概率为1.0时，SRW，SLN-SRW学习不到新特征，每个特征的权值都为0。5.4.2实验结果对比据上节实验，得到了重启概率的较优值，使用训练出的特征权值和重启概率，在测试集上进行实验，比较三种算法的ROC曲线和AUC值，对SWR和SLN-SWR算法，L-BFGS使用学习率1，WMW损失函数中b1，局部梯度下降阶段，设置0.000001，WMW函数中使用b0.03，重复5次随机初始权值，针对每次初始的权值，设置L-BFGS的迭代次数为25次，超过25后停止计算，最后使用梯度下降微调特征权值，设置最大迭代次数也为25次。如图（5-4）所示，其中RWR曲线的AUC为0.769，SWR算法AUC值为0.777，SLN-SWR算法的AUC值为0.792。使用SRW和SLN-SRW训练出的权值参见表5-3，其中W1代表的是DO-DO的边类型，W2代表的是HPO-HPO的关系，W3代表的是GO-GO的关系，W4代表的是DO-GENE的关系，W5代表的是GO-GENE的关系，W6代表的是HPO-GENE的关系，W7代表的是GENE-GENE的关系，W8表示的是偏执项，表中数据来自0.2的SLN-SRW，=0.6的SRW和0.6的RWR算法。表5-3三种模型使用的参数方法W1W2W3W4W5W6W7W8AUCSWR0.680.680.23-0.72-0.26-0.49-0.49-0.450.777SLN-SWR1.832.071.84-1.73-0.86-1.38-1.37-2.590.792RWR1.001.001.001.001.001.001.00N/A0.769通过对比发现，在假阳性率为0.3到0.7的区间内，SLN-SRW算法的没有显著增加，但是在0到0.3的区间和0.7到1的区间内SLN-SRW算法的灵敏度高于SRW算法，表明SLN-SRW算法对多数正例有提升效果。同时使用训练出的特征权值比不直接使用随机游走的效果有所提升。致病基因预测的结果可以直接使用致病基因预测结果，根据分类概率从大到小排序，然后依次改变k值，统计正例的比例，画出查全率曲线（图5-5）。可以看-45- 哈尔滨工业大学工学硕士学位论文到，从前80开始，SLN-SRW算法的效果要高于其他两种方法，SRW的效果稍好于RWR。图5-4测试集上三种算法的ROC曲线图5-5查全率曲线-46- 哈尔滨工业大学工学硕士学位论文SLN-SRW本身还可以添加额外的特征来丰富边的特征，而权重本身的大小还代表了此特征在当前问题中的分类效果。本文中又在边的特征上加入了共同邻居的特征，最后发现训练出的权重只有0.00014，说明这个特征对于当前的训练集效果不大，可能是当前图的稀疏性，导致不同类型节点之间的关系没有太多共同邻居，多数节点的共同邻居的特征数量为0，使该特征不显著。5.5本章小结本章主要对本文中所提出的实验方法进行验证，通过具体实验对提出的方法进行数据统计。首先，使用这三种算法在随机生成的无标度网络上进行多次测试，使用训练参数的绝对误差和来评价算法的优劣，发现LN-SRW和LN-SRW算法的绝对误差和显著低于SRW算法的误差和，具有统计显著性。其次，介绍了相关实验的环境，和内存消耗以及评测数据集的选择，然后给出了评测方法和构建正负例训练样本，正负例测试样本的方法。接下来针对不同的方法，选择不同的重启概率，使得评测尽量做到公平公正。根据第四章给出的每种类型的边的特征向量，使用SRW，SLN-SRW算法进行权值训练，并在测试集上和全1权值的RWR算法进行比较，证明了在致病基因预测方面，使用SRW算法的效果比RWR算法要好，并且SLN-SRW算法在保证时间复杂度不增加的情况下，能够提升SRW算法的精度。最后将致病基因预测转化为致病基因排序问题，使用查全率发现SLN-SRW算法能够较好的提升致病基因的排名。-47- 哈尔滨工业大学工学硕士学位论文结论使用整合的生物网络对致病基因预测是当前生物信息学研究的一个重要方向，在整合网络的过程中如何在保证数据质量的情况下去除冗余信息，组织和构建一个有意义的生物网络，并对此生物网络进行合理的利用来预测致病基因是本文要解决的主要问题。本文的主要研究及成果如下：（1）基于基因本体，人类表型本体，疾病本体和本体注释数据，疾病基因关系数据库，蛋白质相互作用数据库等9种数据源构建了一个具有7万个节点，和近50万条边的双层异构网络。为了减少数据冗余和扩充网络的关系，在构建过程中使用了4个数据库来做不同来源数据标识到统一标识的映射。在保留原始节点特征的基础上设计了一套整合边的证据代码计算权值的策略，最终形成了一个带权的双层异构网络。（2）提出了不同边类型在预测致病基因时重要程度不同的假设，并对该假设进行了验证，最后将网络中的变分为了7个大类，对每类边定制了各自特征向量生成的规则，使用有监督的随机游走模型对这7类边权进行训练，使随机游走有偏的选择不同类型的边，从而达到提高AUC值的目的。（3）提出了拉普拉斯正则化的有监督随机游走，使算法在训练过程中能够综合考虑边端点的度和边的权值，针对拉普拉斯正则化的有监督随机游走训练时时间复杂度较大的情况，又提出了简化版的改进算法。实验表明，简化的算法能够在同样的复杂度下获取较好的结果。虽然整合本体数据构建网路，在网络上将有监督和无监督结合起来进行疾病预测具有可行性，但是也有部分需要完善的方面：（1）有监督随机游走算法可以加入新的特征来提高预测效果，本文只测试了共同邻居的特征，在这方面并没有做进一步的研究。（2）因数据源的不同，且目前缺乏一个统一的测试集来评测效果，这里很难和其它不同种类的算法进行对比，只对比了经典的随机游走。（3）只利用了本体自身的关系，没有尝试构建本体相似度网络，研究表明，使用本体相似性网络会提高基因预测的效果。基于随机游走的致病基因预测在实际应用中表现出比较好的效果，多数据源的异构网络的致病基因预测近年受到越来越高的关注，相信随着数据的丰富，新的整合技术和预测技术的提高，致病基因预测会越来越精准，同时也能够为研究人员提供更可靠的结果。-48- 哈尔滨工业大学工学硕士学位论文参考文献[1]ConsortiumTGO,AshburnerM,BallCA,etal.GeneOntology:ToolfortheUnificationofBiology[J].NatureGenetics,2000,25(1):25-29.[2]LynnMarieS,CesarA,SuvarnaN,etal.DiseaseOntology:ABackboneforDiseaseSemanticintegration[J].NucleicAcidsResearch,2012,40(D1):940-946.[3]ConsortiumUP.TheUniversalProteinResource(UniProt)in2010[J].NucleicAcidsResearch,2010,38(D1):71–75.[4]ZdobnovEM,ApweilerR.InterProScan--AnIntegrationPlatformfortheSignature-RecognitionMethodsinInterPro[J].Bioinformatics,2001,17(9):847-848.[5]BodenreiderO.TheUnifiedMedicalLanguageSystem(UMLS):IntegratingBiomedicalTerminology[J].NucleicAcidsResearch,2004,32(Databaseissue):267-270.[6]SzklarczykD,FranceschiniA,WyderS,etal.STRINGv10:Protein-ProteinInteractionNetworks,IntegratedovertheTreeofLife[J].NucleicAcidsResearch,2015,447-452.[7]HuntleyRP,TonyS,PrudenceMM,etal.TheGOADatabase:GeneOntologyAnnotationupdatesfor2015[J].NucleicAcidsResearch,2015,43(Databaseissue),1057-1063.[8]OgataH,GotoS,SatoK,etal.KEGG:KyotoEncyclopediaofGenesandGenomes[J].NucleicAcidsResearch,2000,28(1):29-34.[9]TenesaA,HaleyCS.TheHeritabilityofHumanDisease:Estimation,UsesandAbuses[J].NatureReviewsGenetics,2013,14(2):139-149.[10]DavidA,DalyMJ,LanderES.GeneticMappinginHumanDisease.[J].Science,2008,322(5903):881-888.[11]KohlerJ,BaumbachJ,TaubertJ,etal.Graph-basedAnalysisandVisualizationofExperimentalResultswithONDEX[J].Bioinformatics,2006,22(11):1383-1390.[12]BirklandA,YonaG.BIOZON:ASystemforUnification,ManagementandAnalysisofHeterogeneousBiologicalData[J].BmcBioinformatics,2006,7(4):514-515.[13]BellL,ChowdharyR,LiuJS,etal.IntegratedBio-EntityNetwork:ASystemforBiologicalKnowledgeDiscovery[J].PlosOne,2011,6(6):2592-2599.[14]FidelRamirez,GlennLawyer,MarioAlbrecht(2012)NovelSearchMethodfortheDiscoveryofFunctionalRelationships[J].Bioinformatics,28,269–276.-49- 哈尔滨工业大学工学硕士学位论文[15]LiekensAM,KnijfJD,DaelemansW,etal.BioGraph:UnsupervisedBiomedicalKnowledgeDiscoveryviaAutomatedHypothesisGeneration[J].GenomeBiology,2011,12(6):1-12.[16]EronenL,ToivonenH.Biomine:PredictingLinksBetweenBiologicalEntitiesusingNetworkModelsofHeterogeneousDatabases[J].BmcBioinformatics,2012,13(17):89-95.[17]陈坚，何洁月.基于本体的生物信息集成技术发展现状[J].计算机工程与科学，2006，28（12）：l18-120.[18]林毅，宁洪，王挺，刘文杰.基于本体的生物信息集成研究[J].计算机工程与应用，2008（44）：18-20.[19]隽立然.基于生物医学本体的生物信息数据库集成方法研究[D].哈尔滨：哈尔滨工业大学计算机科学与技术学科硕士论文，2009[20]Oti1M,SnelB,Huynen1MA,BrunnerHG:PredictingDiseaseGenesUsingProtein–ProteinInteractions[J].JMedGenet2006,43:691–698.[21]KrauthammerM,KaufmannCA,GilliamTC,RzhetskyaA:MolecularTriangulation:BridgingLinkageandMolecular-networkInformationforIdentifyingCandidateGenesinAlzheimer’sDisease[J].PNAS2004,101(42):15148–15153.[22]KohlerS,BauerS,HornD,RobinsonP:WalkingtheInteractomeforPrioritizationofCandidateDiseaseGenes[J].AmJHumanGenet2008,82(4):949–958[23]VanunuO,MaggerO,RuppinE,etal.AssociatingGenesandProteinComplexeswithDiseaseviaNetworkPropagation[J].PlosComputationalBiology,2010,6(1),e1000641:1-9.[24]AsthanaS,KingOD,GibbonsFD,RothFP:PredictingProteinComplexMembershipusingProbabilisticNetworkReliability[J].GenomeRes2004,14:1170–1175.[25]WangJ,GangC,MinL,etal.IntegrationofBreastCancerGeneSignaturesBasedonGraphCentrality[J].BmcSystemsBiology,2011,5(6):1-10.[26]LiJ,EdwardsSM,BoT,etal.ARandomSetScoringModelforPrioritizationofDiseaseCandidateGenesusingProteinComplexesandData-miningofGeneRIF,OMIMandPubMedRecords[J].BmcBioinformatics,2014,15(22):315-315.[27]ValentiniG,PaccanaroA,CanizaH,etal.AnExtensiveAnalysisofDisease-geneAssociationsusingNetworkIntegrationandFastKernel-basedGenePrioritizationMethods[J].ArtificialIntelligenceinMedicine,2014,61(2):63–78.[28]LageK,KarlbergEO,StørlingZM,etal.AHumanPhenome-interactomeNetworkofProteinComplexesImplicatedinGeneticDisorders[J].NatureBiotechnology,2007,25(3):309-316.-50- 哈尔滨工业大学工学硕士学位论文[29]DonchevaNT,TimK,MarioA.RecentApproachestothePrioritizationofCandidateDiseaseGenes[J].WileyInterdisciplinaryReviewsSystemsBiology&Medicine,2012,4(5):429-442.[30]NúriaLB,OuzounisCA.Genome-wideIdentificationofGenesLikelytobeInvolvedinHumanGeneticDisease[J].NucleicAcidsResearch,2004,32(10):3108-3114.[31]XuJ,LiY.DiscoveringDisease-genesbyTopologicalFeaturesinHumanProtein-ProteinInteractionNetwork[J].Bioinformatics,2006,22(22):2800-2805.[32]JiaP,KaoCF,KuoPH,etal.AComprehensiveNetworkandPathwayAnalysisofCandidateGenesinMajorDepressiveDisorder[J].BmcSystemsBiology,2011,5(30):3575-3588.[33]NitschD,GonçalvesJP,OjedaF,etal.CandidateGenePrioritizationbyNetworkAnalysisofDifferentialExpressionusingMachineLearningApproaches[J].BmcBioinformatics,2010,11(3):1-16.[34]ChenB,WangJ,LiM,etal.IdentifyingDiseaseGenesbyIntegratingMultipleDataSources[J].BmcMedicalGenomics,2014,7(Suppl2):1-12.[35]UMartinSB,NagarajanN,AmbujT,etal.PredictionandValidationofGene-DiseaseAssociationsUsingMethodsInspiredbySocialNetworkAnalyses[J].PlosOne,2013,8(5):e58977:1-17.[36]WangJ,PengW,WuF.ComputationalApproachestoPredictingEssentialProteins:aSurvey[J].ProteomicsClinicalApplications,2013,7(1-2):181-192.[37]BaudotA,Gómez-LópezG,ValenciaA.TranslationalDiseaseInterpretationwithMolecularNetworks[J].GenomeBiology,2009,10(6):1-9.[38]ChengZ,KushwahaA,BermanK,etal.AVertexSimilarity-basedFrameworktoDiscoverandRankOrphanDisease-relatedGenes[J].BmcSystemsBiology,2012,6suppl3(6):1-9.[39]Perez-IratxetaC,BorkP,AndradeMA.AssociationofGenestoGeneticallyInheritedDiseasesUsingDataMining[J].NatureGenetics,2002,31(3):316-319.[40]FreudenbergJ,ProppingP.ASimilarity-basedMethodforGenome-widePredictionofDisease-relevantHumanGenes[J].Bioinformatics,2002,18suppl2(10):110-115.[41]ChenJ,AronowBJ,JeggaAG.DiseaseCandidateGeneIdentificationandPrioritizationUsingProteinInteractionNetworks.BMCBioinform10(1):73[J].BmcBioinformatics,2009,10:1-14.[42]BrinS,PageL,MotwaniR,etal.ThePageRankCitationRanking:BringingOrdertotheWeb[J].StanfordInfolab,1999,9(1):1-14.-51- 哈尔滨工业大学工学硕士学位论文[43]WhiteS,SmythP.AlgorithmsforEstimatingRelativeImportanceinNetworks[C]//ProceedingsoftheninthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM,2003:266-275.[44]NavlakhaS,KingsfordC.ThePowerofProteinInteractionNetworksforAssociatingGeneswithDiseases[J].Bioinformatics,2010,26(8):1057–1063.[45]WuX,JiangR,ZhangMQ,etal.Network-basedGlobalInferenceofHumanDiseaseGenes.[J].MolecularSystemsBiology,2008,4(1):189-200.[46]XinY,HanH,LiY,etal.Modularity-basedCrediblePredictionofDiseaseGenesandDetectionofDiseaseSubtypesonthePhenotype-geneHeterogeneousNetwork[J].BmcSystemsBiology,2011,5(11):4176-4200.[47]ZhouD,OrshanskiySA,ZhaH,etal.Co-rankingAuthorsandDocumentsinaHeterogeneousNetwork[C]//2013IEEE13thInternationalConferenceonDataMining.IEEEComputerSociety,2007:739-744.[48]RobinsonPN,KöhlerS,BauerS,etal.TheHumanPhenotypeOntology:AToolForAnnotatingandAnalyzingHumanHereditaryDisease[J].AmericanJournalofHumanGenetics,2008,83(5):610-615.[49]LandrumMJ,LeeJM,RileyGR,etal.ClinVar:PublicArchiveofRelationshipsamongSequenceVariationandHumanPhenotype[J].NucleicAcidsResearch,2014,42(Databaseissue):980-985.[50]AllanPeterD,CynthiaGrondinM,RobinJ,etal.TheComparativeToxicogenomicsDatabase:update2013[J].NucleicAcidsResearch,2012,41(2):1067-1072.[51]GrayKA,DaughertyLC,GordonSM,etal.Genenames.org:theHGNCResourcesin2013[J].NucleicAcidsResearch,2013,41(D1):545-552.[52]ChengL,WangG,LiJ,etal.SIDD:ASemanticallyIntegratedDatabasetowardsAGlobalViewofHumanDisease[J].PlosOne,2013,8(10):e75504:1-9.[53]BackstromL,LeskovecJ.SupervisedRandomWalks:PredictingandRecommendingLinksinSocialNetworks[C]//ProceedingsoftheFourthACMInternationalConferenceonWebSearchandDataMining.ACM,2010:635-644.[54]KumarR,RaghavanP,RajagopalanS,etal.StochasticModelsfortheWebGraph[J].Focs,2002:57-65.[55]ZhaoZQ,HanGS,YuZG,etal.LaplacianNormalizationandRandomWalkonHeterogeneousNetworksforDisease-genePrioritization[J].ComputationalBiology&Chemistry,2015,57:21–28.-52- 哈尔滨工业大学工学硕±学位论文哈尔滨工业大学学位论文原创性声明和使用权限学位论文原创性声明本人郑重声明：此处所提交的学位论文《基于本体与基因网络的致病基因预测研究》，是本人在导师指导下，在哈尔滨工业大学攻读学位期间独立进行研究工作所取得的成果，且学位论文中除己标注引用文献的部分外不包含他人完成或己发表的研究成果。对本学位论文的研究工作做出重要贡献的个人和集体，均已在文中Ｗ明确方式注明。２／作者签名；日期：年月引日学位论文使用权限学位论文是研究生在哈尔滨工业大学攻读学位期间完成的成果，知识产权归属哈尔滨工业大学。．学位论文的使用权限如下；（１）学校可抖采用影印、缩印或其他复制手段保存研究生上交的学位论文，并向国家图书馆报送学位论文（２）；学校可将学位论文部分或全部内容编入有关数据库进行检索和提供相应阅览服务；（３）研巧生毕业后发表与此学位论文研究成果相关的学术论文和其他成果时且第一，应征得导师同意，署名单位为哈尔滨工业大学。保密论文在保密期内遵守有关保密规定，解密后适用于此使用权限规定。本人知悉学位论文的使用权限，并将遵守有关规定。作者签名：日期：ッ＾＾＾年／２月３１日１６导师签名：私乐日期；＞年＇月争日－－５３ 哈尔滨工业大学工学硕士学位论文致谢本文从开题定题到最终论文的撰写的整个过程中，首先非常感谢我的导师王亚东教授的悉心指导，在两年半的学习生活中，感谢王老师教授了我学术方面的研究方法，帮我指点迷津，拓展学术思路，使得我对学术方面有了更深的了解，并将理论运用于实际的应用当中，感谢王老师在生活方面给予我们的帮助，使我们去年在回本部开题时能够有一个良好的学习环境，感谢实验室新购置的服务器让我能够顺利实现本文中的各种验证，也感谢陈津老师在收集数据时提供的专业性指导和建议。感谢中心的其他老师在自己的课题研究中提出的宝贵意见，他们严谨求实，循循善诱的教导给予了我深深的启迪。感谢我的师兄彭佳杰和詹青在本文研究的过程中给与无私的帮助和指导，感谢本数据组的成员李波、朱林娇同学在本课题的研究中给予的支持和帮助。感谢在论文审核过程中认真查看和提出宝贵意见的各位老师们。感谢研究中心的陈明明，邱实，马广煜和马成龙等同学，在科研的路上有他们的陪伴，生活更充实，感谢他们对我生活和学习上的关心和帮助。感谢邵玉凯同学陪我徒步走过深圳的大街小巷，希望你能够在未来走的更远。特别感谢樊静在我遇到困难时耐心听取我的抱怨，给与的鼓励和理解，浮生倥偬，有缘再见。最后，感谢自己的父母，在很多压力很大无处发泄的时候，父母的开导使我能够抛开压力，尽最大的努力做完自己的工作，不能轻易放弃。感谢他们在背后无私的、默默的付出。-54-
此文档下载收益归作者所有
