（计算机软件与理论专业论文）基因序列聚类和分类研究.pdf

硕士学位论文 l ! i i i i , i ! i i ! ! # ! 。_ # # = | = = e 自_ # e ! 自e ! _ _ e 摘要 随着现代生物技术的不断发展特别是基因组计划的实施，人们不断获取大量 的基因序列数据，准确、高效的对基因序列数据进行分析并挖掘出隐藏在其中的 对人类有用的信息是非常必要的。聚类和分类技术正是能够对大量基因数据进行 分析的技术。本文着重研究基因序列数据中的聚类和分类算法。 k 一均值聚类算法是一种常用的聚类算法，它采用重复再分配类成员，使同一 个类成员之间分散度最小的方法来获得最佳聚类结果。本文提出了一种基于隐马 尔可夫模型的二次k 均值基因序列聚类算法，引入了同源基因序列核苷酸比率趋 向于一致的生物学特征来对基因序列数据量化并进行初次k 均值聚类，再将第一 次聚类结果作为输入训练出表征序列特征的隐马尔可夫模型，最后采用基于模型 的k 均值方法聚类，使得算法具有较好的聚类正确率。 在研究了微生物基因核苷酸分布规律的基础上，本文提出了一种使用微生物 遗传特征来进行基因序列聚类的方法。首先从每条基因序列中划分出若干个等差 长度的采样片断，然后利用各采样片断的遗传特征值来作为基因序列聚类的依据。 这是一种相对灵敏而且客观和可信度商的分类方法，试验结果表明该方法是可行 的并且具有较好的聚类效果。 在对基因序列进行分类的过程中如果训练样本种类不全，那么用常规分类方 法进行基因序列的分类就会出现类缺失的情况。针对这个问题本文利用基因序列 独特的排列及结构特征提出了多个新的与模型相关的度量方法，通过模型间距离 矩阵获得的阀值动念调整分类的个数，这样就克服了人为假设已标记类个数为实 际类个数的局限性，减少了训练样本种类不全对模型迭代训练的负面影响，成功 解决了序列训练样本种类不全导致类缺失的问题。 关键词：聚类；分类；基因序列；隐马尔可夫模型：k 均值 基冈序列聚类和分类研究 w i t ht h ec o n t i n u o u sd e v e l o p m e n to fm o d e r nb i o l o g yt e c h n o l o g y , e s p e c i a l l yt h e i m p l e m e n to ft h eh u m a ng e n o m ep r o j e c t ，p e o p l eh a v eg r a d u a l l ya c q u i r e dq u a n t i t i e so f g e n es e q u e n c e sd a t aa n di t sq u i t en e c e s s a r yt oa n a l y z eg e n es e q u e n c e sd a t aa c c u r a t e l y a n de f f i c i e n t l y ，a sw e l la st om i n ep o t e n t i a lu s e f u li n f o r m a t i o nf u rp e o p l e c l u s t e r i n g a n dc l a s s i f i c a t i o na r ej u s tt w om a i nm e t h o d so fa n a l y z i n gq u a n t i t i e so fg e n ed a t a t h i s p a p e rf o c u s e so nt h ec l u s t e r i n ga n dc l a s s i f i c a t i o na l g o r i t h m si ng e n es e q u e n c e sd a t a k m e a n si sac o m m o nc l u s t e r i n ga l g o r i t h mw h i c hm a k e sm e m b e r si nas a m ec l a s s h a v et h em i n i m u md i s p e r s i o nv i ar e a s s i g nc l a s sm e m b e r si no r d e rt oo b t a i nt h eb e s t c l u s t e r i n gr e s u l t s i nt h i sp a p e rw ed i s c u s sad o u b l ek m e a nm o d e - b a s e da l g o r i t h mt o m o d e l i n ga n dc l u s t e r i n gg e n es e q u e n c e sd a t a ，u s i n gh i d d e nm a r k o vm o d e l s ( h m m s ) f i r s t ，t h eb i o l o g i c a lc h a r a c t e ro ff o u rn u c l e o t i d e sr a t i oo fh o m o l o g o u sg e n es e q u e n c e s w h i c ha r et r e n dt oa c c o r d a n ti sp r o p o s e dt oi n i t i a lk m e a nc l u s t e r i n go ng e n es e q u e n c e s d a t a ，a n ds e c o n d ，t h ef i r s tc l u s t e r i n gr e s u l t sa t eu s e da si n p u tt ot r a i ns o m eh m m s t h a t c a nd e n o t es e q u e n c e si d e n t i t i e sw e l l f i n a l l y , m o d e b a s e dk m e a na p p r o a c hi sa d a p t e d t oc l u s t e r i n ga g a i n ，t h i sm a k e st h en e wa l g o r i t h mh a sb e t t e rq u a l i t y o nt h eb a s i so fs t u d y i n gt h ed i s t r i b u t i n gr u l e so fm i c r o b i a ln u c l e o t i d e s ，t h i sp a p e r d i s c u s s e sam e t h o dt oc l u s t e r i n gs e q u e n t i a lg e n ed a t ao fm i c r o o r g a n i s m ，u s i n gg e n e t i c c h a r a c t e r i s t i c s f i r s t ，w ed i v i d ee a c hg e n e s e q u e n c ei n t os o m ea r i t h m e t i cs a m p l e s e g m e n t s s e c o n d l y , t h ec l u s t e r i n gi sd o n ea c c o r d i n gt og e n e t i cc h a r a c t e r i s t i c sv a l u eo f t h es a m p l es e g m e n t s t h i si sa ni n g e n i o u sa n di m p e r s o n a lc l u s t e r i n gm e t h o dw h i c hh a s h i g hr e l i a b i l i t y t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i sm e t h o di s f e a s i b l ea n dh a s c o m p a r a t i v e l yb e t t e rc l u s t e r i n gq u a l i t y i nt h ep r o c e s so fc l a s s i f y i n gg e n es e q u e n c e s ，i ft h et r a i n i n gd a t a sc a t e g o r i e sa r e n o tc o m p l e t e ，t h e nt h ec l a s s i f y i n gg e n es e q u e n c e sb yg e n e r a lc l a s s i f i c a t i o nm e t h o d s w i l ll e a dc l a s s e sm i s s i n g a sc o n c e r n i n gt h i sp r o b l e m ，t h i sa r t i c l ep r o m o t e ss e v e r a ln e w m o d e lm e a s u r i n gm e t h o d sb yc o m b i n i n gt h es p e c i a la r r a ya n ds t r u c t u r ef e a t u r eo fg e n e s e q u e n c e s ，i no r d e rt oo b t a i nv a l v et od y n a m i c a l l ya d j u s tt h en u m b e ro fc a t e g o r i e sb y t h ed i s t a n c em a t r i xa m o n gm o d e l s t h e s en e wm e t h o d sw i l lc o n q u e rt h el i m i t a t i o no f s e t t i n gl a b e l e dc l a s sn u m b e rf a c t i t i o u s l ya st h ea c t u a lc l a s sn u m b e r ，r e d u c et h en e g a t i v e i n f l u e n c et om o d e l si t e r a t i v et r a i n i n gc a u s e db yt h ei n c o m p l e t ec a t e g o r i e so ft r a i n i n g d a t a i ts u c c e s s f u l l ys o l v e st h ep r o b l e mo fc l a s sm i s s i n gc a u s e db yt h ei n c o m p l e t e c a t e g o r i e so ft r a i n i n gd a t a i i 硕十学位论文 k e yw o r d s ：c l u s t e r i n g ；c l a s s i f i c a t i o n ；g e n e ss e q u e n c e s ；h i d d e nm a r k o vm o d e l s ； k - m e a n s h i 基因序列聚类和分类研究 插图索引 图2 i 数据挖掘的基本过程和主要步骤8 图2 2 隐马尔可夫模型1 0 图2 3 离散韵隐马尔可夫模型 图3 ik - 均值聚类算法流程1 7 图3 2 基于模型的聚类算法流程1 8 图3 3i ) n a 马尔可夫链1 9 图3 4 初始模型参数情况2 0 图3 5 基于隐马尔可夫模型的二次k 一均值基因序列聚类算法流程2 2 图3 6 两次k 一均值聚类与建模过程一2 2 图3 7a c c e s s i o nn o 为a b 0 0 8 5 8 1 的序列中核苷酸数量和密度分布2 5 图3 8k = 3 时3 0 条序列聚类结果2 5 6 图4 1 遗传特征实现微生物基因序列聚类算法流程3 0 图4 2a c c e s s i o nn o 为b z 5 4 8 3 4 2 的6 0 0 个核苷酸序列( g + c ) m 0 1 密度分布3 3 图4 3k = 3 时3 0 条序列聚类结采3 3 图5 1 基于模型的基因序列分类算法流程4 1 硕士学位论文 表3 表3 表3 表3 附表索引 嗜碱芽孢杆菌的部分基因序列 e m b l 数据库中提取的3 0 条d n a 序列 3 0 条基因序列的实际分类情况 3 0 条序列核苷酸比率的一l o g ：值 1 6 2 2 2 4 2 5 表3 5 序列个数与k 值均增加时两种聚类算法正确率的变化 表4 1e m b l 数据库中提取的3 0 条微生物d n a 序列一 表4 23 0 条基因序列的编号与实际分类的情况 表4 3n = 4 时所有采样片断的一l o l o g ，值 表4 4 序列个数与k 值均增加时聚类正确率的变化 表5 16 0 条基因序列的编号与实际分类的情况 表5 2 方案一实验数据情况 表5 3 方案二实验数据情况 表5 4 方案一不同序列个数条件下u = o 且l 值改变时分类正确率的变化 表5 5 方案二不同序列个数条件下l 和u 值改变时分类正确率的变化 v 2 6 3 0 3 2 3 3 3 4 4 2 4 2 4 2 4 3 4 3 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 翱澎日期：洲年；月哕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密卯。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 翱澎 矜铆 1 日期：枷年；月研日 日期：泗占年了月 甲日 一i i i l l i l l l i 碳士学i 位论文l i i 骶岛耐黼黼舞嘲哺。懈 _2。2。“”“一 1 1 研究动机与意义 第1 章绪论 自上世纪9 0 年代以来，生命科学经历了前所未有的高速发展，为了处理随之 而来急剧增加的生物信息，人们巧妙的将生命科学与信息技术结合起来，诞生了 一门新的学科一一生物信息学。生物信息学是一门交叉学科，它综合运用了以计 算机技术为代表的信息学和生命科学的知识来对生物信息进行收集、处理、分析 并最终获得所研究生物数据的生物学意义。目前生物信息学的研究对象主要是功 能基因组学和蛋白质组学，其主要任务是分析研究生物分子数据中所蕴涵的各种 信息，特别是从基因组的整体水平上对基因的活动规律进行阐述，研究细胞内全 部蛋白质的组成及其活动规律”。 随着分子生物学和现代医学的迅速发展，特别是人类基因组计划的实施和完 成，人类已经获得大量的生物分子数据，成百上千的生物学数据库迅速出现和成 长，并且其积累速度仍在不断提高【2 1 ，如何利用好获得的数据并挖掘出隐藏在其 中的对人类有用的信息则是一个迫切需要解决的问题。数据挖掘正是一种能够从 大量数据中提取有用的、具有潜在效用知识的技术，且已经在生物信息学领域崭 露头角，逐渐成为生物信息处理的有效方法之一。 分子生物学研究的重大突破，尤其是核苷酸序列研究的进步使得生物系统分 类的基础发生了重大的变化，分类系统已经或正在随着分子标准的不断渗入而完 善。所谓分子标准1 1 主要是指建立在核瞢酸分析技术基础上的分类方法，它要求 生物的序列化，以核苷酸序列为基础研究各种生物学中的重大问题。基因序列聚 类、分类方法通过把目标序列放入已知功能或相对同源的类里，这样就可以利用 已知功能的基因推测同一类中未知功能基因的功能。基因聚类、分类分析还有助 于发现组序列之间的差异以及相似性关系，以便对一个基因家族的特征有基本 的了解，在基因序列的研究中聚类分析已经成为种普遍采用的方法，对数量巨 大的核苷酸序列进行分类分析日渐成为目前生命科学研究的重点。 数据挖掘中的聚类、分类技术能够将具有某种相似性的对象聚集到一起，这 些对象构成了功能相近或者结构相关的分组，研究这些分组对于从已知功能和结 构的对象推断出未知对象的可能功能和结构具有极其重要的意义。 j l l l i i基因序列寨类和筮i 耋丝耋_ | _ 自j = 目- - _ # = = = j _ _ | _ = ；= 目目_ 目2 2 _ 口2 ；_ 2 5 2 4 4 4 5 2 9 一 1 2 研究目的 多年来人们一直把生物学当作是一门实验科学，对生物学的研究主要依赖于 对实验数据的分析和处理，但是随着生命科学和计算机技术的迅猛发展，生物数 据积累速度不断加快，而且各种类型的生物数据数量巨大，特别是d n a 序列数 据以千兆计，传统的分析方法已经远远不能满足研究的需要，这就要求采用更新 的方法和工具来对生物数据进行处理和分析。生物信息学将生命科学与信息技术， 尤其是计算机与网络技术结合，使得人们能够系统的、有针对性的对海量数据进 行研究，在指导实验、精心设计实验方面将会发挥重要的作用。科学家预言：生 物信息学将是2 1 世纪生物学的核心。 分子生物学中心法则认为遗传信息的载体主要是d n a ，生物信息学的大量研 究也都集中在生物的遗传物质d n a 的数据分析上，其中控制生物体性状的一系 列d n a 片段被称之为基因。d n a 序列由四种核替组成：腺嘌呤( a ) 、胞嘧啶( c ) 、 鸟瞟呤( g ) 、胸腺嘧啶( t ) ，分别用字符a 、c 、g 、t 表示。d n a 可以在其自我复 制过程中实现遗传信息的传递，并决定蛋白质氨基酸序列的编码顺序，蛋白质序 列又决定了蛋白质的结构，蛋白质结构最终决定蛋白质的功能n 1 。 分子生物学的一个普遍的规律是序列决定结构，结构决定功能。在对基因序 列相似性的研究过程中时，我们希望根据基因序列的相似性推测出序列之间结构 和功能的相似性。如果基因序列之间有相当的同源性，那么它们之间就可能有功 能上的高度相似性。利用同源比较算法，将待检测的新基因序到在d n a 序列数 据库中序列进行检索后，可以得到一系列与新基因同源性较高的基因或片段，这 些基因和片段已知的功能信息就为进一步研究新基因功能提供了具有重要参考价 值的导向 2 1 。利用数据挖掘的聚类、分类技术寻找同源序列就是要通过一系列的 方法将待测基因序列之间的差异标准化，比较序列的相似度来发现功能和结构相 似的序列。 目前世界上有3 个相互联系的组织维护各自的d n a 数据库，他们分别是美国 的国家生物技术信息中心( n c b i ) 、欧洲生物信息学研究所( e b i ) 和日本d n a 数据库( d d b j ) 1 2 ，这些中心和全球的基因组研究实验室通过互联网联系相互合 作，各数据库中的数据也基本保持同步。作为生物信息处理的工具之一，数据挖 掘技术能够对分布式的生物数据进行清理和语义集成，消除了数据异构和冗余的 问题，为展开大规模研究提供了必备的条件。在序列分析、蛋白质结构预测和基 因表达分析等生物学研究的熟点领域也已经开发出多种有意义的数据挖掘模式、 挖掘算法，并取得了良好的效果。数据挖掘技术因其在大规模数据处理方面的卓 越能力必将在生物信息学的研究中占据越来越重要的地位。 ：i：鲁兰：。，。，；。，。：。一 1 3 研究内容 本文对生物基因序列的聚类和分类算法进行了研究。基因序列聚类方面，在 研究分析了经典的k ，均值聚类分析算法，并结合基因序列核苷酸概率分布潜在规 律的基础上，采用了新的基因序列量化指标，利用初次聚类结果来构造初始化隐 马尔可夫模型，设计并实现了基于隐马尔可夫模型的二次k 均值序列聚类算法， 并应用到基因序列数据的聚类分析中。针对微生物基因核苷酸分稻特有的规律， 将微生物遗传分类法相关的分子生物学知识应用到基因序列聚类中，提出了使用 基因序列采样片断来量化序列的方法，并将微生物遗传特征值作为基因序列聚类 的依据。基因序列分类过程中初始标记的基因序列不一定能够包括所有类别，为 了解决因序列训练样本种类不全导致的类缺失问题，我们采用了基因序列与类模 型的距离公式来衡量模型与序列的相关性，并在此基础上提出了模型内、外置信 度的概念，最后通过使用模型置信度来构造模型之间的距离矩阵，根据模型间距 离矩阵获得的阀值动态调整分类的个数。 1 4 本文主要工作 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚 类。分类与聚类的主要区别是分类需要预先定义的类和带类标的训练实例。本 文主要研究的是聚类和分类技术在生物基因序列领域的应用。工作主要集中在如 何对基因序列进行描述，采用什么标准来度量基因序列之间的相似性，以及如何 构造菜一类别序列的模型和动态调整序列类别的个数，并提高聚类和分类的正确 率等。这种基因序列的聚类和分类在生物学中意义重大，它可以用来发现特征序 列进行基因结构和功能划分，证明序列间的同源性。本文研究了直接将聚类和 分类算法应用到基因序列领域存在的一些问题，通过对比可能存在的性能差异， 利用隐马尔可夫模型来对基因序列进行建模和描述，提出了基于隐马尔可夫模型 的二次k - 均值基因序列聚类算法。针对微生物基因序列在遗传分类法则中独有的 特点，采用核苷酸分析得到的遗传相关性作为比较的准则，将微生物遗传特征值 作为基因序列聚类的依据。最后在利用隐马尔可夫模型对基因序列训练样本进行 建模的基础上，提出了新的模型间距离计算公式，并通过模型问距离矩阵获得的 阀值动态添加新的序列类别，使得基于模型的分类算法在初始类个数不完整的情 况下也能实现正确的分类。本论文主要工作如下： 一、基因序列数据聚类分析及其性能评价 在了解了生物学相关理论与基于模型的聚类方法基础上，提出基于隐马尔可 基因序列聚类和分类研究 夫模型的二次k 一均值基因序列聚类算法，并应用在基因序列数据分析中。再通过 对比传统k 均值算法和基于隐马尔可夫模型的二次k 均值两种聚类算法在不同 基因序列条件下聚类正确率的变化，来对这两种聚类算法进行性能评价。主要工 作有以下几个方面： 1 研究隐马尔可夫概率模型在d n a 一级结构水平的应用，尤其是在基因序 列聚类方面的应用。 2 根据同源基因序列四种核苷酸比率趋向于一致的分子生物学理论，提出用 四种核苷酸比率来对每条基因序列进行描述的方法。 3 了解欧洲生物信息学研究所( e b i ) 维护的e m b l 核酸序列数据库，熟练使 用互联网上序列提取系统( s r s ) 1 4 进行核酸序列查询。 4 研究将初次聚类的结果作为输入数据进行二次聚类的方法，设计基于隐马 尔可夫模型的二次k 均值聚类算法。 5 对基于隐马尔可夫模型的二次k 均值聚类算法进行性能评价分析。 二、微生物基因序列聚类分析及其性能评价 在研究了遗传分类法与微生物基因核苷酸分布规律的基础上，提出利用遗传 特征实现微生物基因序列数据聚类分析的算法，并采用不同基因序列条件下的聚 类正确率了来评判聚类质量。主要工作有以下几个方面： 1 对序列集合中的每一条微生物基因序列从相同的方向取定长片断，再对每 条序列进行采样。 2 根据微生物基因序列独有的特点，设计出使用基因序列的遗传特征值来表 示微生物基因组成特征的方法。 3 熟悉从互联网上序列提取系统进行微生物核酸序列查询的方法。 4 利用k 。均值聚类算法对微生物基因序列数据进行聚类。 5 利用不同条件下基因序列聚类结果的j f 确率进行性能评价分析。 三、基因序列数据分类及其性能评价 目前采用的分类的方法大多都是假定己标记类的样本是完全样本，为了消除 这种人为假设的局限性，首先定义了新的序列与模型之间的距离并提出了模型内、 外置信度的概念，使用创建的模型间距离矩阵来对未标记的序列进行分类，然后 通过比较不同条件下基因序列的分类准确率来对本分类算法进行性能评价。主要 工作有以下几个方面： 1 定义基因序列与模型的距离公式，模型的内置信度和外置信度公式，以及 新的模型之间的距离公式。 2 设计基于隐马尔可夫模型的基因序列分类算法，利用模型间距离矩阵来评 判基因序列与模型的相似性，动态添加新类别，并将其应用到不同条件下基因序 列数据分类中。 硕士学位论文 3 利用不同条件下基因序列分类结果的正确率进行性能评价分析。 1 5 本文组织结构 全文分为五章，主要内容如下： 第一章概述了本文的研究动机与意义、研究目的、研究内容、主要工作以及 组织结构等。第二章详细介绍了研究的背景知识及研究现状，包括生物信息学、 数据挖掘、隐马尔可夫模型的相关概念和应用、生物信息处理中的聚类和分类技 术。第三章首先介绍了基因序列基本知识，然后介绍k 均值基因序列聚类算法和 基于模型的聚类算法，针对k 均值聚类算法在随机初始化k 个类时存在的不确 定性，设计并实现了基于隐马尔可夫模型的二次k 均值基因序列聚类算法，接着 将基于隐马尔可夫模型的二次k 均值聚类算法和传统k 均值算法在不同基因序 列条件下进行聚类正确率的比较，来对这两种聚类算法进行性能比较和对新的聚 类算法进行评价分析。第四章首先介绍了微生物基因组相关研究、微生物分类和 遗传分类法，利用微生物基因序列独特的分子生物学特点，使用遗传特征进行微 生物基因序列聚类分析，接着利用不同条件下基因序列分类结果的正确率进行性 能评价分析。第五章首先介绍了数据分类的定义以及目前数据分类研究中常用的 几种方法，接着分析了基因序列分类过程中常规分类方法的不足并提出了改进的 目标，然后结合基因序列的结构特征提出了多个新的与模型相关的度量方法，最 后设计并实现基于隐马尔可夫模型的基因序列分类方法并对其进行性能评价。文 章最后对全文进行了总结。 基因序列聚类和分类研究 第2 章背景知识及研究现状 2 1生物信息处理中的数据挖掘 2 1 1 生物信息学概念与发展 2 0 世纪9 0 年代以来，伴随着各种基因组测序计划的实施和分子结构测定技 术的突破及因特网的普及，成百上千的生物学数据库不断涌现和扩充，生物信息 数据正以惊人的速度增长。截止2 0 0 4 年止，仅登录在美国g e n b a n k 数据库中的 d n a 序列总量已超过7 0 亿个碱基对。数据的大量积累并不仅仅表现在d n a 序 列方面，还包括蛋白质的一级结构即氮基酸序列的增长。但是拥有数据并不等获 得了知识，数据资源的急副嘭胀首先迫使我们不得不考虑寻求一种强有力的1 具 去组织它们，以利于对已知生物学知识的储存和进一步加工利用，这就促进了以 收集、储存、检索、分析、开发、利用这些巨型信息资源的生物信息学的发展”- 。 1 9 9 5 年，在美国人类基因组计划( h u m a ng e n o m ep r o j c o t ，h g p ) 第一个五年总 结报告中给出了一个较为完整的生物信息学的定义m ：生物信息学是一门交叉学 科，它包含了生物信息的获取、处理、褚存、分发、分析和解释在内的所有方面， 它综合运用数学、计算机科学和生物学等各种工具来阐明和解释大量数据所包含 的生物学意义。 目前生物信息学的研究对象主要是d n a 序列和蛋白质序列，研究范畴是以对 基因组d n a 序列的分析作为出发点，分析研究序列数据中所含的各种信息，寻 找或发现新基因，特别是d n a 序列中遗传及控制信息，并在此基础上研究基因 的功能，研究蛋白质序列与结构及功能的关系，模拟和预测蛋白质的空间结构， 分析蛋白质的性质等口”。美国于1 9 9 0 年正式启动了耗资数十亿美圆的人类基因 组计划，其目的在于阐明人类基因组d n a 核苷酸序列，破译人类全部遗传信息， 到2 0 0 3 年为止，该计划已经得到人类的3 0 亿个碱基对，其他种属基冈组的d n a 全序列测定也在积极地进行。生物信息学的发展在国内外基本上都处在起步阶段， 我国生物信息学经过十余年的发展也已经取得了不少成果”i ，如北京大学研究建 立起一个e m b l 的镜像数据库，并提供数据检索服务。复旦大学遗传学研究所为 克隆新基冈而建立的一整套生物信息系统也已初具规模。中科院上海生化所、生 物物理等在结构生物学和基因预测研究方面也有相当的基础，中科院计算所作为 我国计算机科学的项尖机构。利用自身优势，也开始在生物信息方面投入大量的 我国计算机科学的顶尖机构。利用自身优势，也开始在生物信息方面投入大量的 硕士学位论文 人力物力，从事相关的研究。 2 1 2 数据挖掘定义 数据挖掘( d a t am i n i n g ) h7 】也称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) ，是一种用于从大型数据库或数据仓库中探索和抽取隐藏信息的新 技术。它能从存有海量信息的数据库中识别出新颖有效的知识，并开采出具有潜 在效用的模式，最终找出可用来指导商业行为或辅助科学研究的最有价值的信息。 从技术上来划分，数据挖掘分为两大类：探索型数据挖掘和预测型数据挖掘。探 索型数据挖掘包括一系列在预先未知任何现有模式的情况下在数据内查找模型的 技术，如频度分析、分群和关联分析等。预测型数据挖掘包括一系列在数据中查 找目标变量与其他变量之间关系的技术，如分类、聚类、数值预测等。数据挖掘 的主要步骤大体如下【i 。，1 0 l ： 1 数据选择 全面而丰富的数据是数据挖掘的前提，没有数据挖掘也就无从谈起，所以给 需要解决的问题一个明确的定义，认清数据挖掘的目的并选择合适的数据是非常 关键的。所选择的数据可以来自现有的数据库系统或者数据仓库。 2 数据预处理 由于一些不确定因素导致采集到的数据可能存在瑕疵或者不一致性，甚至出 现部分数据缺失的情况，因此对数据的整理是必须的。通过数据整理，可以提高 研究数据的质量，为下一步数据挖掘的顺利开展做好了准备。 3 数据韵转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的。建立一 个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 4 数据挖掘 利用各种数据挖掘方法对所得到的经过转换的数据进行挖掘，在这个过程中 可以对所选择的算法进行改进和完善，所有模式推导与知识的获取工作均由挖掘 算法来实现。 5 对数据分析和同化 在对挖掘结果进行解释和评估的基础上，需要对结果进行细致而深入的分析， 并将分析得到的知识集成到业务信息系统的组织结构中去，这是一个同化的过程， 决策者可以依据这些知识来进行科学决策。 文献【9 】对数据挖掘基本过程的描述如图2 1 所示： 基因序列聚类和分类研究 i ，、 j 属裔 预处理 谂磊试一+ 氤 的数据 + | 后的数卜- l 的数据l 的信息j l 的知 据 、 u 图2 1 数据挖掘的基本过程和主要步骤 随着各种大型业务数据库尤其是生物数据库信息量的迅速膨胀，以及对这些 数据的理解和解释的需要，数据挖掘的研究正方兴未艾1 1 0 ，今后研究的焦点可能 有：研究专门用于知识发现的数据挖掘语言；研究i n t e r n e t 上的数据挖掘方法；对 各种非结构化数据，如：文本数据、图形图像数据、多媒体数据的挖掘；研究数 据挖掘与数据仓库相结合的方式，数据挖掘与数据仓库一体化的研究等。数据挖 掘必将以更加灵活和强大的分析能力在各行各业得到应用。 2 1 3 研究现状及应用 同时利用和处理大量的生物信息数据，探索其中的生物学规律，是当前国外 生物信息学研究的主要内容。数据挖掘技术对生物信息学的研究与发展起着至关 重要的作用，并且已经在凭借其强大的模式发现功能实现了对多种生物学知识模 式的挖掘。如概念类别描述、关联分析、分类和预测、聚类分析、孤立点分析以 及演变分析0 - “】。目前数据挖掘在生物信息学中的研究重点主要表现在以下几个 方面： ( 1 ) 分布式数据库语义集成与数据处理。许多国家和研究组织都建立了基因 序列数据库、蛋白质结构和功能数据库以及其它信息中心数据库，这些数据不但 分散而且存储介质多样，在同一数据库中可能存在着大量重复或者一些高度相似 的数据，造成了数据冗余，因此需要对这种异构和分布式的数据库进行语义集成。 数据挖掘中的数据清理和数据集成方法02 1 有助于对数据库进行集成与重构，通过 对数据的清理、变换、编码对数据进行系统而协同的分析，将其变成可以被正确 奄询和使用的数据。 ( 2 ) d n a 序列搜索和比对l 。生物信息学的大量研究都集中在对d n a 数据的 分析上，在基因分析中一个最为重要的搜索问题是d n a 序列中的相似搜索和比 较。通过对分别来自带病和健康组织的基因序列进行相似搜索和比较，可以归纳 出两种基因序列模式之问的区别和联系，有助于推导出抗病基因片断和致病基因 片断。为识别一个新发现的基因和一个已知基因家族之间的进化关系而对两个 硕士学位论文 d n a 序列进行比对，找出它们之间的最大匹配，确定它们的同源性或相异性，高 效的数据搜索和序列比对算法是数据挖掘研究的重点。 ( 3 ) 路径分析。一种疾病可能是由多种致病基因共同弓l 起的，不同的致病基 因在疾病发展的各个阶段既有区别又相互联系。关联规则，15 ”】等数据挖掘技术 可以对路径进行分析有助于发现基因组和基因间的交叉与联系，帮助确定在目 标样本中出现的基因种类，在疾病发展的每个阶段探索致病基因的构成特点，结 合疾病的不同发展阶段针对性的开发出发治疗药物，这就能够更好的在疾病发展 的初期对其进行控制并对症下药，从而取得更好的治疗效果。 ( 4 ) 生物数据可视化。由于生物数据的高复杂性和高维性，只能通过图、树、 方体和链等形式来对生物数据进行抽象与表示。同时，对数据分析后得到的数据 结果也需要以图形的方式表现i ，以便于寻找数据之间的规律和关系。数据可视 化促进了对复杂结构和序列模式的理解，有助于从新的视角建立数据模型，在生 物信息学的数据挖掘中起着重要的作用。 ( 5 ) 生物数据聚类和分类。生物信息学中对生物数据的聚类、分类研究主要 是将生物序列放入已知功能或相对同源的类罩，划分出为一系列有意义的子集， 这样就可以利用已知功能的生物序列推测出同一类中未知功能序列的功能。在基 因的表达、d n a 序列的研究中，聚类、分类已经成为最常用的程序。聚类、分类 技术主要包括传统的模式识别方法和数学分类法。聚类算法1 3 1 有基于划分的方法、 基于层次的方法、基于网格的方法和基于模型的方法。分类算法【3 t 1 主要包括判定 树归纳分类、贝叶斯分类、神经网络技术、后向传播分类、遗传算法、粗糙集和 模糊集方法等。 对生物序列进行聚类与分类研究是进行生物数据挖掘的重要手段之一，本文 将着重对生物基因序列进行聚类和分类研究。 2 2 隐马尔可夫模型介绍 2 2 1 模型结构 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，h m m ) ，”堤一个动态的统计模型， 此模型由包含一个初始状态( b ) 以及终止状态( e ) 的多个结点线性序列构成。 其中的某一个状态可以以一定的概率转移到另外的状态( 终止状态除外) ，而且在 转移时产生输出，能产生的输出是有限的，输出也将以一定的概率产生。隐马尔 可夫模型可看作一系列可相互转移的有限状态的集合，这些状态的转移又是间接 地通过观察序列来描述的，它包含两个随机过程：状态间转移过程和发散观察序 列的过程，其中状态问转移过程称为隐过程，它是间接的通过观察序列来描述的。 基因序列聚类和分类研究 目e ，| - _ e 自_ = 目- _ = ! ! = ! ，- _ # = ! = - - _ e e = = = - _ _ = j i i = 自! = _ - = # = j _ - e g ! = = | _ - = ! = = = 自= ! = ! 自_ _ = ! = 鼍 根据观察符号产生方式的不同，隐马尔可夫模型分为离散的和连续的两种。针对 基因序列的构成特征，需要采用离散类型来对基因序列进行建模，本文所涉及到 的模型均为离散的隐马尔可夫模型。 一个离散的隐马尔可夫模型丑可以特征化描述为如下5 个部分】： 1 模型的隐状态个数，用s = 碱，s 2 ，“，s u j 来表示所有的隐状态，对于每一 个时间f ，用q 代表在时间t 时的隐状态。 2 每个隐状态具有的离散观察符号的个数m ，这些观察值可以用来表示模 型的输出，用v = v ，也，一。 来表示所有的观察符号。 3 状态转移概率分布a = ， q ，= h 吼“= s ji 岛= s , l ，1 f ，j s n ( 2 1 ) 并且存在约束条件：q ，0 ， = l ，1 - i ，n ( 2 2 ) 4 状态，时的观察符号概犟分布b = 喊( t ) ， b j ( k ) = h ha t t iq 。= s ，】，1 j n ，1 k m ( 2 3 ) 5 初始状态分布z = 防 ， 珥= p q l = e 】，1s i n ( 2 4 ) 并且存在约束条件： n 巧o ，一= 1 ( 2 5 ) 一个离散的隐马尔可夫模型可以形式化定义为个三元组： 五= ( 爿，b ，# )( 2 6 ) 文献【1 5 】用图2 2 表示个隐马尔可夫模型： q ；一lq h lq f + 2 x ，一lx fx f + 1x f + 2 图2 2 隐马尔可夫模型 其中q 位置就是隐马尔可夫模型的隐状态，每一个时间f 对应一个隐状态，并 通过状态转移概率嘞从状态i 转移到状态，。x 位置表示观察状态( 发散状态) ， 通过观察符号概率分布函数b j ( k ) 产生若干观察值。 硕士学位论文 图2 3 离散的隐马尔可夫模型 图2 3 是一个具有隐状态个数n = 4 ，s = 俩，是，s ，s , i ，且离散观察符号的个数 m = 4 ，观察符号集合v = h ，v 2 ，v 3 ，v 的离散的隐马尔可夫模型。 2 2 2 模型的三个关键问题 1 h m m 的基本问题之一：评估问题( e v a l u a t i o np r o b l e m ) 给定一个观察序列o = q q 0 r 和模型 = ( 一，b ，f ) ，求某个观察值序列的概率 p = ( d l 丑) 。这个问题的解决用通常被称为“向前一向后”算法( f o r w a r d b a c k w a r d ) 的b a u m w e l c h 算法解决b 一1 92 0 1 。 给定一个特定的隐状态序列 q = g l g ：q r ( 2 8 ) 此时由q 状态转移路径产生观察序列0 的概率为 r p ( o iq 五) = f i p ( qi q , ，五) ( 2 8 ) t = l 一般假设每个观察值产生概率是独立的，可以得到 e ( o l q ， ) = 气( d 1 ) ( d 2 ) c o t ) ( 2 9 ) 模型丑具有隐状态q 的概率为 p ( q i a ) = n ( 2 1 0 ) 根据上述公式容易推出： p ( o i a ) = p ( o i q ，a ) p ( q i 五) = ，( q ) 。( 0 2 ) ( 2 1 1 ) * q 。( q ) 2 h m m 的基本问题之二：解码问题( d e c o d i n gp r o b l e m ) 已知观测序列o = 0 , 0 2 q 和模型五= ( 一，b ，z ) ，如何估计与观测序列相对应的最 基因序列聚类和分类研究 佳状态序列，即在某种准则下找到一个能够镀贴切的“解释”观测序列的隐状态 序列，此问题可转化为找到一个最佳隐状态序列满足概率e ( q i o ) 最大。这个问题 可由v i t e r b i 算法d 8 1 9 解决。由贝叶斯公式得到： 删o ) = 篱 ( 2 1 2 ) 需要递归的计算p ( q ，d ) ： 定义 4 ( f ) = m a x m ，扎，( 吼，吼，- 一，吼一。，吼= q j ，o l ，d 2 ，