《基于索引结构的代谢网络比对算法研究》由会员分享，可在线阅读，更多相关《基于索引结构的代谢网络比对算法研究（60页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学 硕士学位论文 基于索引结构的代谢网络比对算法研究 姓名：张明 申请学位级别：硕士 专业：计算机应用技术 指导教师：高琳 20100101 摘 要 随着人类基因组计划的开展与现代生物技术的迅猛发展，生物信息数据的增 长呈现爆炸之势，这为揭开生命奥秘提供了数据基础；计算机运算能力的提高和 国际互联网络的发展使得对大规模数据的存储、处理、检索和解读提供了理论基 础。而如何运用信息科学和计算技术的手段，通过数据分析和处理，揭示海量数 据间的内在联系和生物学含义，解读他们所蕴涵的结构和功能信息，进而提炼有 用的生物学知识，是目前生物信息学研究的目的。在对生物网络数据的分析中， 一个很重
2、要的工作就是进行同源搜索。同源搜索是通过网络图的比对来实现的， 近年来随着网络比对技术在生物研究领域中所占的地位逐渐加重，比对算法也得 到了深入而广泛的研究，也因此出现了许多有效的生物网络比对算法。近年来， 随着生物研究方法的进步，海量高通量生物网络数据集的迅速增加，需要一种快 速高效的图查询方法。同时，由于高通量的数据集具有存在大量假阳性和噪声数 据的特点以及对拓扑结构的严格限制，精确的图比对算法的应用受到限制，同时 需要高效、近似的图比对算法。 在这种情形下，本文陈述一种基于索引结构的生物网络近似比对算法，这种 技术将索引结构引入图的比对，在计算图的相似性时构建一个具有弹性的模型， 这种模
3、型充分考虑到了生物网络的特性和图结构的差异。将生物网络抽象为无向 图，并以路径为单位建立比对模型，接着将目标图和查询图分解为小的查询片段， 用分级过滤方法进行筛选，最后将符合要求的片段进行组装，进而转化为查找极 大团问题，从而找出符合要求的结果。经过实验分析，该算法对图的拓扑结构没 有严格限制并且具有较高的运行效率，因此该算法具有更宽广的应用前景。 关键词：代谢网络 图比对 索引结构 同源 Abstract Along with the human genome projects beginning and the modern biological technologys rapid dev
4、elopment, the biology message datas growth presents potential of an explosion, which provided data foundation for opening the mysteries of life; The enhancement of computing capabilities and the development of the Internet provides large-scale datas storage, processing, retrieval and interpretation
5、with a theoretical basis. But the purpose of bioinformatics is how to use the information science and computation technologys method, through the data analysis and processing, to reveal the inner link during mass data and the biology meaning, explain the structure and the functional information they
6、 contain, then extract useful biology knowledge. An important tool for analyzing biological networks is the ability to perform homology searches, which is completed through the alignment of networks. In recent years, network comparison techniques promise to take an increasing role in the field of bi
7、ological research, this problem has been widely and deeply studied and many efficient algorithms are available. In recent years,with the rapid development of biological research methods, the high-throughout quantity of data increase rapidly, there is a growing need for effective and efficient graph
8、querying methods. Due to the noisy and incomplete characteristics of these high throughout biological data and the restricted topology structures, exact graph matching algorithm have limited use and approximate graph matching methods are required. In the context, this paper present a metabolic netwo
9、rk alignment algorithm based on index-structures, which introduce index structure into graph alignment. This paper employ a flexible model that allow for the difference of graph structure and characteristic of biological networks when we compute the similarity of query graph and database graphs. We
10、firstly abstract the biological networks as the undirected graph and we modeled the alignment based on pathways. Next, the target graphs and query graphs are broken down into smaller fragments and we employ hierarchical filtering methods to screen them. then, the suitable candidates were assembled i
11、nto bigger one and the problem is converted to find the maximal cliques. In the end, the proper result can be found. The related experiments demonstrate that our algorithm has a wider range of applicability than the previous restricted approach. So, our algorithm is effective and applicable. Key wor
12、ds : Metabolic network Graph alignment Index-structures Homology 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期 关于论文使用授权的说明关于论文使用授权的说明 本
13、人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 （保密的论文 在解密后遵守此规定） 本学位论文属于保密在 年解密后适用本授权书。 本人签名： 日期 导师签名： 日期 第一章 绪论 1 第一章 绪论 传统的生物学是一门实验科学，生物学研究依赖于对实验数据的处理和分析。 生物学同时也是一门发现科学，通过实验
14、发现新现象、新规律，经过分析、归纳 和总结，提炼出新的生物学知识。随着生物科学和技术的不断发展，生物数据积 累速度将不断加快。因此，也就对生物数据的科学分析方法和使用分析工具提出 了更新、更高的要求1。 生物信息学(Bioinformatics)是由生物科学， 计算机科学， 信息科学， 应用数学， 统计学等多门学科相互交叉而形成的一门新兴学科。它以计算机为主要工具，开 发各种软件，对日益增长的DNA和蛋白质的序列和结构等相关信息进行收集、储 存、发行、提取、加工、分析和研究，同时建立理论模型，指导实验研究，它由 数据库、计算机网络和应用软件三大部分构成2。它包含了两个方面：一是对海量 数据的收
15、集，整理与服务；另一方面是从中发现新的规律。生物信息学不只是一 门为了建立、更新生物数据库及获取生物数据而联合使用多项计算机科学技术的 应用性学科，也不仅仅是只限于生物信息学这一概念的理论性学科。事实上，它 是一门理论概念与实践应用并重的学科。它不仅具有重要的学术价值，还有很大 的商业价值，有着远大的发展前景。随着后基因组时代的到来，它将发挥着越来 越不可替代的作用。可以毫不夸张地说，生物信息学将是21世纪生物科学发展的 核心领域。 1.1 生物信息学背景 生物信息学这一词出现已经很久，早在1956年美国田纳西州盖特林堡召开的 首次“生物学中的信息理论研讨会”上便产生了生物信息学的概念。但是在
16、最近20 年左右，随着人类基因组计划(HGP)的迅猛发展，核酸序列的海量增加，才逐渐发 展成一门独立的学科。美国在人类基因组计划实施五年后的总结报告中，对生物 信息学做了以下的定义：生物信息学是一门交叉学科，它包含了生物信息的获取、 处理、存储、分发、分析和解释等在内的所有方面，它综合运用数学、计算机科 学和生物学的各种工具，来阐明和理解大量数据所包含的生物学意义。 生物信息学是伴随着人类基因组计划的实施逐渐发展壮大起来的，其发展历 程大致经历了三个阶段，前基因组时代：这一阶段生物信息学的主要工作包括生 物数据库的建立，检索工具的开发以及DNA和蛋白质序列分析。基因组时代：这 一阶段生物信息学的主要工作是大量核苷酸序列测定、分析、新基因寻找和识别， 以因特网为基础的网络数据库系统的建立和交互界面的开发以及基因组序列信息 的提取分析等。后基因组时代：这一阶段生物信息学的主要研究工作将包括蛋白 基于索引结构的代谢网络比对算法研究 2 质组学研究及人类基因组注
