（计算机应用技术专业论文）粗糙集理论在启动子识别中的应用研究.pdf

摘要 将粗糙集理论应用于生物信息学，是上个世纪末以来许多科研工 作者一直关注的研究热点，而且越来越多的被应用于生物信息学的各 个方面，目前已在人工智能、知识与数据发现、模式识别与分类、故 障检测等发面得到了广泛应用，它能有效地分析不精确、不一致、不 完整等各种不完备信息。而启动子识别又是生物信息学中重要的研究 课题。启动子是非常重要的控制和调控转录的d n a 区域，其结构的研 究对于基因表达模式、基因调控网络、细胞特异等方面是十分重要的。 因此，如何从基因组中准确、快速地识别出启动子、发现其中包含的 信息，将具有非常重要的意义。 针对粗糙集理论的相关基本概念和基于计算机的启动子识别技 术的现状进行分析与研究。指出如何将粗糙集理论运用于启动子识别 技术中，研究运用粗糙集理论对现有启动子识别技术进行改进的方 法，从知识依赖性的角度出发，利用知识依赖性计算转录因子结合位 点间的依赖关系，为今后的启动子识别技术奠定基础。 对转录因子结合位点序列进行分析研究，首先分析了粗糙集对于 不完备信息系统的处理方法，然后在此基础上运用属性重要性对序列 进行预处理，为今后运用粗糙集理论进行启动子识别研究提供了相应 的便利条件。 在对序列进行预处理和计算位点间依赖关系的基础上，提出一种 基于粗糙集理论的启动子识别方法，解决现有启动子技术单独考虑转 录因子结合位点的出现来进行启动子判断所存在的问题。通过启动子 序列相关数据的收集，对提出的方法进行实验分析和验证，用数据来 检验该方法的有效性。从实验结果可看出，该方法能较好地识别出启 动子序列。 关键词粗糙集，决策表，启动子识别，转录因子结合位点 a b s t r a ct t h ea p p l i c a t i o no fr o u g hs e tt h e o r yt ot h ef i e l do fb i o i n f o r m a t i c sh a s b e e nt h eh o ta r e af o rr e s e a r c h e r ss i n c et h ee n do fl a s tc e n t u r y t h er o u g h s e tt h e o r yi s j u s t p r o v i d e d w i t ht h e p r o b l e m ，a n di t i s a p p l i e di n t o b i o i n f o r m a t i c se x t e n s i v e l ym o r ea n dm o r e ，i ti sa p p l i e di n t om a n yf i e l d s e x t e n s i v e l y , s u c ha sa r t i f i c i a li n t e l l i g e n c e ，d i s c o v e r yo fk n o w l e d g ea n d d a t a ，i d e n t i f ya n dc l a s so fm o d e ，f a u l td e t e c t i n ga n ds oo n ，i tc a l la n a l y z e i m p r e c i s e ，i n c o n s i s t e n t ，i n c o m p l e t e a n d a n y o t h e rv a r i o u s i m p e r f e c t i n f o r m a t i o n s r e c o g n i t i o ni s a l li m p o r t a n tr e s e a r c hs u b je c ti nt h ef i e l do f b i o i n f o r m a t i c s p r o m o t e ri sad n aa r e aw h i c hi sv e r yi m p o r t a n tt o c o n t r o la n da d j u s tt r a n s c r i b i n g t h er e s e a r c ho fi t sc o n f i g u r a t i o nt ot h e g e n ee x p r e s s i o nm o d e l ，t h eg e n ea d j u s t a b l en e t w o r ka n d t h ec e l lv a r i a n c e i se x t r e m e l yv a l u a b l e s o ，h o wt oi d e n t i f yp r o m o t e ra n df i n di n f o r m a t i o n c o n t a i n e db yt h e s ep r o m o t e ra c c u r a t e l ya n dq u i c k l yf r o mg e n eg r o u pw i l l b e c o m e t r e m e n d o u s l ys i g n i f i c a t i v e t h et h e s i sa n a l y s i s e da n dr e s e a r c h e dt h eb a s i cc o n c e p tr e l a t e dt o r o u g hs e tt h e o r ya n dt h ec u r r r e n tr e s e a r c hs i t u a t i o no ft h ec o m p u t e r p r o m o t e rr e c o g n i t i o nt e c h n o l o g y t h e nt h et h e s i sw e n to nt of i g u t r eo u t t h em e t h o do fa p p l y i n gr o u g hs e t t h e o r y t o p r o m o t e rr e c o g n i t i o n t e c h n o l o g y , r e s e a r c h e dt h ei m p r o v e m e n to fc u r r e n tp r o m o t e rr e c o g n i t i o n t e c h n o l o g yu s i n gr o u g hs e tt h e o r y , f r o mt h ep e r s p e c t i v eo fk n o w l e d g e d e p e n d e n c e ，c a l c u l a t e dt h ed e p e n d e n c eo ft r a n s c r i p t i o nf a c t o rb i n d i n g s i t e su s i n gk o n w l e d g ed e p e n d e n c e ，l a i dt h ef o u n d a t i o nf o rp r o m o t e r r e c o g n i t i o nt e c h n o l o g yi nt h ef u t u r e t h e nt h et h e s i sa n a l y s i s e da n dr e s e a r c h e dt h et r a n s c r i p t i o nf a c t o r b i n d i n gs i t e ss e q u e n c e ，a n a l y s i s e dt h em e t h o d su s i n gr o u g hs e tt h e o r yo f t r e a t i n gi n c o m p l e t ei n f o r m a t i o ns y s t e mf i r s t l y , t h e np r e t r e a t e d t h e s e q u e n c e su s i n ga t t r i b u t ei m p o r t a n c e ，p r o v i d e df a c i l i t a t i o no fp r o m o t e r r e c o g n i t i o nu s i n gr o u g hs e tt h e o r yf o rt h ef u t u r e o nt h eb a s i so ft h es e q u e n c ep r e t r e a t i n ga n dt h ec a l c u l a t i n go fs i t e s d e p e n d e n c e ，p r o p o s e dap r o m o t e rr e c o g n i t i o nm e t h o db a s e d0 nr o u g hs e t t h e o r y , r e s o l v e dt h ep r o b l e mo fc u r r e n tp r o m o t e rr e c o g n i t i o nt e c h n o l o g y t h a tc o n s i d e r e dt h et r a n s c r i p t i o nf a c t o rb i n d i n gs i t e s i n d i v i d u a l l y b y c o l l e c t i n gt h ep r o m o t e rs e q u e n c e s ，t h e nt h i st h e s i sv e r i f i c a t e dt h em e t h o d u s i n ge x p e r i m e n t ，t e s t e dt h ee f f e c t i v e n e s so ft h em e t h o du s i n gr e l a t e d d a t a s t h er e s u l to ft h ee x p e r i m e n tp r o v e dt h a tt h em e t h o dt h i st h e s i s p r o p o s e dc a nr e c o g n i s e dp r o m o t e rw e l l k e yw o r d sr o u g hs e t ，d e c i s i o nt a b l e ，p r o m o t e rr e c o g n i t i o n ，t r a n s c r i p t i o n f a c t o rb i n d i n gs i t e i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 兰：l 茎日期：笪年曼月翌日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印，缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 硕士学位论文第一章绪论 第一章绪论 1 1 课题研究背景及意义 生物信息学是- f - 新兴的交叉学科，它是伴随基因组研究而产生的，所以其 研究内容紧随着基因组研究而发展。该学科主要从事对基因组研究相关生物信息 的获取、加工、储存、分配、分析和解释。这一定义包括了两层含义，一是对海 量数据的收集、整理与服务，即管理好这些数据；另一个是从中发现新的规律， 使这些数据得到充分利用。 根据中心法则可知，基因转录是遗传信息传递过程中第一个具有高度选择性 的环节，编码区和调控区是人类基因组d n a 序列当中两类重要的功能信息。启 动子就是最重要的调控区，它决定了基因表达的关键性的第一步：信使r n a 的 转录。启动子结构的研究对于基因表达模式、基因调控网络、细胞特异性等方面 是十分重要的。鉴于启动子具有如此重要的生物学作用，如何从基因组中快速地 识别出启动子、发现其中包含的信息，已经成为后基因组时代一个非常重要的课 题。 粗糙集理论是一种研究不完整、不确定知识处理的数学工具【i 2 1 ，它已经广 泛地在人工智能、知识与数据发现、模式识别与分类、不精确数据的分析推理以 及发现潜在知识、数据挖掘等方面得到了较为成功的应用。其主要思想是根据已 有属性对论域对象的划分，通过不可分辨关系确定给定问题的上、下近似域，在 保持信息系统分类能力不变的前提下，进行知识约筒，导出问题的决策规则。 因此，如何运用粗糙集理论从基因组中发现潜在知识进行启动子的识别可能 成为一个很有意义的研究课题。本文结合粗糙集理论方面的知识与方法，研究基 于粗糙集理论的启动子识别方法。 1 2 粗糙集理论的产生和发展 粗糙集理论的提出背景 数据是对客观事物的属性，数量，位置或它们之间的相互关系的形式表示， 是各种信息的载体。然而浩瀚自然界中的大部分事物却是表露不全，不精确或含 糊不清的。在经典逻辑中，只有真、假二值之分，因而它无法对此类问题进行 准确描述。如何表示和处理这些现象就成为一个人们期望解决的研究领域。长期 硕士学位论文 第一章绪论 以来，许多逻辑学家和哲学家致力于研究含糊概念。早在1 9 0 4 年谓词逻辑的创 始人g f r e g e 就提出了含糊( v a g u e ) - - 词，他把它归结到边界线上，也就是说在 全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分 类。 1 9 6 5 年，美国控制论专家z a d e h 提出了模糊集，不少理论计算机科学家和 逻辑学家试图通过这一理论解决g f r e g e 的含糊概念，但模糊集没有给出确定 的数学公式描述这一含糊概念，故无法计算出它的具体的含糊元素数目，如模糊 集中的隶属函数p 和模糊逻辑中的算子九都是如此。1 9 8 2 年波兰学者z p a w l a k 针对q f r e g e 的边界线区域思想提出了粗糙集，但当时并未引起国际计算机界 的足够重视。p a w l a k 把那些无法确认的个体都归属于边界线区域，而这种边界 线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，所 以含糊元素数目是可以计算的，即在真假二值之间的含糊度是可以计算的。粗糙 集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息，而模糊集 理论中则需要像隶属度或概率值这样的由主观确定的信息。 1 9 9 1 年，p a w l a k 出版了一部专著( r o u g hs e t s t h e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a ) ) ，它奠定了粗糙集理论的基础，并从此掀起了粗糙集理论 及应用的研究高潮。 1 2 2 粗糙集理论的研究对象 粗糙集理论的研究对象是由一个多值属性( 特征、症状、特性等) 集合描述 的一个对象( 观察、病例等) 集合，对于每个对象及其属性都有一个值作为其描 述符号，对象、属性和描述符号是表达决策问题的三个基本要素。这种表达形式 也可以看成一个二维表格，表格的行与对象相对应，列对应于对象的属性。各行 包含了表示相应对象信息的描述符号，还有关于各个对象的类别成员的信息。通 常，关于对象的可得到的信息不一定足以划分其成员类别。换句话说，这种不精 确性导致了对象的不可分辨性。给定对象间的一个等价关系，即导致由等价关系 构成的近似空间的不分明关系。粗糙集理论就用不分明对象类形成的上近似和下 近似来描述。这些近似分别对应了确定属于给定类的最大的对象集合和可能属于 给定类的最小的对象集合。下近似和上近似的差是一个边界集合，它包含了所有 不能确切判定是否属于给定类的对象。这种处理可以定义近似的精度和质量。粗 糙集方法可以解决重要的分类问题，所有冗余对象和属性的约简包含属性的最小 子集，能够很好的近似分类，得到可以接受质量的分类。而且，它还可以用决策 规则集合的形式表示最重要属性和特定分类之间的所有重要关系。 2 硕士学位论文第一章绪论 1 2 3 粗糙集理论的研究现状 1 9 9 1 年波兰p a w l a k 教授的第一本关于粗糙集的专著( ( r o u g hs e t s ：t h e o r e t i c a l a s p e c t so f r e a s o n i n ga b o u td a t a 和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用 及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的 深入研究。1 9 9 2 年在波兰k i e k r z 召开了第l 届国际粗糙集讨论会。从此每年召 开一次与粗糙集理论为主题的国际研讨会。 我国于2 0 世纪9 0 年代开始对粗糙集理论进行研究，并取得了一系列研究成 果，在国内外重要期刊与学术会议上发表了很多文章，产生了较大的影响。自 2 0 0 1 年起我国成功召开了5 届以粗糙集与软计算为主题的全国性学术会议。2 0 0 3 年1 0 月，我国在重庆成功举办了第9 届粗糙集、模糊集、数据挖掘和粒度一软 计算的国际会议。粗糙集理论作为人工智能理论及其应用领域中一个较新的学术 热点，已经引起了越来越来的科研人员重视。 目前，粗糙集理论研究主要分为理论部分和应用部分。理论方面主要研究粗 糙集理论的代数和逻辑性质。对粗糙集理论方面的研究还包括：粗糙集模型的推 广、问题不确定性的研究、与其他处理不确定、模糊性问题的数学理论问的关系 与互补、纯粹数学理论方面的研究、粗糙逻辑方面的研究和与人工智能其他方向 关系的研究等。应用方面有一般关系数据库中属性的依赖关系；从数据库中产生 一般规则；将关系数据库作为机器学习中例子学习的一个特例产生出特殊规则和 分类规则；利用信息熵来研究关系数据库的信息论性质：用粗糙集理论研究不协 调关系数据库中属性的依赖关系等。 1 粗糙集的理论研究 目前对粗糙集理论的研究主要集中在： ( 1 ) 粗糙集模型的推广 目前主要有两种方法：构造性方法，代数性( 公理化) 方法。构造性方法主 要思路是从给定的近似空间出发去研究粗糙集和近似算子。这种方法研究的问题 往往来源于实际，所建立的模型有很强的应用价值，其主要的缺点是不容易深刻 了解近似算子的代数结构。代数方法也称为算子方法，它的明显优点是能深刻地 了解近似算子的代数结构，其缺点是应用性不够强。 ( 2 ) 不确定性问题的理论研究 粗糙集理论中的不确定性主要由两个原因产生的，一是直接来自于论域上的 二元关系及其产生的知识模块，即近似空间本身。另一个原因是来自于给定论域 里粗糙近似的边界，当边界为空集时知识是完全确定的，边界越大，知识就越粗 糙或越模糊。 3 硕士学位论文 第一章绪论 ( 3 ) 与其他处理不确定性方法的理论的研究 知识库的知识的类型一般有两类：一类是库中所有对象的描述是完全已知 的；另一类是库中对象的描述只有部分是已知的，即知识库中的知识是不确定的。 模糊集和粗糙集理论在处理不确定性和不精确性问题方面都推广了经典集 合论，但模糊集是通过关于集合的隶属程度来近似描述，而粗糙集是通过一个关 于某个可利用的知识库的一对上下近似来描述。从集合对象间的关系来看，模糊 集强调的是集合边界的病态定义上的，而粗糙集则强调的是对象间的不可分辨 性；从研究对象来看，模糊集研究的是属于同一类的不同对象间的隶属关系，而 粗糙集研究的是不同类中的对象组成的集合关系，重在分类。模糊集的隶属函数 大多由专家根据经验给出的，因此有很强的主观意志，而粗糙集的粗糙隶属函数 的计算直接从被分析的数据直接获取的，非常客观。 ( 4 ) 算法研究 粗糙集理论中的有效算法主要集中在导出规则的增量式算法，约简的启发式 算法，粗糙集基本并行算法和与粗糙集有关的神经网络与遗传算法【3 】等。 ( 5 ) 与其他数学理论的联系 从算子的观点看，粗糙集与之相联系比较紧密的有拓扑空间、数理逻辑、模 态逻辑、格与布尔代数、算子代数等。从构造性和集合的观点来看，它与概率论、 模糊数学、证据理论、图论、信息论等比较密切。 。2 粗糙集的应用研究 随着粗糙集理论研究的日益深入，作为一种新兴的数据处理工具它在模式 识别、专家系统、股票数据分析、人工神经网络、医疗诊断、d n a 数据分析等 各个领域。 ( 1 ) 从数据库中知识发现。( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 【4 5 1 。k d d 又称数据挖掘( d a t am i n i n g ) ，是当前人工智能和数据库技术交叉学科的研究热点 之一。r s 方法现在已经成为k d d 的一种重要方法，其导出的知识精练且更便 于存储和使用。 ( 2 ) 模式识别。文【6 】应用r s 方法研究了手写字符识别问题，提取出了特征属 性。 ( 3 ) 股票数据分析。g o l a n 和z i a r k o 应用粗糙集理论分析了1 0 年间股票的历 史数据f 7 1 ，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了 华尔街证券交易专家的认可。 ( 4 ) 粗糙控制。p l o l l k a 【8 】等人应用粗糙控制研究了经典的“小车倒立摆系 统，取得了较好的结果。m r o z e k 9 应用粗糙集理论成功地提取了水泥窑炉的控 制规则，将最初的1 3 条规则缩减为5 条。z i z a r k o t l o 】用粗糙集方法实施城市通道控 4 硕士学位论文第一章绪论 制，将铁路沿线固定站点的交通控制看作一个决策属性表，通过粗糙集从现有数 据中抽简行驶方案的决策规则。p e t e 一1 1 】等人设计了逼近时间粗糙控制器，将粗 糙集方法与传统p i d 控制相结合，对卫星角度控制系统中的仰角进行控制。 ( 5 ) 人工神经网络。由于人工神经网络训练时间较长，是制约a n n 实用化的 因素之，所以应用粗糙集理论化简神经网络训练样本集，在保留重要信息前提 下，消除了多余的数据，j e l o n e k 等对此作了大量的研究【1 2 】，对脑肿瘤的显微图 进行分类，用粗糙集预处理数据，收敛速度提高了4 7 2 倍。文 1 3 ，1 4 将r s 与 a n n 结合起来，充分利用r s 处理不确定性的特长以增强a n n 的信息处理能力。 ( 6 ) 医疗诊断。在医疗诊断方面，用集方法根据以往病例归纳出诊断规则， 用来指导新的病例。人工预测早产准确率只有1 7 3 8 ，应用粗糙集理论可提 高到6 8 9 0 p s j 。 1 3 粗糙集理论的特点及其所能解决的问题 1 3 1 粗糙集理论的特点 粗糙集是一种软计算方法，软计算中的主要工具包括粗糙集，模糊逻辑，神 经网络，概率推理，信度网络，遗传算法与其它进化优化算法，混沌理论等。传 统的计算方法即硬计算，使用精确，固定和不变的算法来表达和解决问题。而软 计算的指导原则是利用所允许的不精确性，不确定性和部分真实性以得到易于处 理，鲁棒性强和成本较低的解决方案，以便更好地与现实系统相协调。 粗糙集方法的简单实用性使其能在创立后的不长时间内得到迅速应用，它具 有以下特点： ( 1 ) 它能处理各种数据，包括不完整的数据以及拥有众多变量的数据； ( 2 ) 它能处理数据的不精确性和模棱两可，包括确定性和非确定性的情况： ( 3 ) 它能求得知识的最小表达和知识的各种不同颗粒层次； ( 4 ) 它能从数据中揭示出概念简单，易于操作的模式； ( 5 ) 它能产生精确而又易于检查和证实的规则，特别适于智能控制中规则的 自动生成。 1 3 2 粗糙集理论所能解决的问题 粗糙集能有效地处理下列问题【1 6 】： ( 1 ) 不确定或不精确知识的表达； ( 2 ) 经验学习并从经验中获取知识； 硕士学位论文 第一章绪论 ( 3 ) 不一致信息的分析； ( 4 ) 根据不确定，不完整的知识进行推理； ( 5 ) 在保留信息的前提下进行数据化简； ( 6 ) 近似模式分类； ( 7 ) 识别并评估数据之间的依赖关系 1 4 生物信息学及启动子 1 4 1 生物信息学的主要研究方向 生物信息学和粗糙集理论都是新兴起的学科，为了使粗糙集理论能更好的为 生物信息学服务，首先要对生物信息学的主要研究方向【1 7 饽】进行深入的分析， 从而找出研究切入点，充分发挥粗糙集理论的作用，解决生物信息学中可以改进 的问题。下面将简单分析生物信息学中主要的研究方向，为粗糙集理论和生物信 息学的结合打下基础。 1 序列比对 序列比对的基本问题是比较两个或两个以上符号序列的相似性或不相似性。 这一问题包含了以下几个方面： ( 1 ) 从相互重叠的序列片断中重构d n a 的完整序列； ( 2 ) 在各种试验条件下从探测数据( p r o b ed a t a ) q a 决定物理和基因图； ( 3 ) 存贮、遍历和比较数据库中的d n a 序列； ( 4 ) 比较两个或多个序列的相似性； ( 5 ) 在数据库中搜索相关序列和子序列； ( 6 ) 寻找核苷酸的连续产生模式； ( 7 ) 找出蛋白质和d n a 序列中的信息成分。 2 蛋白质结构比对与预测 蛋白质结构比对与预测研究的基本问题是比较两个或两个以上蛋白质分子 空间结构的相似性或不相似性。具有相似功能的蛋白质，其结构一般也相似，这 是因为，蛋白质的结构与功能是密切相关的。蛋白质结构比对与预测有两个重要 的方法，同源建模和指认。 3 基因识别、非编码区分析研究 基因识别的基本问题是给定基因组序列后，正确识别基因的范围和在基因组 序列中的精确位置。 4 分子进化与比较基因组学 分子进化是根据不同物种中同一基因序列的异同来分析生物的进化。研究分 6 硕士学位论文 第一章绪论 子进化既可以用d n a 序列也可以用其编码的氨基酸序列来进行，或者可通过相 关蛋白质的结构比对来研究，这些方法的前提假定是一样的，即是假设相似种族 在基因上具有相似性。 5 序列重叠群装配 人类基因的测量采用了短枪方法，这就要求把大量的较短的序列全体构成重 叠群，然后逐步把它们拼接起来形成序列更长的重叠群，直至得到完整序列的过 程称为重叠群装配。 6 遗传密码的起源 对遗传密码的研究通常认为：密码子与氨基酸之间的关系是生物进化历史上 一次偶然的事件而造成的。不同于这种理论来解释遗传密码的有选择优化、化学 和历史等三种学说。随着各种生物基因组测序任务的完成，为研究遗传密码的起 源和检验上述理论的真伪提供了新的素材。 7 基于结构的药物设计及其他 要了解人体内蛋白质的结构、功能、相互作用以及与各种人类疾病之间的关 系，寻求各种治疗和预防方法是人类基因工程的目的之一。其他一些方向如基因 表达谱分析、代谢网络分析、基因芯片设计和蛋白质组学数据分析等，逐渐成为 生物信息学中新兴的重要研究领域。 1 4 2 粗糙集与生物信息学的结合 随着粗糙集理论的发展及各专家学者的研究深入，粗糙集理论越来越多的被 应用于生物信息学中，如在医疗诊断、基因序列研究、蛋白质结构预测研究等其 它方面都已经有了相关的研究与应用。 1 基因序列研究 依据基因序列分析的结果可以对许多疾病进行诊断，目前基因序列的分析与 研究已经成为人类疾病研究的热点。很多研究主要是基于一种理论假设：假设具 有相似表达序列的基因组具有相似的功能，或者假设具有相似功能的基因组具有 相似的表达序列。实际上，不同功能的基因可能具有相似的表达序列，而有相似 表达序列的基因可能有完全不同的功能。生物过程中，基因内部的相互作用通常 是非常复杂的，一个生物过程可能基于数百个基因的协同作用，同时一个基因也 可能同时参与几个生物过程。粗糙集理论属于有监督的一种机器学习方法，将粗 糙集理论应用于基因序列的研究将会是一种新颖的研究思路。 文 2 0 】利用粗糙集理论的近似质量概念，定义了属性相关度与属性相互作用 度两个量化公式，衡量基因之间、基因与癌症类型之间的关系。对基因表达数据 进行信息分析，提高了癌症分类诊断的准确性。该研究方法有较好的区分癌症类 7 硕士学位论文第一章绪论 型能力，与传统方法相比能尽早诊断出具体的癌症类型，并辅助疾病的早期治疗。 2 蛋白质结构预测研究 结构基因组学是后基因组时代国际研究热点之一其目标是确定所有生物蛋 白质组中的每个蛋白质的三维结构，从原子水平来研究蛋白质和生命现象。蛋白 质结构预测的方法可以分为两大类【2 1 2 3 1 ：一类是考虑蛋白质分子之间，蛋白质 分子与溶剂之间的相互作用，利用分子力学的能量极小化方法，计算出蛋白质分 子的天然空间结构；另一类方法是所谓的“基于知识的预测方法 ，即从数据库 中已有的蛋白质的空间结构与其一级序列之间的联系总结出一定的规律，逐级从 级序列预测二级结构，再建立可能的三维模型，根据总结出的空间结构与其一 级序列之间的规律，排除不合理的模型，再根据能量最低原理得到修正的结构。 文献 2 4 】应用粗糙集理论中基于规则的数据挖掘算法，预测了蛋白质结构类 别。其方法主要以氨基酸合成物和8 个物理化学参数数据作为条件属性构建决策 系统，经过对决策系统的约简后，获得可以应用于新对象分类的决策规则。该文 献还将此预测方法与其他关联成分分析、神经网络、s v m 等预测方法进行比较， 比较结果证实了粗糙集理论在生物信息学的蛋白质结构预测研究中具有较大的 优势。 3 医疗诊断 目前，越来越多的国内外学者和专家对粗糙集理论在医学数据分析中的应用 进行了研究，研究的方法主要分为“建立诊断模式并预测结果 和“特征提取 两种。 ( 1 ) 建立诊断模式并预测结果 研究人员根据医学案例中已获得的数据，应用粗糙集理论中的不可分辨关 系、约简和信息系统的构建等相关概念，将医学数据转换成信息系统中的对象、 属性和属性值等数值化表示形式，然后利用粗糙集理论的属性约简等算法，从转 换得到的信息系统中除去冗余属性及属性值，获取决策规则，最后应用于具体的 医疗案例分析中进行分析、诊断。实验表明，应用了粗糙集理论的医学诊断模式， 普遍比未使用的诊断效果要明显。文 2 5 3 0 分别应用粗糙集理论对医学数据进 行分析，建立了相应疾病的诊断模式，与以往未使用粗糙集理论的诊断方法相比 具有更准确的诊断结果。 ( 2 ) 特征提取 现阶段许多医疗数据的分析过程需要提取数据特征，然后提供给预先设计的 分类器进行分类能力训练，从而有助于疾病分类预测模式的建立。而粗糙集理论 恰恰具有这方面的能力，可以将粗糙集理论应用于此过程进行数据的预处理，提 取数据特征。文献【3 l 3 2 对疾病等相关医学数据构成的属性集合进行选择，构 8 硕士学位论文 第一章绪论 造最小分辨子集集合，减少了后继神经网络等分类器的输入维度。 4 其他 粗糙集理论除了应用于上述领域之外，在诸如基于结构的药物设计方面也有 所应用。文献 3 3 3 4 基于粗糙集理论的化学计量法对药物设计中的受体和配基 识别进行了研究。在化学计量方法中，受体和配基的参数被用来联合建模以预测 绑定耦合度，构建的模型提供了由粗糙集知识体系得出的最小决策规则知识库。 根据这些知识，可以建立一个机制阐明存在于数据集中的受体和配基之间是相互 作用的机理，更深层次地理解受体配基相互作用的生物学本质。 1 4 3 基于计算机的启动子识别研究现状 目前，基于计算机的启动子识别技术【3 5 确1 被越来越多的学者所研究，而且 在各种启动子识别软件中很多软件利用寻找转录因子结合位点来对启动子进行 识别【3 7 枷】。如何识别出这些特异性转录因子结合位点就成为了识别启动子序列 的关键。本文在这里简单介绍几种转录因子结合位点的识别方法： 1 保守序列法 保守序列法是指将一组给定的转录因子结合位点样本对齐，得到一个可以近 似匹配所有位点样本的共有序列，但并不要求各个位置完全匹配。共有序列中允 许的不匹配的数目、模糊性与共有序列用于搜寻时所具有的精确性、敏感性息息 相关。该方法是最早的用于搜寻转录因子结合位点的方法。 2 权重矩阵法 位置加权矩阵法是一组已知位点样本用位置加权矩阵来表示，然后用该矩阵 搜寻未知的位点。利用该矩阵，分配给转录因子结合位点的各位置上每种可能出 现的核苷酸一个权值，对一个给定的序列，将各位置的相应分数相加后给出该序 列作为潜在位点的得分，然后与一个事先给定好的阈值进行比较，再来判断该给 定序列是否为位点。 3 模体法 对于一组功能相近的已知的转录因子结合位点序列，如果无法进行对齐的 话，一般采用模体法。目前对于模体的识别都是基于k 元组思想，k 元组是指在 序列中相匹配的很短的序列片段。k 元组的基本思想就是在集合中自动搜寻过表 达的k 元组。根据模体特点的不同，可以采用不同的模体搜寻方法。 1 5 论文研究的内容和意义 粗糙集理论在生物信息学研究过程中的应用，是数据挖掘技术与生物信息学 9 硕士学位论文第一章绪论 之间很好的结合点。生物信息学是一门新兴的交叉学科，随着人类基因组计划的 启动和实旌，生物数据迅速增长，面对日益增长的海量数据，如何从其获取有效 信息成为生物信息学迫切要解决的问题，这也正是将粗糙集理论与生物信息学结 合的意义所在。 考察粗糙集理论的研究内容及其处理问题的能力，结合粗糙集理论与数据挖 掘的相关知识，将粗糙集方法运用于启动子的识别具有极大的现实意义。 本论文围绕着粗糙集理论的主要研究内容以及启动子识别技术的现状展开， 对其中的关键问题进行研究和探索，深入分析启动子识别假阳性过高的影响因 素，使用粗糙集方法对其进行改进。 1 6 论文的组织结构 第一章绪论。 本章首先分析了粗糙集理论产生的背景、特点、所能处理的问题及国内外研 究现状，接着描述了生物信息学的主要研究方向、启动子识别研究的现状，最后 介绍了本论文研究的内容、意义及组织结构。 第二章粗糙集理论的基本概念。 本章首先描述了粗糙集理论的主要思想，接着以知识与知识库的概念引出粗 糙集理论的基本概念和定义，然后介绍了信息系统中数据预处理的方法，以及决 策表知识越简的方法，最后介绍了粗糙集知识依赖性的概念。 第三章转录因子结合位点问的依赖关系 本章利用粗糙集理论知识的依赖性，计算转录因子结合位点问依赖关系在此 基础上分析启动子中转录因子结合位点间的相互作用关系，为将来利用结合位点 来识别启动子打下了理论基础。 第四章粗糙集理论在序列预处理中的应用 本章在已有知识的基础上，利用粗糙集属性重要度分析转录因子结合位点序 列的预处理方法，这为以后将粗糙集理论更好的应用于启动子识别技术中提供了 便利的条件。 第五章基于粗糙集理论的启动子识别研究。 本章提出了基于粗糙集理论的启动子识别方法，首先利用粗糙集理论数据预 处理的方法，对启动子序列集的数据进行预处理，然后建立决策表进行分析，利 1 0 硕士学位论文 第一章绪论 用属性依赖度概念，对启动子序列中的转录因子结合位点序列进行分析研究，导 出决策规则，最后收集数据集，用实验验证了该方法的有效性。 第六章总结与展望。 对本论文的研究工作进行总结，指出进一步研究工作的重点和方向。 硕士学位论文 第二章粗糙集理论基本概念 第二章粗糙集理论基本概念 粗糙集理论是一种新型的软计算方法，由于它能有效的分析不完整、不一致、 不精确等各种不完备的信息，对数据进行分析和推理，并从中发现隐含的知识， 揭示潜在的规律，近年来在人工智能、知识与数据发现、模式识别与分类、不精 确数据的分析推理以及发现潜在知识、数据挖掘等方面得到了较为广泛和成功的 应用。本章介绍了粗糙集理论的基本概念，作为后续章节的理论基础。 2 1知识与知识库 设u = 瓴，x z ，) 是我们感兴趣的对象组成的一非空有限集合，称为论域。 任何子集x u ，称为u 中的一个概念范畴，可以认为空集也是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。f 可定义为一个划分，其 中：f = 五，x 2 ，e ) ，置互u ，五a 。对于i j ，i , j = 1 ，2 ，3 ，以来说 置n x ，= f 2 j 。u 上的一族划分称为关于u 的一个知识库。 粗糙集理论认为知识与分类密不可分，知识就是人类和其他物种所固有的分 类能力，分类是推理、学习与决策中的关键问题，所以也可以从分类的角度去描 述知识库。设r 是u 上一族等价关系，u r 为r 的所有等价类族，r 工1 。表示包 含元素x u 的尺的等价类。一个知识库也就是一个关系系统k = 缈，r ) ，其中【， 为非空有限集，称为论域，尺是【厂上的一族等价关系1 4 。 若p c _ r ，且p a ，则p 中全部等价关系的交集也是一种等价关系，称为 p 上的不可分辨关系，记为伽d ( 一，且有【x k ( p ) 2 【l 【z 】p 。非空子集p 尺所产 生的等价关系i n d ( p ) 的所有等价类关系的集合即u i n d ( p ) ，称为基本知识，相 应的等价类称为基本概念；特别地，若关系q r ，则关系q 称为初等知识，相 应的等价类就称为初等概念。 2 2 上下近似与粗糙集 令x u ，r 为u 上的一个等价关系。当x 能表达成某些尺基本范畴的并 集时，称彳是尺可定义的，否则称x 为r 不可定义的。 尺可定义集是论域的子集，它可以在知识库k 中精确定义，而尺不可定义集 不能在这个知识库中被定义。可定义集称为尺精确集，而r 不可定义集称为r 非 精确集或尺粗糙集。当存在等价关系r i n d ( k ) 且x 为r 精确集时，集合x u 1 2 硕士学位论文第二章粗糙集理论基本概念 称为k 中的精确集；当对于任何r f n d ( g ) ，x 都为r 粗糙集，则称x 为k 中 的粗糙集。 给定知识库k ；( u ，r ) ，对于任意一个对象集合x 【厂和一个等价关系 r i n d ( k ) ，定义两个子集： r x = o y u r i 】，n y 囝 ，( 2 - 1 ) 丛= u r u r i r s x ) 。 ( 2 - 2 ) 分别称为x 的尺上近似集和r 下近似集。若麒；砑，说明z 可以用属性r 精确描述，j 为可定义集或精确集，否则，则说明x 不能用属性r 精确描述， 是不可定义的，即为粗糙集，用上下近似集合来描述【纠3 1 。 b n r ( x ) = 肘一丛称为x 关于边界r 的边界域，p o s r ( x ) = 丛称为x 关 于r 的j 下域，n e g 矗( x ) = u 一肘称为z 关于尺的负域。图2 1 为粗糙集概念示意 图。 |厂。 ， 1 ， l 汲 _ l 、 l h ) 1 l 、 弋n ( 1 v 、 r - 。 l i 图2 - 1 粗糙集概念示意图 图2 1 中，每个小方格表示由知识r 所产生的等价类；曲线围起来的区域表 示某个要表达的概念x ：里层折线包围的区域是概念彳的下近似，而外层折线 包围的区域就是概念x 的上近似，位于里外两层折线问的区域就是概念x 的边 界区域。图中概念x 无法用小方格准确表达( 即粗糙集) ，却可用图中的上、下 1 3 硕士学位论文第二章粗糙集理论基本概念 近似两个集合( 精确集) 来粗略的表示。由图可看出，粗糙集的不精确性是由于 边界域的存在引起的，边界区域越大，其精确性越低；若边界区域为空集，则租 糙集便成为精确集。 2 3 决策表 2 3 1 决策表定义 决策表是一类特殊而重要的知识表达系统m 】，它在决策应用中起着重要的 作用，多数决策问题都可以用决策表形式来表达。 决策表可以根据知识表达系统定义如下： 设s = ( u ，a ，v ，厂) 为一知识表达系统，其中u ：对象的非空有限集合，称为 论域；a ：属性的非空有限集合；v - - i j 圪，圪是属性口的值域；是一个信息函 数，既为 c a 么，工u ，f ( x ，口) 圪。( 6 j c u d ，c o l d = o ，c 称为条件属性集， d 称为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。下面 通过一个例子来具体说明决策表中的条件属性及决策属性，如表2 1 所示，其中， 身高、性别、视力为条件属性，录取为决策属性。 表2 - 1 决策表示意 在决策表中，不同属性可能具有不同的重要性。为了找出某些属性( 或属性 集) 的重要性，常用的方法是从表中去掉一些属性，再来考虑去掉该属性后分类 会怎样变化。若去掉该属性后相应的分类变化较大，则说明该属性的强度大，即 重要性高；反之，说明该属性的强度小，即重要性低。 2 3 2 决策规则 在决策表中，最重要的是决策规则的产生1 4 引，决策表中的每一行对应诸 1 4 硕士学位论文 第二章粗糙集理论基本概念 如u 寸y 形式的决策规则，u 和矿分别称为决策规则的前驱和后继当决策 表s 中决策规则u y 为真时，我们说该决策规则是s