硕硕士士学学位位论论文文一种基于生物数据的多层关联规则一种基于生物数据的多层关联规则挖掘算法挖掘算法A Thesis Submitted in fulfillment of the Requirements for the Degree of Master of EngineeringAn Algorithm for Mining Biological Data Multilevel Association RulesCandidate: Zhang PingMajor: Computer Software and TheorySupervisor : Prof. Lu YanshengHuazhong University of Science but existing algorithms still have some shortcomings. The proposed algorithms for mining multilevel association rules, such as Cumulate algorithm and ML_T2L1 algorithm, are based on Apriori algorithm. These algorithms still adopt “candidate generate and test“ method to get frequent patterns which cause large cost in computing and I/O; so they are inefficient.Improved from FP_Growth algorithm, MAGO-FP, an optimized data mining technique to discover the multilevel association rules from gene expression data and the concept hierarchy of Gene Ontology (GO) has been proposed. The following measures are applied to expand FP-Growth algorithm: (1) Expanding every transaction by adding all ancestors of each item during the process of scanning the database. This measure ensures that we can get multilevel association rules; (2) Deleting the ancestors that are not frequent items in time to compress search space and enhance the efficiency of mining; (3) Avoiding generating redundant frequent patterns. The multilevel association rules mining algorithm can figure out the relations between GO terms by summarizing the genes with the hierarchy of GO. An experiment showed that MAGO-FP algorithm got the same result as Cumulate algorithm did and inherited the strongpoint of high efficiency of FP_Growth algorithm.A data set of 300 expression profiles for yeast has been analyzed; using the algorithm, we found numerous rules in the data. A cursory analysis of some of these rules reveals numerous associations between certain genes, many of which made sense biologically, others suggesting new hypotheses that may worth of being further investigated. The algorithm could be used to analyze gene expression profiles and uncover gene networks.Key words: Data Mining, Multilevel Association Rules, Gene Ontology, MAGO-FP Algorithm华 中 科 技 大 学 硕 士 学 位 论 文III目目 录录摘 要.IAbstract.II1 绪 论1.1 研究背景与意义.(1)1.2 关联规则挖掘研究进展.(2)1.3 生物数据关联规则挖掘的基本步骤.(11)1.4 论文组织结构.(14)2 关联规则挖掘算法2.1 关联规则的定义和相关概念.(15)2.2 两种经典的关联规则挖掘算法.(17)2.3 多层关联规则的定义和相关概念.(25)2.4 两种经典的多层关联规则挖掘算法.(28)2.5 小结.(31)3 GENE ONTOLOGY 结构下优化的多层关联规则挖掘算法3.1 基于 APRIORI 算法的多层关联规则挖掘算法的局限性.(32)3.2 基因本体论（GENE ONTOLOGY）及其概念分层结构 .(32)3.3 MAGO-FP 算法.(39)3.4 小结.(44)4 MAGO-FP 算法的实验分析4.1 实验平台与过程.(45)4.2 性能优势分析.(45)IV4.3 实验结果与分析.(46)4.4 小结.(48)5 结 论 .(50)致 谢 .(51)参考文献 .(52)附录 1（攻读学位期间发表论文目录） .(60)华 中 科 技 大 学 硕 士 学 位 论 文11 绪绪 论论1.1 研究背景与意义研究背景与意义生命科学近年来获得突破性进展1，随着生物学和医学的迅速发展，生物数据呈指数级增长，无论是在数量上还是在质量上都极大的丰富了生命科学的数据资源，提供了揭开生命奥秘的数据基础。然而生物数据种类丰富，高通量，维数高，本质上具有异质性与网络性，远远超出传统的分析方法的能力和速度，其处理、挖掘、分析和理解日益迫切。如何分析这些具有丰富内涵的数据并从中获得关生物结构和功能的信息，从中得到对人类有益的信息，是生物研究的瓶颈，是当前研究所面临的一个严峻挑战。生物信息学是在此背景下发展起来的综合运用生物学、数学、信息学以及计算机科学等诸多学科理论方法的崭新交叉学科，是在生命科学的研究中,以计算机科学知识为辅导工具对生物信息进行储存、检索和分析的科学，是当今生命科学和自然科学的重大前沿领域之一。它包含两方面的内容，一方面是对海量数据的搜索、管理、服务，即“管好数据” ；另一方面从中发现规律，即“读懂”数据。随着人类基因组计划的完成，生物信息学的研究重点已经从开始的序列分析、数据库查询逐渐向生物信息的挖掘、表达、数据多样性分析的方向发展，高通量实验数据分析成为目前生物信息学研究的热点和重点。这些数据是通过一些高通量实验测量技术得到的，往往包含着几千个基因或基因片断和几十个属性。高通量实验数据，无论是转录水平上还是蛋白质水平上，其中都蕴含着丰富的生物学知识，可以帮助我们理解基因、理解生物、理解细胞等等，例如某疾病是由什么基因引起的、细胞是处于正常还是恶化状态、药物对肿瘤细胞是否有效等。由于越来越多数据得以公开，人们迫切希望通过数据挖掘技