（计算机应用技术专业论文）基于粗糙集理论的基因序列研究.pdf

摘要 粗糙集理论是一种处理不确定、不完备和不精确数据的数学理论 工具，在数据分析与处理领域有着广泛而重要的应用。生物信息学是 一门结合了数学理论、计算机科学与生物学知识的新兴交叉学科，其 目的是致力于对生物信息的获取手段、处理方法、存储方式进行研究， 分析和解释大量生物学数据背后所包含的生物学意义以及应用，生物 信息学目前己成为世界交叉学科研究领域的一个新热点。本文基于粗 糙集理论，主要对生物信息学中涉及d n a 序列的启动子与基因表达 序列数据进行研究。 粗糙集理论在启动子序列研究中具有独特的优势。启动子识别研 究从生物学实验手段随着高效计算能力的计算机出现而转到了计算 机模拟识别。启动子是指导基因转录起始重要作用的序列段，在d n a 序列中可能处于多个位置。在d n a 序列中寻找确切的启动子位置具 有一定的困难，应用统计学知识、粗糙集理论中信息系统的约简与规 则获取方法，可以对不确定启动子位置进行分析、识别并预测一段 d n a 序列中存在启动子的可能性。 在基因表达序列的数据分析与规则获取研究中，粗糙集也具有较 优表现。本文将粗糙集理论应用于基因表达谱数据分析，给出一种基 于粗糙集理论与信息论的基因分析与选择启发式算法，处理大基因数 据集中存在冗余信息的问题，从海量基因数据集中选取了与疾病最关 联的基因集合。该方法能够有效处理以基因数据信息构成的信息系统 中的大量属性情况，降低去除无关联属性的成本，高效获取目的基因 集合。基于该启发式算法的理论研究，在基因数据库中保留了关联基 因，辅助获取基因决策表的最简规则，并向专家提供决策支持，构建 辅助决策的规则知识库。 本文最后在基因表达序列研究领域广泛应用的实际医疗数据集 l e u k e m i a 数据集上进行了算法理论实验仿真，仿真结果进一步阐明 了理论研究成果。 关键词粗糙集，生物信息学，启动子，粗糙熵 a bs t r a c t r o u g hs e tt h e o r y ( r s t ) i sa m a t h e m a t i c sm e t h o df o rd e a l i n gw i t h u n c e r t a i n ，i m p e r f e c t i o na n di m p r e c i s ed a t a i ti sw i d e l ya p p l i e di nd a t a a n a l y s i s a n dp r o c e s s i n ga r e a b i o i n f o r m a t i c si s a l l i n t e r d i s c i p l i n e c o m b i n e dw i t hm a t h e m a t i c s ，c o m p u t e rs c i e n c ea n db i o l o g y i ti ss t u d y i n g t h eb i o l o g yi n f o r m a t i o nb yd if f e r e n tm e t h o d s ，a n a l y z i n gt h em e a n i n go f b i o l o g yd a t aa n da p p l y i n gr e s e a r c hr e s u l t si n t op r a c t i c e b i o i n t o n n a n c sl s 一 o n eo ft h eh o ts p o ti nt h ec r o s s d i s c i p l i n e sa l lo v e rt h ew o r l d b a s e do n r s t , t h ep r o m o t e ra n dg e n ee x p r e s s i o ns e q u e n c ed a t ai nb i o i n f o r m a t i c s a r em a i n l ys t u d i e di nt h i st h e s i s i t i sa na d v a n c e dm e t h o df o rr s tb e i n ga p p l i e di np r o m o t e r s e q u e n c er e s e a r c h p r o m o t e ri d e n t i f y i n g r e s e a r c hi sm o v e df r o mt h e b i o l o g ye x p e r i m e n tm e t h o d st oc o m p u t e rs i m u l a t i n gi d e n t i f i c a t i o n i t i s a ni m p o r t a n ts e q u e n c es e g m e n tf o rp r o m o t e rt oi n s t r u c tt h et r a n s f e ro f g e n e p r o m o t e r sc a nb eo ns e v e r a l l o c a t i o n si nd n as e q u e n c e t h e r e f o r e ， i t i s d i f f i c u l t yt o l o c a t et h ee x a c tp o s i t i o n sf o rp r o m o t e r si nd n a s e q u e n c e a p p l y i n gt h es t a t i s t i c sa n dr s t i n t ot h ep r o m o t e rr e s e a r c hi s g o o df o rl o c a t i n gt h eu n c e r t a i np o s i t i o n ，i d e n t i f y i n ga n dp r e d i c t i n gt h e p r o m o t e r si nd n as e q u e n c e s r s ti sa l s oe x c e l l e n ti nt h es t u d yo fg e n ee x p r e s s i o ns e q u e n c ea n d g e n e r a t i o no fd e c i s i o nr u l e s b a s e do nr s ta n di n f o r m a t i o nt h e o r y , a h e u r i s t i ca l g o r i t h mf o rg e n ea n a l y s i sa n ds e l e c t i o ni sp r o p o s e di nt h i s t h e s i s b a s e do nt h i sa l g o r i t h m ，g e n e sr e l a t e dt ot h ed i s e a s ec a nb e s e l e c t e df r o mm a s sg e n es e t sa n dr e d u n d a n ti n f o r m a t i o nc a l lb er e d u c e d i nt h er e s e a r c ho ft h e o r yw i t ht h i sh e u r i s t i ca l g o r i t h m ，r e l a t e dg e n e sc a n b er e s e r v e df r o mt h eg e n ed a t a b a s ea n dm i n i m a ld e c i s i o nr u l es e t sc a nb e g e n e r a t e d r u l e sc o u l db ep r o v i d e dt ot h ee x p e r t sf o rb u i l d i n gd e c i s i o n r u l es e t s t h e r ei sa ns i m u l a t i o no nt h em e d i c a ld a t a s e t s ，l e u k e m i ad a t a s e t s ， w h i c hi sw i d e l yu s e dt os t u d yg e n es e q u e n c e s t h es t u d i e si nt h i st h e s i s a r ef u r t h e ri l l u s t r a t e db yt h es i m u l a t i o nr e s u l t s k e yw o r d s r o u g hs e t ，b i o i n f o r m a t i c s ，p r o m o t e r , r o u g he n t r o p i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：垫塑艺劁日期：盥年月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：秀砾师签名：垂垒女姐日期：堂2 l 年月旦日 硕士学位论文第一章绪论 1 1 课题研究背景与意义 第一章绪论 随着全世界范围内互联网的广泛应用以及各国研究机构在计算机计算能力 上不断投入更多的研究，不断深入研发高性能计算机，此时的计算机信息处理能 力已经远远超过了最初设计的信息处理能力。二十一世纪是一个数据信息剧增的 时代，在各个研究领域、各个研究机构和各个行业部门中都有无数日益庞大的数 据信息，计算机的引入对如何能以更高效、更准确、更大容量地方式处理这些数 据信息提供了一个切实可行的办法。在这样一个科学技术迅猛发展的时代，生物 学科在研究方法、研究手段和实验条件不断提高的过程中，学科研究所获得的各 种数据不断增长，相应的生物学数据库容量也越来越大。 生物分子学包含了具有丰富内涵的数据，数据中隐藏着人类目前尚不知道的 生物学知识。为了分析，理解，提取和应用这些海量的与复杂的生物学数据中所 隐含的知识，需要综合运用分子生物学、数学、物理学、计算机科学、电子学、 自动化等领域的知识、理论、方法与技术。因此推动了多学科之间的交叉研究与 应用，在多学科理论的研究的大背景之下，便出现了生物信息学这一门前沿而新 颖的交叉学科。 随着数学与计算机科学的知识逐步应用到生物学研究中，不断有许多科研人 员拓展思路，结合数学理论与计算机科学理论，分析生物信息学中亟待解决的问 题，并取得了一定的研究结果。 波兰数学家z p a w l a k 于1 9 8 2 年提出的粗糙集理论【1 】【2 】【3 】【4 】【5 1 ，是一种应用于 数据分析，处理不精确、不一致和不完备信息的软计算理论，它可以通过数学计 算的方式去定量分析数据集。二十世纪八十年代末得到了各国研究人员的关注， 九十年代至今的一系列以粗糙集理论为主题的国际学术会议广泛讨论粗糙集理 论并发表了许多论文，同时也有许多基于该理论的应用系统被成功开发，成功应 用于知识发现、数据挖掘、人工智能和决策支持等领域6 】【7 1 【8 】【9 】【10 1 。 粗糙集理论通过可以量化的方式，对一定范围内的数据进行分类，利用集合 的概念去分析数据的归属性。基于上下近似集合、边界域和正负域等概念去划分 数据，该理论更加适合处理从现实中抽取而得的数据，特别适合处理新兴学科生 物信息学相关的数据。目前生物信息学研究积累的数据是一个无穷的集合，而且 依靠目前的科技手段研究获得的数据仍然是一种高噪声、高维度、不完备和不一 致的信息。粗糙集理论在生物信息学研究中的应用是计算机学科机器学习技术在 硕士学位论文第一章绪论 交叉学科领域中的新研究思路。针对生物信息学中高维度、高通量的数据结构与 数据内容，将粗糙集等数学原理应用于智能数据挖掘和处理，并寻找数据库之间 新的联系，探讨其生物学意义是粗糙集理论结合生物信息学研究的意义所在。 将计算机学科知识与技术，生物学相关知识结合起来，特别是对目前已经存 在的海量数据库，利用较早前从对已分类对象和已存储的事例分析得来的知识去 分类新的对象是机器学习要完成的典型任务之一i l 。基于用集合形式表现的决 策规则的知识运用，是新兴交叉学科生物信息学领域对数据检索、分析处理和新 知识提取较为新颖的一种研究思想。 对生物信息学中的基因序列与启动子预测的研究内容，引入粗糙集理论是计 算机学科对生物学科的有益补充。在基因序列的研究方面能依靠计算机技术加快 研究的速度，解决生物信息学中日益增加的生物学数据处理问题：在启动子预测 的研究方面能通过粗糙集提取规则，以基于知识的推理方式去预测实验室手段难 以完成的启动子预测分析问题。 目前生物信息学结合粗糙集理论的研究主要目的是把生物学问题转化为对 数字符号处理的计算机问题，将复杂的生物学问题抽象成计算机学科可以解决的 数学问题，把以往依靠实验室手段去分析和验证课题的现状改进成通过计算机就 可以完成的方式。 粗糙集理论结合生物信息学的研究过程是从粗糙集理论出发，根据相关数据 挖掘算法与机器学习技术，提高工作效率、增加专家知识、扩展研究领域并最终 将研究成果应用到实践中去。基于粗糙集理论的生物信息学分析与应用研究已成 为智能信息处理领域一个十分具有前沿性与拓展性的研究课题。 1 2 国内外研究现状与水平 1 2 1 粗糙集理论研究现状 二十世纪六十年代初，l a z a d e h 提出模糊集理论( f u z z ys e t s ) 1 2 】。此理论被 许多计算机科学家和逻辑学家认为是对1 9 0 4 年谓词逻辑的创始人g f r e g e 提出 的含糊概念的最终定义与基础理论解释。但由于模糊集不具有可计算的数学公 式，即不能通过定量的方式进行含糊度的分析与研究，例如模糊集中的隶属函数 与模糊逻辑中的算子五都是这种情况。 粗糙集理论( r o u g hs e t s ) 1 3 j 是通过等价关系描述上近似集和下近似集的数学 理论，它将具有无法明确归属去向的元素个体都归于上近似集和下近似集之差 集，即边界区域。因为上下近似集均可以通过数学公式明确计算出来，那么其中 具有含糊性的元素数目也可以被计算出来，即真假二值之间的含糊程度也可以被 2 硕士学位论文第一章绪论 计算出来。粗糙集理论为数据分析与处理提供了一种新的数学方法。该理论主要 贡献在于它反映了人们处理不模糊问题的常规性，即以依靠不完备和不精确信息 处理模糊现象的能力，或依据观察度量所得的不精确结果而对数据集进行分类的 能力。但是当时该理论研究并未引起国际计算机学术界的重视，研究的范围仅限 于东欧国家。 以数学符号体系完整地描述了粗糙集理论，奠定了粗糙集理论研究的数学基 础的粗糙集理论专著，是z p a w l a k 在1 9 9 1 年出版的“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 fr e a s o n i n ga b o u td a t a 。它与r s l o w i n s k i 主编的粗糙集理论及应用专 著“i n t e l l i g e n td e c i s i o ns u p p o r t ：h a n d b o o ko fa p p l i c a t i o n sa n da d v a n c e so ft h e r o u g h s e t st h e o r y 1 4 j 总结了这一时期粗糙集理论的研究成果，进一步促进了粗 糙集理论的发展，极大推动了国际上对粗糙集理论应用的研究兴趣。 第一届国际粗糙集理论研讨会于1 9 9 2 年在波兰的k i e k r z 召开后，波兰、加 拿大、美国、日本等地分别举行了以粗糙集为主题的国际会议。随着世界范围内 对粗糙集理论的研究不断扩充，于1 9 9 4 年成立了一个为推进粗糙集理论在各个 领域研究的国际性学会“国际粗糙集学会( i n t e r n a t i o n a lr o u g hs e ts o c i e t y ) 。a c m c o m m u n i c a t i o n 在1 9 9 5 年将粗糙集列为新出现的计算机科学的研究课题。国际 信息科学杂志( i m e m a t i o n a lj o u r n a lo fi n f o r m a t i o ns c i e n c e s ) 为粗糙集理论的研究 在1 9 9 8 年出了一期专辑。国际粗糙集协会主办的第一本粗糙集国际期 刊”a d v a n c e si nr o u g hs e t s ”在2 0 0 4 年出版发行。 在国内，第一届粗糙集与软计算学术研讨会于2 0 0 1 年5 月在重庆举行，之 后每一年都分别举行了粗糙集与计算趋势国际会议。中国人工智能学会粗糙集与 软计算专业委员会与中国计算机学会人工智能与模式识别专业委员在浙江金华 主办2 0 0 6 年第六届中国r o u g h 集与软计算学术研讨会，在山西太原主办2 0 0 7 年粗糙集与软计算、w e b 智能、粒计算联合学术会议。在这些会议上，大量具有 较高学术价值和应用价值的论文不断被发表，极大地推动了国内外粗糙集理论基 础研究和实践应用步伐。 自粗糙集理论问世以来，它在各个研究领域迅速发展起来并取得了一定的应 用结果【1 5 】： 模式识别领域，在手写字符识别问题研究中，文献【1 6 】应用粗糙集方法提取 出了表征字符间区别的特征属性： 知识发现领域，即在目前人工智能和数据库技术交叉学科的研究热点领域 中，粗糙集方法可以导出更加精练、更加便于存储和使用的知识【l 7 j ； 专家系统领域，依据粗糙集理论获取规则，为构造专家系统知识库提供了一 条新的研究思路【1 8 】； 硕士学位论文 第一章绪论 人工神经元网络领域，由于人工神经网络训练存在训练时间太长的缺点，人 工神经网络实际应用受到了制约。应用粗糙集理论可以简化神经网络训练样本数 据集，消除冗余的数据，保留核心的数据信息，训练速度得以提高，增强了人工 神经网络的信息处理能力，促进了人工神经网络的实际应用【1 9 l 【2 0 1 1 2 1 】； 医疗诊断领域，粗糙集方法根据以往的病例归纳出诊断规则，用来指导新的 病例。例如，现有的孕妇早产人工预测只有1 7 至3 8 的准确率，应用粗糙集 理论则可提高到6 8 至9 0 的准确率。 1 2 2 生物信息学研究现状 在当今科学技术迅猛发展的时代，生物学科在研究方法、研究手段和实验条 件不断提高的过程中，学科研究所获得的各种数据不断增长，相应的生物学数据 库的容量也越来越大，并以一个惊人的速度爆炸式地存储海量的生物学数据。同 时，伴随全球范围内互联网的普及以及国际上计算机计算能力研究的不断深入， 此时的计算机信息处理能力与其刚面世的能力有着天壤之别。计算机能更高效、 更准确、更大容量地处理世界上各个领域、各个学科研究不断积累的数据信息。 将计算机学知识与技术，生物学相关知识结合起来，特别是对目前已经存在 的大容量数据库的数据检索、分析处理操作，是新兴交叉学科生物信息学产 生的背景。生物信息学是- i - j 结合了计算机信息处理技术与生命学的综合研究新 领域。 第一届“生物学中的信息理论讨论会在美国田纳西州的g a t l i n b u r g 召开， 这次会议举行于1 9 5 6 年，这也是生物信息学研究开始的里程碑会议。随着二十 世纪八九十年代计算机技术与生命科学的迅猛发展，计算机科学和网络技术被广 泛应用到生物学问题的解决过程中，其典型代表是美国启动的人类基因组计划。 二十世纪末，1 9 9 0 年，美国国会通过了3 0 亿美元的研究经费正式启动了人 类基因组计划，预计用1 5 年的时间，在2 0 0 5 年绘出人类基因图谱。继美国之后， 英国、日本、法国、德国、中国等1 8 个国家相继参与这个计划，成为重大国际 合作计划。这是迄今为止在生命科学领域最宏大的研究计划，与二十世纪的“阿 波罗计划一和“曼哈顿工程 并列，也被称为生命“阿波罗计划。 2 0 0 0 年6 月经过全球科学家近1 0 年的共同努力，美、英、法、德、日和中 国的工作都取得了阶段性胜利，2 0 0 0 年6 月2 6 日，美国总统克林顿在白宫向世 人庄严宣布：人类基因组草图的绘制工作已经完成。这是人类科学史上的又一个 里程碑时的时间，人类基因组图堪称人类的“第二张解剖图 ，生命科学与人类 社会历史一同进入了一个崭新的时机，科学界无不为之欢呼雀跃。 4 硕士学位论文 第一章绪论 2 0 0 1 年2 月1 2 日，美、日、德、法、英、中科学家和美国塞莱拉公司联合 科学家首次公布了人类基因组“基本信息 人类基因组工作草图及初步的 分析结果。 2 0 0 4 年1 0 月自然杂志公布的“人类基因组”图谱精确版涵盖了9 9 人类 染色体组的图谱，经过美、英、日、德、法、中6 国科学家近3 年的精心“修纂”， 原本遗漏了1 5 万个细节的“人类生命天书 几近完美。新图同时显示，人类基 因实际数只有2 万2 5 万，比最初估计的1 0 万个要少很多。可以说，“人类基 因组”计划的第一步基因测序工作已经完成。随着基因破译速度的加快，人 类将有望揭开d n a 的全部奥秘。 然而，如何从海量数据中挖掘出人类所需要的知识才是生物学研究的最终目 的。目前人类对生物学知识的研究最大的困难是要处理速度以指数方式增长的生 物学数据量。随着生物学数据研究的不断深入，世界范围内建立起了许多涉及生 命科学各个研究领域的生物学数据库，其中有美国国立卫生研究院全国生物技术 研究中心( n c b i ) 的g e n b a n k ；欧洲生物信息学研究所( e b i ) 的( e m b l ) 数据库；日 本国立遗传学研究所( n i g ) 的d n a 数据库( d d b j ) ；瑞士生物信息学研究所( s i b ) 的s w i s s p r o t ；美国b r o o k h a v e n 国家实验室的p d b 。n c b i 开发的e n t e r z 系统 综合了上述各大数据库的信息和m e d l i n e 的文献信息。 中国的生物信息数据库领域建设主要集中在数据信息化管理、数据库标准 化、共享与集成；基因信息评估与检测系统的建立；中国有特殊需要的二级、三 级数据库和专业数据库的构建；保持与国际常用数据库有效连接和及时更新。 生物信息学的市场规模也是巨大而不断急速增长的。2 0 0 2 年e b a s e d 商业 商业市场就达2 0 0 0 亿美元，但是在1 9 9 8 年才8 亿美元；药物基因组学数据收集 和分析在2 0 0 2 年为3 5 亿美元，1 9 9 8 年才1 0 亿美元；生物芯片的数据收集和分 析在2 0 0 2 年和1 9 9 8 年分别为4 0 亿和5 亿美元。由此可以看出，无论是在医药 领域还是生物芯片领域等方面，整个生物信息学涉及的待开发市场规模是十分巨 大的。 从生物信息学概念提出至今，该学科研究内容与理论技术手段不断发展，目 前该领域下列几方面仍是主要研究重剧2 2 】： 1 序列比对 序列比对基本研究内容就是对两个或者两个以上的符号序列进行相似性或 者不相似性的比较。在序列长度较小的情况中，用动态规划算法进行序列比对较 为适用；但在长序列情况中，引入了启发式算法处理较为合适。已有的b a l s t 和f a s t a 算法及相应的改进方法就是基于该基础而开发出来的。以上主要是针 对序列的总体进行比对，至于局部比对，s m i t h w m e r m a n 算法是比较好的一种算 硕士学位论文第一章绪论 法。 2 蛋白质结构比对和预测 蛋白质结构比对和预测基本研究内容就是对两个或者两个以上蛋白质分子 空间结构进行相似性或者不相似性的比较。 目前蛋白质结构预测的方法可以分为两大类。一类是考虑蛋白质分子之间、 蛋白质分子与溶剂之间的相互作用，利用分子力学的能量极小化方法，计算出蛋 白质分子的天然空间结构。另一类方法是所谓的“基于知识的预测方法”，即从 数据库中已有的蛋白质的空间结构与其一级序列之间的联系总结出一定的规律， 逐级从一级序列预n - 级结构，再建立可能的三维模型，根据总结出的空间结构 与其一级序列之间的规律，排除不合理的模型，再根据能量最低原理得到修正的 结构。 3 基因识别、非编码区分析研究 基因识别的基本问题是指在给定基因组序列中正确识别基因的范围和在基 因组序列中的精确位置。在形成蛋白质后被丢弃的非编码区由内含子组成，实验 中发现如果去除了非编码区基因的复制是不能完成的。所以，d n a 序列作为一 种遗传语言，既包含在编码区，又隐含在非编码序列中。 目前大多数基因识别算法都是基于已知的基因顺序。同源比较算法是完全依 赖于已知的顺序，而隐马尔科夫之类的算法都需要对已知的基因结构信号进行学 习或训练。如果能够对更多的e d n a 数据的收集和整理，则可以深入的研究基 因结构，并寻找隐藏在基因的不同结构部分的内在统计规律，从而建立更准确的 基因预测算法。 4 分子进化和比较基因组学 分子进化的主要内容是指对不同物种中同一基因序列的异同来研究生物的 进化，构建进化树。d n a 序列或d n a 编码的氨基酸序列，相关蛋白质的结构比 对都可以研究分子进化( 前提假定是相似种族在基因上具有相似性) 。通过比较 可以在基因组层面上发现哪些是不同种族中共同的、哪些是不同的。 5 序列重叠群装配 重叠群装配是指把大量的较短的序列全体构成了重叠群，并逐步把它们拼接 起来形成序列更长的重叠群，直至得到完整序列的过程。序列的重叠群是一个 n p 完全问题。 6 遗传密码的起源 传统遗传密码的研究认为，密码子与氨基酸之间的关系是生物进化历史上一 次偶然的事件而造成的，并被固定在现代生物的共同祖先里，并一直延续至今。 7 基于结构的药物设计 6 硕士学位论文第一章绪论 基于生物大分子结构及小分子结构的药物设计是生物信息学中的极为重要 的研究领域。 因此，生物信息学无论是在理论研究，还是理论实际应用方面，都是具有 十分宽阔的研究天地。 1 3 论文研究主要内容与工作 随着大规模生物信息学数据库的广泛使用和网络的高速发展，生物学数据研 究方法广泛使用计算机科学技术，人们越来越关注如何更高效和准确地开发和利 用已获得的数据库中的数据。因此，研究基于粗糙集的生物信息学数据分析具有 极重要的理论意义和现实意义。 本文研究基于粗糙集理论的数据分析相关理论及其处理技术，研究的主要内 容与工作包括： 1 基于基因表达序列中的启动子位置特点的分析，给出一种基于粗糙集理 论的d n a 序列中启动子位置的预测计算方法，获取启动子结合位点的启发式预测 规则。为进一步确定基因表达序列数据中确认是否还有启动子，所含启动子位置 点，数据库基因数据中的启动子片段扫描提供了信息支持； 2 基于现有的信息理论与方法的分析基础上，结合粗糙集理论引入信息论 中熵的定义，给出一种基于粗糙集理论的粗糙信息熵定义。为有效地分析生物学 基因表达序列数据中的不确定性度量提供了可计算的数学表达公式，为进一步选 择关联基因的数据预处理提供了可比较的定量数据信息含量分析； 3 基于粗糙信息熵的定义与粗糙集理论中的属性重要度定义，给出了一种 以粗糙信息熵与属性重要度为衡量标准的基因分析与选择算法r m s m e 。依据该 算法，可以选择出所含最小不确定性信息的基因子集，分析基因与疾病分类之间 的关系，获取可以辅助专家进行疾病分类的规则知识。本文最后在实际的医疗数 据集上进行了实验仿真，验证了该算法的有效性并对所获得的知识规则进行了应 用，实验仿真数据表明使用该算法可以获得较好的满意结果。另外，该算法简便、 直观，易于从实际医学治疗与临床案例本质上体现基因与疾病的关系，决策规则 的获取过程及其实际内涵。 1 4 论文结构组织 论文共分五章，结构组织如下： 第一章主要介绍论文研究主题背景与意义，介绍粗糙集理论与生物信息学的 7 硕士学位论文 第一章绪论 国内外相关研究现状，简述本文主要研究内容与工作，并给出论文各章节结构安 排。 第二章简要介绍粗糙集理论与生物信息学有关的基础知识与主要研究内容。 粗糙集理论介绍了近似集、属性重要度、属性依赖性、约简与分辨矩阵；生物信 息学领域主要介绍了基本概念与研究内容，以及相关的计算智能方法。 第三章从信息熵及本文定义的粗糙信息熵概念出发，描述了基于粗糙集理论 的生物信息学启动子与基因选择研究：首先对启动子的识别进行粗糙集方法分 析，获取决策规则，辅助决策系统的研究；然后详细介绍如何将粗糙集理论应用 于基因选择分析，构建疾病分类系统的辅助决策规则集。 第四章利用互联网上公开的生物信息学数据集，对第三章的理论研究方法进 行了实验仿真。对实验仿真结果进行分析，获得对专家系统知识库有意义的决策 规则集。 第五章归纳总结论文的主要研究工作，并展望未来进一步的研究工作。 1 5 本章小结 本章主要从课题研究背景与意义出发，对粗糙集理论结合生物信息学的研究 以提高工作效率、增加专家知识、扩展研究领域并最终将研究成果应用到实践中 去进行了总体框架描述。基于粗糙集理论的生物信息学分析与应用研究已成为智 能信息处理领域一个十分具有前沿性与拓展性的研究课题。在简介粗糙集理论与 生物信息学各自的诞生背景、发展历程、以及研究与应用现状后，本章还介绍了 论文的主要研究内容与结构组织情况。 8 硕士学位论文第二章粗糙集理论与生物信息学 第二章粗糙集理论与生物信息学 从十八世纪数学家倡导用通用符号语言和逻辑演算改革形式逻辑学，到十九 世纪建立命题演算和一阶谓词演算系统，从而形成了经典逻辑学：数理逻辑学体 系。该经典逻辑学只有真、假值之分，但是现实生活有许多含糊的信息不能仅靠 真、假来区别。由此引出了许多理论来描述含糊信息，例如有z a d e h 的模糊理论。 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的，它是可计算的，即有 公式可计算含糊度【2 引。二十世纪八十年代末得到了各国研究人员的关注，九十 年代至今的一系列以粗糙集理论为主题的国际学术会议广泛讨论粗糙集理论并 发表了许多论文，同时也有许多基于该理论的应用系统被成功开发，成功应用于 知识发现、数据挖掘、人工智能和决策支持等领域。 2 1 粗糙集理论基础 粗糙集理论是一种新的数学理论，用来处理不完全、不精确与不确定的数据。 它是建立在分类机制的基础上的，将分类理解为在特定空间上的等价关系，而等 价关系构成了对该空间的划分。同时，知识是对数据的划分，而每一被划分的数 据集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不完全、不精 确与不确定的知识用已知的知识库中的知识来( 近似) 刻画。 因此粗糙集具有与其他处理不精确、不确定问题理论所不具备的特点【2 4 】： 改理论的优点是无需提供问题所需处理的数据集合之外的任何先验信息，所以对 问题的不确定性的描述或处理是比较客观的；而缺点是未能包含处理不精确或不 确定原始数据的机制，所以与其它概率论、模糊数学和证据理论等处理不精确信 息理论有较好的互补性。 2 1 1 不可分辨性与上、下近似 在现实生活中，对象是根据某种定义了的属性关系来区分彼此。在对象分类 过程中，如果将属性相差不大的对象归于同一类，那么对象之间的关系就是不可 分辨关系。 例如出售的咖啡有“味道”与“温度 两种属性，而“味道”有“苦 与“不 苦”，“温度 有“热与“冷 两个属性值，那么对于“热的苦咖啡”、“热的不 苦的咖啡”、“冷的苦咖啡”和“冷的不苦的咖啡”的描述，表明了这些不同咖啡 9 硕士学位论文 第二章粗糙集理论与生物信息学 对象之间的关系是清楚描述的，或者说可以互相区分。但是，当两杯咖啡的描述 仅仅是“热的咖啡”时，那么两杯咖啡是不可以区分的，在“热 的属性值下它 们是不可以被分辨哪一个是苦的，哪一个是不苦的。 对于这种不可分辨的关系，在粗糙集理论中被定义为“不可分辨性”。不可 分辨关系也称之为等效关系，两个“热的苦咖啡”之间的不可分辨关系可以分别 理解为它们在“热与苦 两种属性特征下存在等效不可分辨关系。 由论域中相互间不可分辨的对象组成的集合，是组成论域知识的颗粒。不可 分辨关系这概念在粗糙集理论中占据重要地位，它揭示了知识的颗粒状结构， 是定义其它概念的基础。知识被认为是一族等效关系得集合体，它将论域分割成 一系列的等价类或等效类。而知识的粒度也正是造成使用已有知识不能精确地表 示某些概念的主要原因【2 5 】。 令r 是非空有限论域u 上的等价关系，且r 是不可分辨关系，二元序对 a = ( u ，r ) 称为近似空间。若( x ，y ) r ，那么可以定义对象x 与y 在近似空间彳中 的不可分辨定义为：v ( x ，少) u x u 。 u 关于r 的商集u r 是u 上由r 生成的等价类全体，它构成了u 的一个划 分。商集u r 中的集合称为基本集或原子集。若将u 中的集合称为概念或表示 知识，则a = ( u ，r ) 称为知识库，原子集表示基本概念或知识模块。 而在知识库中，并不是所有的基本概念或者知识模块都是可以精确地去描述 一个给定集合的。即存在一种具有不能被精确定义的数据元素的集合，而粗糙集 理论提出了用近似的方法去描述定义集合中的数据元素。任意一个子集x ，可 以用x 关于彳的一对a p r x 和印崩来“近似 地定义描述： a p r x = u 【x 】i 【x 】sx ) = 扛ui 【x 】x ) a p r x = u l x l 叫n 囝 = x u i 【x f q x 0 1 其中【x 】是x 所在的有限论域中不可分辨关系r 确定的等价类。由上下近似 定义，可以引出以下几个概念。 x 关于彳的正域p o s ( x ) ：下近似集a p r x ，是根据现有知识判断出肯定属于 x 的对象所组成的最大集合；而上近似集a p r x 是根据现有知识判断出可能属于 x 的对象所组成的最小集合。x 关于彳的负域n e o ( x ) ：u a p r x ，是根据现 有知识判断出肯定不属于x 的对象所组成的集合。x 的边界域b n ( x ) ： a p r x a p r x ，是根据现有知识判断出可能属于x 但不能完全肯定是否一定属于 x 的对象中所组成的集合。 1 0 硕士学位论文第二章粗糙集理论与生物信息学 为了形象理解以上概念，可以做出上下近似集，边界域与论域的关系示意图： 边界域b n ( x ) 上近似集a p r x 论域u 下近似集a p r x 图2 - 1 上下近似集，边界与论域关系示意图 因此，下近似集a p r x 是彳中确定包含在x 中的子集合的最大集合，而上近 似集a p r x 是a 中确定包含在x 中的子集合的最小集合。因此，当且仅当 a p r x = a p r x 时，x 是可定义的；当且仅当a p r x a p r x 时，x 是不可定义的， 这时称x 是粗糙集。 2 1 2 属性重要性与属性依赖性 属性重要性的通俗理解为，在一个信息系统i = ( u ，a ) 中，x 彳是一属性 子集，x a ，如果在x 中增加属性x 之后，信息系统分辨度的提高程度，就是 所谓的属性重要性。提高程度越大，可以认为x 对于x 越重要。 定义2 1 设x 彳是一属性子集，x a 是一属性，x 对于x 的属性重要 性，记为s i g x ( x ) 2 6 】： s i g x ( x ) = l i x u x ) i i x i 其中lxi 表示ii n d ( x ) i ，1 n d ( x ) 是x 上给定的所有等价关系的集合族。 文献 2 7 】对属性重要性定义在信息系统s 中，c 和d 分别为条件属性集和决 策属性集，属性子集c c c 关于d 的重要性定义为： s i g d ( c ) = y c ( d ) 一y c - c ( d ) 其嘲班等掣。 粗糙集理论中属性重要性亦有代数定义。如果f 是属性集d 导出的分类， 属性子集b 在属性集b 中的重要性可以描述为【2 8 】： r b ( f ) 一r b 叫( f ) 这表示当从属性集b 中去掉属性子集b 后，对，近似分类的质量的影响。 硕士学位论文第二章粗糙集理论与生物信息学 同时，召曰，当属性集b 是默认的条件属性全集时，以上定义可以简称为条件 属性子集b 的属性重要性。 其他的属性的重要性度量方法，如属性子集召的重要性也可以描述为： p o s b 叫( f ) p o s 8 ( f ) 其中p o s b ( f ) = up o s b ( x ) 。 e ， 以上粗糙集理论中的属性重要性定义是从不同的角度出发的定义描述，但其 本质是对属性集合元素在整个属性集合中的重要性计算，通过对正域区间集合的 定量计算可以获得属性元素对整个论域的重要程度，从而提供了进一步选择重要 属性的依据。 对于什么是知识的依赖性，属性依赖性以及变精度粗糙集模型下的属性近似 依赖性文献 2 9 1 作了如下详细阐述。 知识的依赖性是指，令k = ( 以尺) 是一个近似空间，其中尸，q c r ： ( 1 ) 当且仅当i n d ( p ) c _ i n d ( q ) 时，知识q 依赖于知识p ，即知识q 是由知 识尸导出的，记作p 专q ； ( 2 ) 当且仅当p j q 且q j p ，或i n d ( p ) = i n d ( q ) 时，知识尸与知识q 等 价，记作p 三q ； ( 3 ) 当且仅当尸一q 与q 专尸均不成立时，知识p 与知识q 独立，记作 p q 。 由以上定义可以得知以下等价条件： ( 1 ) p 寸q ； ( 2 ) l n d ( p u q ) = i n d ( q ) ； ( 3 ) p o s p ( q ) = u ： ( 4 ) 对于所有x e u q ，有丛= x ，其中型表示i n d ( p ) x 。 以上等价条件表明，如果知识q 依赖于知识尸，则在知识库中，知识q 是多 余的。那么，这时知识尸u q 与知识p 提供同样的对象特征信息。 属性依赖性的一些重要性质： ( 1 ) 如果尸专q 且q p ，则p 一尺 ( 2 ) 如果尸一q 且q p ，则p i , j q - - - r ( 3 ) 如果p - - - r u q ，则p r 且j p j q ( 4 ) 如果p q 且q u r r ，则j p u r 寸r ( 5 ) 如果p q 且尺专丁，则p t j r - - - q u t ( 6 ) 如果p 寸q 且p d p ，则p q ( 7 ) 如果尸专q 且q c q ，则尸寸q 。 1 2 硕士学位论文 第二章粗糙集理论与生物信息学 对于知识q 部分依赖于p ，即知识尸导出q 的部分知识，可以用知识的正域 定义这种部分可导出关系：令k = ( 以尺) 为一知识库，且尸，q c _ r 。当 k = y e ( q ) = ip o s e ( q ) i iui 时，称知识q 是k ( 0 k 1 ) 度依赖于知识p 的，记作p q 。那么， 当k = 1 时，称q 完全依赖于p ； 当0 k 1 时，称q 粗糙( 部分) 依赖于p ； 当k = 0 时，称q 完全独立于p 。 可以从k 的定义得知，y e ( q ) 是q 和尸之间的依赖度，也可以说y e ( q ) 反映 了通过知识p 可以推导出有多少知识( 对象) 能被划入分类u q 的模块中。但 是，y e ( q ) 并不能完全反映出模块u q 中类之间的分布情况。为此，定义另一 个系数t a x ) 爿丛i i x i ，其中x e u q ，可以计算出知识尸能够将u q 中的 每个类的多少个元素正确划分。 决策表中的属性依赖性可以通过计算一个决策表的属性重要性来判断。令 k = ( 以彳) ，( a = c u d ，c n d = a ，其中c 和d 分别为条件属性集和决策属性 集) ，f 2 jcx c ，acy d ，u y u 6 = 叻。其中u o = u 万，万是全 划分：【，6 = ，l u 6 1 = 1 。 对于】，而言，如果对于每个x x 在x 中是重要的，则称非空子集x 是独立 的；否则x 是依赖的。空集g 称为独立的。 另外，属性依赖性有如下描述【3 0 j ：令pcq ，rcq ，且p ar = a ，如果把p 和r 分别作为一个决策表的条件属性集和决策属性集，且y ，( 尺) = l ，则称r 依赖 于p ，记为p r 。显然，如果尸 r ，则对v a r ，有p 口) 。 2 1 3 约简与分辨矩阵 如果论域u 是研究对象的有限集合集，那么u 中的任何一个子集称为u 中 的一个范畴。而u 中的一条知识既是这些范畴的集合，又是一条知识分类： u = 置l 置 五，k ，以) ) ，其中五a ，置n x ，= o ，u x , = u 。另外， 也将范畴视为一个等价关系。 等价关系的可删除性：在等价关系集合r 中，如果存在r r ，使得