不确定生物网络比对算法研究

《不确定生物网络比对算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、隶．初大·粤硕士学位论文万方数据不确定生物网络比对算法研究万方数据ResearchonProbabilisticBiologicalNetworkAlignmentAlgorithmAThesisSubmittedtoSoutheastUniversityFortheAcademicDegreeofMasterofEngineeringBYZHAOMu-weiSupervisedbyHEJie-yueSchoolofComputerScience&EngineeringSoutheastUniversityJune2014万方数据东南大学学位论文独创性声明本人声明所呈交的学位论文是我个人

2、在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。研究生签延；车趋吼划东南大学学位论文使用授权声明东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文和在技术保护期限内的论文外，允许论文被查阅和借阅，可以公布(包括以电子

3、信息形式刊登)论文的全部内容或中、英文摘要等部分内容。论文的公布(包括以电子信息形式刊登)授权东南大学研究生院办理。研究生签志斗奎聊签名：，一，．碱f。，日期：万方数据摘要不断发展的生物实验测定技术产生了越来越多的生物网络数据，比如蛋白质相互作用网络、基因转录调控网络等，这些数据中蕴含了大量的关于各种有机体之间相互影响和相互作用关系的信息。如何解释和分析此类生物网络数据，已经成为当前生物信息学领域的一个亟待解决的问题。其中，有一类重要的研究工作就是生物网络数据的比较，即生物网络比对。生物网络比对，简言之就是要寻找两个(或多个)生物网络顶点之间的一组映射关系，使得生物网络之间的相似性得分最

4、高。值得注意的是，由于一些原因，比如生物网络中相互作用模块的规模、密度、冗余度以及模块间的距离，甚至生物实验的误差，都会导致测量得到的数据不完全准确，使得其中含有许多不确定事件(概率事件)，比如蛋白质相互作用网络中的边是以一定概率存在的，基因转录调控网络中的DNA也是以一定概率被转录成为RNA的。因此，在生物网络比对过程中，充分考虑和利用不确定信息，使用不确定图结构刻画原始网络，可以更准确地对现实情况进行建模，从而得到更准确的比对结果。然而，由于不确定图的概率特性，这些不确定信息在提高比对结果准确性的同时，也提高了算法的复杂度。目前绝大多数的生物网络比对算法都是针对确定生物网络比对问题而

5、设计的，仅有极少数的算法可以处理不确定生物网络数据。因此，本论文针对不确定生物网络比对进行了研究，主要工作包括：1、本文提出了一种改进的不确定生物网络比对算法PBNA(ProbabilisticBiologicalNetworkAlignment)。在确定生物网络比对算法IsoRank的基本框架之上，PBNA将不确定生物网络信息纳入到顶点相似性矩阵构建过程中，允许参与比对的两个网络中有一个为不确定网络，之后应用邻居二分图(NBG)和贡献者(Contributor)改进了相似性矩阵计算公式，从而提高了顶点相似性计算的精度，并应用概率母函数降低了求解矩阵内每个元素期望的复杂度。实验验证了PB

6、NA能够得到现有的确定生物网络比对算法得不到的比对结果，并以我们所知的现存唯一的不确定比对算法Prob为参考标准，验证了PBNA可以在更短的时间内得到更具生物意义的比对结果。2、现有的Prob算法和PBNA算法仅能够利用到一个生物网络中的不确定信息，即只允许参与比对的两个网络其中一个是不确定网络。因此，本文进一步提出了“完全的不确定网络比对(CompleteProbabilisticAlignment)”概念，并将现有的Prob算法与PBNA算法分别改进为完全不确定比对算法ProbCP与PBNACP。两种改进的算法分别在原算法的基础之上，将之前被忽略掉的一个网络中的不确定信息纳入到顶点相

7、似性矩阵构建过程中，并利用离散随机变量相关理论求其期望值，参与之后的运算。实验结果验证了两种扩展算法的有效性，并比较了二者的生物意义和时间效率，再次验证了加入Contributor等概念的PBNACP算法能够得到更具生物意义的比对结果，以及有着更高的时间效率。关键字：不确定生物网络；网络比对；蛋白质相互作用网络：离散随机变量万方数据AbstractThedevelopmentofbiologicalexperimenttechnol