（计算机软件与理论专业论文）基因表达数据聚类和分子结构数据库搜索.pdf

摘要 生物信息学是一门内涵非常丰富的交叉学科，该学科的核心研究内容是使用 计算机科学与技术对生物学研究的实验数据管理、统计、分析并预测，其作用已 经渗透到现代生物学研究的各个主要领域和阶段。生物信息学是当前计算机科学 研究中的一个热点领域。由于研究对象的背景不同，生物信息学与传统的计算机 科学具有相当不同的研究特点和方法。在这个领域不断有开放性问题涌现，同时 已有问题也仍然需要新的方法与技术以适应不同的应用情况。 本文深入讨论了在生物信息学研究中的两个热点问题：基因表达数据聚类分 析和结构数据库搜索。我们汇总了在这两个问题上已有的工作，对其中有价值的 思想，方法和技术做了总结与评估，在此基础上，提出了用于新型基因样本一时 间微阵列基因表达数据的聚类算法g t r i c l u s t e r 和用于化学化合物分子结构 数据库的子结构搜索算法g s t r i n g 。 与传统的聚类算法不同，g t r c l u s t e r 用于从新型的g s t 微阵列数据中挖 掘一致性三维聚类簇。与已有的方法相比，g t r i c l u s t e r 突破了强加的限制， 使用了更为通用的三维聚类模型。因此，g t r i c l u s t e r 能够找出有可能被已有 方法忽略但却具有生物学重要性的一致性基因聚类簇。在真实数据库上进行的实 验验证了该算法的有效性，同时显示g t r i c l u s t e r 具有良好的噪音鲁棒性。合 理地运用g t r j c l u s t e r 可以充分利用新型微阵列数据的优势，给用户提供有用 的信息。 g s t r i n g 是针对化学化合物分子结构数据库进行子图搜索的算法。我们从领 域知识得到启发，将语义信息记录在用于表示结构的字符串中，使用合适的方法 对这些字符串构建索引以支持有意义的子结构搜索操作。对于给定的查询，我们 使用这些索引过滤图数据库，得到较小的候选集，减少需要进行的高时间复杂度 的子图同构匹配。g s t r i n g 也能很方便地支持相似子图搜索问题。在真实数据集 上的实验表明，与已有的方法相比，g s t r i n g 在索引大小，索引构建时间，索引 过滤效率和准确率等主要性能指标上取得较好的平衡。在上述工作的基础上，我 们开发了一个原型系统。 关键字：生物信息学，基因表达数据，微阵列，聚类，双聚类，图数据库，分子 结构数据库，子图搜索，图索引，图相似性查询。 a b s t r a c t b i o i n f o r m a t i c si sa l li n t e r d i s c i p l i n ew i t hs i g n i f i c a n tm e a n i n g ，w h o s ec o r ec o n t e n t i n c l u d e sa p p l y i n gc o m p u t e rs c i e n c ea n dt e c h n o l o g yt ot h em a n a g e m e n t ，s t a t i s t i c sa n d a n a l y s i so ft h ed a t as o u r c e df r o mb i o l o g i c a lr e s e a r c h i t sf u n c t i o nh a se f f e c t e do nt h e v a r i o u sf i e l d sa n dl e v e l so fm o d e mb i o l o g i c a lr e s e a r c h n o w , b i o i n f o r m a t i c si sah o t t o p i co fc o m p u t e rs c i e n c e d u et ot h ed i f i e r e n tt a s kb a c k g r o u n d ，b i o i n f o r m a t i c sh o l d s d i 腩r e n tc h a r a c t e r i s t i c sa n dm e t h o d sf r o mt r a d i t i o n a lc o m p u t e rs c i e n c er e s e a r c h al o t o fo p e np r o b l e m sc o n t i n u et oe m e r g ei n t h i sf i e l d w h i l et h ee x i s t e dp r o b l e m sd e s i r e n e wm e t h o d sa n dt e c h n i q u e st of a c i l i t a t ec h a n g i n ga p p l i c a t i o n s o u r p a d e ri n v e s t i g a t e st w oi m p o r t a n tp r o b l e m so f b i o i n f o r m a t i c s ：g e n ee x p r e s s i o n d a t ac l u s t e r i n ga n a l y s i sa n ds t r u c t u r a ld a t a b a s es e a r c h i n g w es u m m a r yt h ee x i s t e d w o r k so nt h e s et w op r o b l e m sa n de v a l u a t e st h ev a l u a b l ei d e a s m e t h o d sa n dt e c h n i q u e s b a s e do nt h ek n o w l e d g e ，w ep r o p o s eg t r i c l u s t e rw h i c hi sac l u s t e r i n ga l g o r i t h m f o rh o v e lg e n e s a m p l e t i m em i c r o a r m yd a t a s e ta n dg s 缸n gf o rc h e m i c a lc o m p o u n d s t r u c t u r ed a t a b a s es e a r c h d i f f j r e n tf r o mt r a d i t i o n a jb i c l u s t e r i n ga l g o r i t h m g t r i c l u s t e rm i n e sc o h e r e n t 3 de l u s t e r si nt h eh o v e lg s tm i c r o a r r yd a t a s e t c o m p a r e dt ot l l ee x i s t e dm e t h o d g t r i c l u s t e r c o n q u e r st h ei m p o s e dr e s t r i c t i o na n du s e sam o r eg e n e r a l3 dc l u s t e r m o d e l t h u s ，g t r i c l u s t e rh a st h ec a p a b i l i t yt of i n ds o m eb i o l o g i c a ls i g n i f i c a n c e c o h e r e n tg e n ec l u s t e rw h i c hm a y b eo m i t t e db ye x i s t e dm e t h o d e x p e r i m e r i to n r e a l w o r l dd a t a s e tv e r i f i e st h ee f f e c t i v e n e s so fg t r i c l u s t e ra n da l s os h o w st h e r o b u s t n e s st on o i s e t h u s ，g t r i c l u s t e rc a nt a k ea d v a n t a g eo fn o v e lg s t m i c m a r r a yd a t a s e ta n dp r o v i d en s e f u li n f o r m a t i o nt ou s e r s g s t r i n gi sas u b g r a p hs e a r c ha l g o r i t h md e s i g n e df o rc h e m i c a lc o m p o u n d s t r u c t u r e d a t a b a s e w ea r ei n s p i r e db yd o m a l nk n o w l e d g ea n dr e c o r ds e m a n t i e si n t ot h es t r i n g s r e p r e s e n t ss t r u c t u r e s t h e n , w ei n d e xt h e s es t r i n g si np r o p e rw a y t os u p p o r tm e a n i n g s u b s t r u c t u r es e a r c h f o rag i v e nq u e r y , w ef i l t e rt h ew h o l eg r a p ht h r o u g ht h ei n d e xt o g e tas m a l l e rc a n d i d a t es e t t h u s ，h i e , ht i m e e o m p l e x i t ys u b g r a p hi s o m o r p h i s m m a t c h i n go p e r a t i o n sa r er e d u c e d g s t r i n gc a na l s of a c i l i t a t es i m i l a r i t ys u b g r a p hs e a r c h e x p e r i m e n to nr e a l w o r l dd a t a s e ts h o w st h a tg s t r i n gk e e p sab e t t e rb a l a n c eb e t w e e n i n d e xs i z e ，c o n s t r u c t i o nt i m e ，c a n d i d a t es e ts i z ea n df i l t e r i n ga c c u r a c yt h a nt h ee x i s t e d m e t h o d s b a s e do nt h ea b o u v ea l g o r i t h m ，w ed e v e l o pap r o t o t y p es y s t e m k e y w o r d s ：b i o i n f o r m a t i c s ，g e n ee x p r e s s i o nd a t a , m i c r o a r r a y , c l u s t e r i n g ，b i c l n s t e r i n g ， g r a p hd a t a b a s e ，c h e m i c a lc o m p o u n dd a t a b a s e ，s u b g r a p hs e a r c h , g r a p hi n d e x i n g ，g r a p h s i m i l a r i t yq u e r y 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他入或其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 作者签名 论文使用授权声明 日期：塑1 笙塑! 蹋 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 作者签名导师签名 劬7 年；同9 同 1 1 研究背景 第1 章引言 生物信息学起源于8 0 年代使用计算机算法( 动态规划s m i t h w a t e r m a n 算法) 【l 】帮助进行序列比对( s e q u e n c ea l i g n m e n t ) 这一经典问题。生物信息学初始的研究 目的只是为生物学研究者提供必需的计算手段来处理实 ( w e te x p e r i m e n t ) 得到 的数据。而今，生物信息学已经发展为一门内涵非常丰富的交叉学科，其核心内 容是使用计算机科学与技术对生物学研究的实验数据管理、统计、分析并预测， 生物信息学已经渗透到现代生物学研究的各个主要领域和阶段。生物信息学研究 的典型数据包括基因组数据( d n a 、r n a 序列数据库与结构数据库) 、蛋白质组 数据、化学分子结构数据库、生物大分子结构数据库和基因表达数据等。 生物信息学在生物科学研究中占有愈加重要的地位，不仅具有支持性作用， 也在逐渐地增强其推进和指导意义。现代生物学研究中的各个主要环节都需要生 物信息学的参与，例如： 遗传学家和分子生物学家对基因组研究的必要条件就是准确的基因序列 ( d n a 、r n a 序列) 。在使用基因测序实验 2 】后得到的只是基因序列的一些片段， 这时就需要使用生物信息学工具将这些片段数据还原为正确的基因序歹l j ( 基因识 别算法【3 】、基因重组算法 4 ) 。 生物学家需要对新发现或者已有的基因做深入的研究，尤其针对基因的功 能。通常情况下，基因通过由其翻译( t r a n s l a t e ) 得到的蛋白质产物在生物体内产生 作用。在不同的生物条件下，同一个基因会产生不同的蛋白质产物从而具有不同 的功能。除了直接使用生物实验的方法来发现这些蛋白质，生物学家还可以事先 使用基因裁剪算法来预测可能的产物。准确的算法可以使生物学家集中研究于感 兴趣的基因及其特定的蛋自质产物，由此节省大量的实验成本。 蛋白质在生物体内所起到的作用主要由其空间结构决定，而蛋白质的空间结 构又由其一级结构( 蛋白质序列) 决定。因此生物学家需要准确的蛋白质空间结构 预测算法( 包括二级结构、三级结构、四级结构) 。 生物学家为了了解生物体内的生化反应路径( b i o l o g i c a lp a t h w a y ) 还必须借助 基因微阵列实验( m i c r o a r r a y ) 5 等手段来了解生物体内基因的表达和调控。而微 阵列实验得到的数据只有经过计算机技术的分析和挖掘才能提炼出生物学家感 兴趣的表达和调控模式。为了完成这个任务而引入的数据挖掘技术也成了生物信 息学乃至生物学研究的重要工具。 针对疾病找到有效的药物手段是生物学的一个重要应用研究。当生物医学家 了解了疾病的病理，就要针对须修复的生化反应路径设计具有相应功能的药物。 生物医学家需要大规模地筛选已有的数据库来寻找可能有效的化合物结构或者 替代物，同时还要考虑副作用和生产能力。整个筛选过程会占据长期的药物研发 过程加大的比重。这样高效的化合物结构搜索算法( 6 5 】可以大幅节约药物筛选【6 】 的时间和经济成本。 由这些事例可知，在整个生物学研究链中都有生物信息学的重要作用。计算 机科学研究者可以在这个仍然充满着开放性问题的新兴领域作出贡献。 目前，生物信息学的主要研究方向包括：( i ) 序列分析：主要包括序列比对、 基因识别、基因重组；( 2 ) 基因表达和蛋白质分孝斤：主要包括基因表达数据分析、 蛋白质结构的预测、蛋白质活性预测、生化反应路径、调控代谢网络；( 3 ) 生物 学理论检验和建立如进化论模型的建立、生物群落研究等。 研究者充分利用了计算机研究中已有的方法，试图解决这些问题，并根据需 要做扩展和变化。在生物信息学中常用的计算机方法和技术包括：( 1 ) 序列的搜 索、索弓 、比对算法，如b l a s t 7 1 、f a s t a 8 。这些方法在很大程度上与已有 的各种字符串算法具有共性；( 2 ) 大规模统计方法，利用高速计算能力对生物学 理论建模并检验；( 3 ) 人工智能、机器学习和数据挖掘算法，在基因表达数据分 析和蛋白质网络研究中，常见的贝叶斯网络、模式识别、分类、聚类等算法都得 到了广泛应用。( 4 ) 结构数据库索引、搜索方法：为生物学家提供了高效的检索 工具，提高工作效率。 然而这个新型学科与传统计算机科学研究相比，还具有相当不同的特点。生 物信息学中，用户往往要求能够处理海量数据。典型的基因组序列数据库包括 l o g b 量级的数据，而大型的数据库可能包含t b 级的数据，更重要的是，生物 学家的任务往往涉及到在多个数据库之间做数据查询和比较，这迸一步加大了需 要处理的数据量。大型的数据库通常包含多个不同质的数据集，这些数据集一般 采用文本文件的形式存储。数据表示内容的语法语义一般沿用生物化学惯例， 对同一内容可能会采取不同的惯例。这种做法有助于生物学家的直观认识和理 解，却不利于高效计算。除了生物学实验固有的高错误率和高噪音环境外，生物 数据库的管理方式还容易带来另一种错误。大部分生物数据库采取开放松散的组 织，数据由全世界的研究者自行提交，会发生同一内容的数据以不同的命名标 记被重复提交，却又因为不可避免的错误和嗓音不完全一致，严重影响了数据的 自动化管理。生物信息学研究中所使用的计算模型多变而复杂，由于生命过程的 复杂性，将生物学研究任务形式化为计算问题的过程需要计算机科学家和生物学 家顺畅的沟通与交流。而对于同一个问题的同样数据，生物学家可能提出不同的 2 模型以求得到不同视角的结果。这又使得相比传统计算机科学，在研究初期生物 信息学研究意图取得的计算结果不那么明确。 基于上述的原因，简单地将生物信息学问题形式化，直接套用计算机研究中 已有的算法解决会在实际应用中发生很大的困难。通常，一个新的生物信息学开 放问题需要生物学研究者和计算机研究者共同努力，不断交流修正才能提出合适 的解决方案。 在本文中，我们充分地考虑到了生物信息学的研究背景和特点，对我们的研 究内容设计合适的方法，并经过了实践的检验。 1 2 研究内容 生物学研究中一条重要的研究链是针对疾病开发出有效的药物治疗手段。这 是一个高时间、经济成本投入的研究过程，同时也需要多个领域的生物学家共同 努力。在整个研究流程的各个环节都需要生物信息学的参与：对于某个特定的疾 病，临床研究者会使用统计方法来评估各类因素对该疾病的影响和病人的生理情 况；为了在个体病患中找寻疾病可能的规律，研究者也使用了文本挖掘算法以从 病历中找到有用的信息；为了发现病理根源，生物学家需要将疾病的外在表现 症状定位到具体的可能发生病变的生物路径上。蛋白质网络以及基因表达情况是 构建完整的生物学路径的有效手段。遗传学家也需要使用基因表达数据来判断疾 病或者疾病的特定表现型( p h e n o t y p e ) 是否与特定的基因型( g e n o t y p e ) 相关。这些 工作都需要使用合适的算法来分析蛋白质交互作用和基因表达数据；如果，可以 将疾病准确地联系到特定的一些基因或者定位到具体的生物路径点上，将是生物 医学研究的重要成果，不但可以提高疾病诊断的准确率，还能够推进有效药物的 设计。之后，药理学家会根据掌握的病理知识，从庞大的数据库中筛选可能对于 发生病变的生物路径有修正作用的结构，为了加速筛选过程必须有高效的结构数 据库搜索方法。一旦可能的结构被筛选出，还会使用计算机算法来初步分析其药 理作用和毒性，才能做进一步的动物临床实验。 由此可见，整个药物设计研究过程中综合运用了多项生物信息学方法，对于 这些方法的进一步研究有着确定的实用价值。在充分考虑了现有的研究情况，可 行性和数据来源后，我们选择了基因表达数据聚类分析和分子结构数据库搜索这 两个问题作为研究对象。对这两个问题，先前的研究者已经做了不少工作，但是 仍然留下了继续探究的空阳j 和必要。同时在这两个领域内也有大量的公开数据可 供利用。 从微阵列实验技术产生之初【6 】，研究者就使用了包括聚类在内的分析手段 来找出基因表达数据中可能具有生物重要意义的模式。经过实践，研究者很快意 识到直接使用传统的聚类算法与生物模型并不完全吻合。从c h e n g 和c h u r c h 9 第一次提出了双聚类的术语( b i c l u s t e r i n g ) 开始，这一类聚类算法受到了很大的关 注。一系列的双聚类算法被设计并运用到实践中取得了良好的效果。四类主要的 双聚类簇已经得到了深入的研究。对于处理不同的聚类簇模型和不同的聚类簇结 构都有多种算法可供使用。由于计算手段的进步，充分发挥了微阵列实验技术的 威力，使得该实验受到更大的重视而迅速普及，研究者陆续发布了大量重要的实 验数据。现今，一些研究者已经开始通过合力感兴趣的领域建立大规模的并且充 分记录了己取得的知识的基因表达数据库。同时，聚类的计算工作也逐渐从设计 高效的新方法转向如何正确地使用领域知识来验证所得到的聚类簇确实能够抓 住生物学重要的模式并且帮助生物学家推断出有意义的信息。 本文关注于新型的基因样本时间微阵列数据的聚类分析。这种三维聚类可 以视为双聚类的进一步拓展，又具有更高的复杂度。为了发挥这种新型微阵列数 据的优势，研究者需要高效而又能抓住表达模式的整体变化趋势的聚类算法。目 前已知的最好的工作是通过加入加法模型或者乘法模型的强制对称性，使搜索过 程在维度较小的方向上进行从而提高时间效率。但是这种方法牺牲了一部分发现 具有生物学意义模式的能力。因此，仍然需要有更好的解决方案，本文在这个问 题上做了一些初步的探索。 本文的第二个研究工作是分子结构数据库搜索技术。分子结构数据库实际上 以一个图数据库的形式存储，因此这个问题与目前数据库社区的研究热点：大规 模图数据库( 包括使用树建模的x m l 数据库) 有着紧密的联系。分子结构数据库 搜索的难点在于子图同构问题和在实际应用中需要的相似性子结构搜索。子图同 构使德搜索具有相当高的复杂度。而相似性子结构搜索更令原有的算法和技术不 能很好地解决这类问题。我们受领域知识和已有研究的启发，构建高效的索引来 针对查询过滤图数据库，使复杂的子图同构匹配只需在一小部分候选集上执行。 我们的方法和一些已有的研究具有相似的基本思想，但是就我们所知，这个研究 是第一个将应用领域的学科知识语义记录在字符串索引的工作。 1 3 本文结构 引言简要介绍了本文的两个工作的大背景一生物信息学和其在整个生物学 研究链中的作用。 第二部分将综述在基因表达数据聚类分祈和分子结构数据库搜索技术已有 的相关工作。 4 第三部分详细介绍我们提出的三维基因表达数据聚类算法g t r i c l u s t e r 和实验结果。 第四部分详细介绍我们提出的新的分子结构数据库搜索算法g s t f i n g 和实验 结果。 第五部分展示了g s m n g 的原型系统。 第六部分对我们所做的工作做总结，并展望未来的研究方向。 2 1 概述 第2 章相关工作 如引言中所述，本文的研究工作，基因表达数据聚类和分子结构数据库搜索 在整个生物学研究环节中有重要作用，同时也是生物信息学研究中的热点问题。 生物信息学发展至今，各个领域尤其是数据库社区的研究者都在这两大类问题上 已经进行了深入研究。从最早期的直到最近的研究工作不仅覆盖了这两类问题的 许多方面，同时也为后来的研究者提供了成熟的视角、思想和方法。 我们通过阅读先前研究者的文献，详细地了解这两大类问题的起源、发展和 现状。我们仔细地研究了前人的工作，得到了许多认识和启发，同时分析了问题 现有的空白点以及已有方法的优势或者不足。在此基础上，我们开始了在这两个 问题上的探索。在研究过程中，我们提出并实践了创新的思想和方法，并继续跟 踪最新的研究文献，通过比较验证了我们的研究成果。 在这一章中，我们汇总了前人在这大类问题上优秀的工作，多方位地介绍所 研究的问题。我们按照应用领域，基本思想，所用方法等方面分析前人的工作， 指出其中给予我们思考和启发的亮点，并做了总结和评价。 本章的组织结构如下：第一节概述本章的主要内容和目的。第二节介绍基因 聚类表达数据聚类相关工作的现状。第三节我们汇总了与分子结构数据库搜索相 关的各项工作。第四部分小结。 2 2 基因表达数据聚类研究现状 在本小节中，我们首先概述基因表达数据聚类。然后重点讨论在该问题上得 到最普遍应用和研究的双聚类方法，接着概括在基因一样本一时间微阵列数据上 做三维聚类问题的初期工作。 2 2 1 基因表达数据聚类问题概述 在基因表达数据聚类这类问题上，本文的研究工作主要集中在新型的基因一 样本时间微阵列数据的三维聚类上。然而，这个问题与先前的研究者在传统基 因表达数据上所做的聚类工作有着很深的联系，可以视为从最初使用聚类框架到 目前普遍使用的双聚类( b i c l u s t e r i n g ) 框架的研究过程的进一步扩展。同时，三维 聚类这个问题也和一些已有的双聚类算法有着思想、方法上的密切联系。因此， 6 本小节阐述基因表达数据聚类问题的定义和应用意义。 d n a 芯片微阵列实验和其它的技术可以同时测量大量基因( 可能是某个生 物组织包含的全部基因) 在多个不同实验样本上的表达水平。实验样本可能对应 与不同的时间点或者不同的环境条件。在另一类情况下，样本可能来自不同的生 物组织( 癌化组织或者健康组织) 、甚至于来自不同的生物个体。将得到的基因表 达数据( 简称表达数据) 可视化是具有挑战性的工作，而从基因表达数据中抽取出 生物学相关的知识就更加困难。 通常，基因表达数据被安排成矩阵形式，每一个基因对应于一行，每一个条 件对应于- - y u 。这个矩阵中的每一个单元格表示某个基因在一个特定条件下的表 达水平，记录着一个实数值，一般是这个基因在特定条件下m r n a 的相对富集 度( r e l a t i v ea b u n d a n c e ) 的对数。研究者在两个维度：基因维度和条件维度上详细 分析了基因表达矩阵。研究者通过比较矩阵的行来分析基因的表达模式，或者比 较矩阵的列来分析样本的表达模式。 分析基因表达数据的通常目的包括： a ) 根据基因在多个条件上的表达水平对其分组。 b ) 给定已知分类的其他基因的表达水平，对一个新基因分类。 c ) 根据多个基因的表达水平，对条件分组。 d ) 根据一组基因在该实验条件下的表达水平，对一个新的样本分类。 聚类技术可以用于分组基因或条件，因此可以直接应用于上述的任务a 和b ， 也可以间接地用于任务c 和d 。在基因表达数据出现之后，研究者立即使用了传 统的聚类算法来作分析【1 0 3 】。 2 2 2 基因表达数据双聚类问题定义 但是，直接对基因表达数据应用数据挖掘领域已有的聚类算法遇到了很大困 难。许多重要的活性模式对于一组基因来说，只在特定条件下是共通的。事实上， 基于对细胞过程的一般性认识，研究者认为只有一个基因子集在一部分特定实验 条件下呈现共同调控( c o r e g u l a t e d ) 和共同表达( c o e x p r e s s e d ) 现象，但是这个子集中 的基因在其它条件下的表达几乎呈相互独立的关系。发现这种局部的表达模式可 能是揭开许多隐藏的遗传路径的关键。因此，在这个领域非常需要超越数据挖掘 中已有的聚类框架，发展出能够发现微阵列表达数据中的局部模式的新方法 【1 0 】e 双聚类b i e l u s t e r i n g 这一术语最早由c h e n g 和c h u r c h 9 使用在基因表达数据 分析上。双聚类是指一类与已有聚类算法不同的同时执行行列聚类的聚类算法。 双聚类算法在其它的领域也有应用。在文献中使用了双聚类的多个别名( 共聚类 c o c l u s t e r i n g 二维聚类b i d i m e n s i o n a lc l u s t e r i n g 和子空间聚类s u b s p a c ec l u s t e r i n g ) 7 来指称相同的问题形式。一个最早期的双聚类形式是由h a r t i g a n 提出的直接聚类 算法( d i r e c tc l u s t e r i n g ) 1l l ，也被称作区块聚类( b l o c kc l u s t e r i n g ) 1 2 。 双聚类与传统聚类的不同之处在于：聚类可以单独地用于行或者列，而双聚 类则同时在行列两个维度上做聚类。这意味着聚类产生的是全局模型而双聚类产 生局部模型。当使用聚类算法时，一个给定的基因簇中的每一个基因都是在所有 的条件上定义。相似的，一个条件簇中的每一个条件也是定义在所有基因的活性 上。但是，一个双聚类簇中的每一个基因是只使用一都分条件( 所有条件的一个 子集) 来选择的。同样的，双聚类簇在中的每一个条件也是只使用一部分基因选 择出来的。双聚类技术的目标是通过同时对基因表达数据矩阵的行列进行聚类来 识别基因的子集和条件的子集。我们可以得出结论双：聚类算法识别出一组在特 定实验条件子集上呈现相似活性模式的基因。因此，双聚类方法在以下多种情况 作为关键技术被应用： a ) 只有一部分基因参与到研究者感兴趣的细胞过程中 b ) 研究者感兴趣的细胞过程只在一部分条件下具有活性 c ) 一个基因可能参与多个生物路径但是可能不是在所有的条件下都具有共 同活性 基于以上的理由，使用双聚类来识别基因和条件组，需要遵循以下限制 a ) 一个基因簇应当被定义在一个条件子集上 b ) 一个条件簇应当被定义在一个基因子集上 c ) 聚类簇不能是排斥的或者穷尽的：一个基因或者条件可以属于多个聚类 簇或者不属于任何一个聚类簇，而且是使用条件或者基因的一个子集分 组 另外，由于在实际的基因表达实验中固有的高噪音性，鲁捧性也是双聚类算 法特别需要关注的问题。 大部分的双聚类算法应用在处理基因表达数据矩阵上，不过，也有许多双聚 类在其他领域的应用。因此，我们考虑一个通用形式的数据矩阵，a ，有一个行 集合x = ， 和一个列集合y = y ，j ，。 ，矩阵中的每个单元格口。对应于 一个表示行i 和列，之蒯关系的值。我们使用k 的来指明矩阵一。考虑i x 和 j 工分别是行和列的子集，4 。，= ( ，) 表示4 中由行子集合，和列子集和，组 成的子矩阵。 如上定义，给定一个数据矩阵a ，我们定义一个行聚类簇为在列全集上显现 了相似行为的一个行子集合。即，一个行聚类簇a 。= ( ，y ) 是定义在列全集】，上 8 的行子集合，= i i 7 0o ，( ，x ，七斤) 。由此，行聚类簇( l d 被定义为矩阵4 的一个m 的子矩阵。 相似的，一个列聚类簇是在行全集上显现了相似行为的一个列子集合。一个 列子集合a 。= ( x ，j ) 是定义在行全集上的列子集合， j = ，工) ，( ，cy ，5 m ) 。列聚类簇( l 力被定义为矩阵a 的一个n x s 的子 矩阵。 而双聚类簇( b i c l u s t e r ) 是在某个列子集上显现相似行为的一个行子集，或者 相反。由此，双聚类簇如= ( ，j ) 是一个行子集和列子集， i = ，t ，( ，x ，k s 胛) ，j = ，工) ，( ，y ，j m ) 。双聚类簇j ) 被定义为 矩阵a 的一个s 的子矩阵。 由上，我们可以定义双聚类算法要解决的问题。给定一个数据矩阵4 ，双聚 类算法的目标是识别一组双聚类簇鼠= ( ，以) ，这其中每个双聚类簇尾都满足 某个特定的一致性，相似性特点。而一致性湘似性特点的定义会随着应用的不同 而有所变化。 研究者发现数据矩阵和图论有着一些有趣的联系。一个数据矩阵也可以被视 为一个加权二分图( w e i g h t e d b i p a r t i t e g r a p h ) 。有图g = ，e ) ，v 是一组顶点集合， 而e 是边集合。如果图的顶点可以被分为两个集合三和r ，满足e 中的每条边 的两个顶点分别属于上和r ，那么图g 被称为一个二分图。而数据矩阵a = ( 爿，y ) 和二分图存在如下的映射：工中的顶点对应于矩阵每一列，r 中的顶点对应于 矩阵中每一行，边的权重表示行i 和列，交叉得到的单元格的值( 在基因表达矩阵 中就是活性水平的强度) 。矩阵和图论这种映射关系的存在导致产生一些非常有 趣的基于图算法的表达数据分析方法。 尽管双聚类问题的复杂度可能取决于特定的问题形式，特别是用于评估一个 双聚类簇的质量的度量函数。但是几乎所有有意义的双聚类变种问题都是 n p c o m p l e t e 。数据矩阵a 的最简单形式就是一个0 1 矩阵，每个单元格口。为0 或l 。在这种情况下，一个双聚类簇对应于数据矩阵映射得到的二分图的一个双 团。由此，找最大双聚类簇的问题等价于在二分图中找寻最大边双团( m a x i m i l l e d g eb i c l i q u e ) f 司题，该问题被证明为一个n p - c o m p l e t e 问题i t 3 。当矩阵4 中使 用实际数值来计算双聚类簇的质量是，复杂度将会更加高。因此，大部分双聚类 9 算法都使用启发式的方法来识别双聚类簇，而且在许多情况下会经过一个预处理 过程( 如归一化步骤) 使感兴趣的模式更加明显。而其他不使用启发式方法的在最 差情况下必然会呈现指数级的复杂度。 2 2 3 双聚类算法类型分析 评价双聚类算法的最重要标准是该算法能够识别的双聚类簇种类，据此已有 的研究工作一般可以分为以下四类： a ) 常数型双聚类 b ) 行或者列常数型双聚类 c ) 一致数值型双聚类 d ) 一致变化趋势型双聚类 前三类直接分析数据矩阵中的数值，试图找到具有相似行为的行子集合和列 子集合。这些相似行为可以表现在行上，列上或者数据矩阵的两个维度上。第四 类双聚类算法的目标是发现一致性型的变化趋势而不考虑数据矩阵中的绝对数 值。因此，一致变化趋势型双聚类将数据矩阵的单元格视做符号。这些符号可能 是名字，也可能对应于给定的次序，或者表示相对于一个正常值豹正向或者负向 的一致性变化。 在基因表达数据中，常数型双聚类簇显示了在条件子集上具有相似表达值的 基因子集。行常数型双聚类簇识别在一个条件子集上具有相似表达值的基因子 集，但是允许基因与基因之间的表达值有所不同。相似的，一个列常数型双聚类 簇识别在一个基因子集上呈现相似值的一个条件子集，而假设条件与条件之间的 表达值不同。但是，用户可能对基因和条件之间更复杂的关系感兴趣。这样，一 致数值型双聚类簇识别在行和列上具有一致表达值的一个基因子集和一个条件 子集。另一方面，用户感兴趣的是在找到一个条件子集上共同上调控( u p r e g u l a t e d ) 或者下调控( d o w r t r e g u l a t e d ) 的一个基因子集，而不考虑这些基因的准确表达数 值。或者用户希望识别在一个基因子集上始终具有相同或者相反的一个条件子 集。在这些应用中，识别一致变化趋势型双聚类簇就变得很有帮助。 根据每个问题的特定属性，研究者关注于不同种类的双聚类簇，并使用不同 的度量函数来评估被识别的双聚类簇的质量。这些度量函数的选择和每种聚类算 法希望找到的聚类簇特性密切相关。在具体做法上，大多数的双聚类算法同时在 数据矩阵的两个维度上聚类来找到上述四种双聚类簇。而一些两路( t w o w a y ) 聚 类算法则先在数据矩阵的两个维度上单独聚类，然后再将所取得的一维结果合并 得到行和列的子集作为最终的双聚类结果。这些方法的结果依赖于一维聚类算法 所使用的距离或者相似性度量函数。我们在基因样本时间微阵列数据上也使用 了相似的思想，来寻找最大一致三维聚类簇。 o 在逐个介绍一些重要的聚类算法前，我们引入一些基本记法以方便之后的叙 述和比较。给定矩阵a = ( z ，y ) ，x 为行集合，y 为列集合。，是x 的子集，是 y 的子集，一个双聚类簇是由，和，组成的子矩阵【，力。口。是矩阵a 的i 行_ ，列 的单元格。我们定义叼为双聚类中第i 行的平均值，吼为双聚类中第，列的平 均值，而是双聚类中所有单元格的平均值：2 南吾嘞，嘞2 南荨， 2 南，勋”，2 高善2 南苫嘞。 当一个双聚类算法的目标是找到一个或多个常数型双聚类簇时，很自然地会 考虑重排行和列，使相似的行和相似的列聚集在一起的方法来发现具有相似数值 的双聚类簇。但是这样的方法只能在无噪音的数据上取得良好的效果( 但是大多 数可用的数据都有噪音) ，因此需要更加成熟的法案以达到寻找常数型双聚类的 目的。 一个完美的常数型双聚类簇是这样的子矩阵( ，力：对于所有的i ，和， 的值都相等，日。= 。尽管在某些数据矩阵中能够找到这样“理想”的双聚类簇， 但一般常数型双聚类簇会被嗓音掩盖。这就意味着被视为一个常数型双聚类簇的 值口。通常会呈现仉+ 的形式，即在1 的基础上加上一个噪音巩。因此，研究 者通常使用方差作为评估常数型双聚类簇的度量函数。 h a r t i g a n i1 提出了一个称为d i r e c tc l u s t e r i n g 的基于划分的算法，该算法也被 称作b l o c kc l u s t e r i n g 。这个算法将原始的数据矩阵分为子矩阵( 双聚类簇) 的集合， 并使用方差来评估每个双聚类簇( ，j ) 的质量：v , 4 r f f ，) = ( 嘞一a u ) 2 i ，, j e j 根据这个标准，一个完美的双聚类簇是一个方差为0 的子矩阵。因此，数据 矩阵中的每个单行单列矩阵( ，d ，即是每个单元格都是一个理想的双聚类簇。 为了避免将数据矩阵划分为单列单行的双聚类簇。h a r t i g a n 假设数据矩阵中共有 足个双聚类簇。可以看到这种算法深受经典聚类算法k - m e a n s 的影响，同样也引 入了相似的缺点：用户难以实现确定聚类簇的数目。当数据矩阵被划分为置个 f 2 v a r u ，) 。= ( - - a 。) t = 、岖 i “ 双聚类簇时，算法就停止。而结果的质量使用这k 个双聚类簇全局方差( o v e r a l l v a r i a n c e ) 来计算： t i b s h i r a n i 等人【1 4 】对h a r t i g a n 提出的区块划分算法加入了后退剪枝方法，该 算法仍然使用和b l o c kc l u s t e r i n g 相同的衡量函数。但是，t i b s h i r a n i 等人设计了 一种基于排列的方法来推导出最有的双聚类簇数e 有效地克服了h a r t i g a n 算法 的缺点。 一个完美的行常数型双聚类簇是一个子矩阵( j ，d ，其中所有的值可以使用 如下的表达式得到：( 1 ) a 。= + a ，或( 2 ) 口。= x 口，声是双聚类簇的基本值，而 a 。实在行i 上的调整。这个调整可以是加法形式如同表达式( 1 ) ，也可以是乘法形 式如同表达式( 2 ) 。完美的列常数型双聚类簇具有与上述相似的形式。 这种的双聚类簇不能通过简单地计算值的方差或者计算行和列之间的相似 性来找出。最直接的方法是分别使用行和列的平均值将矩阵归一化。g e t z 等人【1 5 1 使用了简单归一化方法的变种来预处理数据。如果使用相对复杂的归一化方法就 可以使他们的算法不仅能够挖掘行列常数型双聚类簇，还可以迸一步扩展到一 致数值型双聚类簇。 其他研究者提出了不使用归一化方法的双聚类算法。这些方法考虑到了真实 数据中的噪音，允许寻找不完美的行列常数型双聚类簇。s h e n g 等人 1 6 在贝叶 斯框架下解决双聚类问题。他们使用g i b b s 采样的方法得到参数期望值，提出了 一套基于双聚类簇模式的频繁模型的策略。他们的方法不仅找到了行和列的集 合，并使用双聚类簇每一列下的每一个离散值的后验频繁度作为双聚类簇模式表 示的概率模型。他们使用多项式分布来建模每列数据，假设双聚类簇内每列的多 项式分布是独立无关的。s h e n g 等人假设数据矩阵的方向为行到列，检验对于每 一列，双聚类簇内的值是否在行上一致。通过这样的做法，他们能够识别列常数 型双聚类簇。以列到行的方向使用相同的方法，就能识别出行常数型双聚类簇。 s e g a l 等人【1 7 】提出了一个基于概率关系模型( p r m ) 的方法。该方法使用基因 和条件作为独立对象将b a y e s i a n 网络拓展为一个关系设置。通过这个方法，s e g a l 等人也能发现行常数型双聚类簇。不过，他们的方法可以对基因条件特定属性 上的表达水平依赖性建模，而更加通用。通过正确地推导出表达水平和基因( 或 者条件) 之间依赖性，他们的方法可以优化比前述表达式更为普遍的表达式来对 双聚类簇建模。更进一步，s e g a l 等人考虑了如何使用c p d t r e e ( c o n d i t i o n p r o b a b i l i t yd i s t r i b u t i o n t r e e ) 从多个可能的p r m 中作出选择。他们使用了一个评