基因芯片技术是近年来分子生物学领域的一大技术突破,它可以平行检测数以万计基因的表达水平,从而获得不同条件下基因组水平的基因表达数据。然而面对迅速增长的数据,如何借助有效的计算方法对海量数据进行分析成为了新的挑战。本文主要研究的就是如何针对基因表达数据设计双聚类算法,从而在表达数据中寻找趋势一致双聚类,即那些在特定条件下具有趋势一致表达的基因集。通过对基因表达数据的研究,有助于分析基因的表达调控信息,了解基因之间的相关性,对疾病诊断治疗、药物疗效判断等方面具有十分重要的意义。最早的研究基因表达数据的方法是利用单聚类算法分别对基因或条件进行分析。其结果反映的往往是一组基因在全部条件下,或全部基因在某些条件下表达的相关性。然而在生物体内,参与同一调控功能的仅仅是一部分基因,且它们只在部分条件下具有表达相关性。同时,许多基因通常具有多种调控功能,可能会在不同的条件下表现出不同的功能。因此在基因表达数据的分析中,我们需要的是能够反映部分基因在部分条件下表达相关性的双聚类,同时允许不同的双聚类之间会存在一定程度的覆盖,而这些数据特征都是采用传统的单聚类算法难以获得的。双聚类算法的提出为基因表达数据的分析提供了有效的方法,使得我们可以找到在特定条件下具有一致表达类型的基因集。双聚类算法最初由Morgan等人提出,他们将矩阵分解为值近似相等的子矩阵。随着双聚类算法被应用到基因表达数据的分析中,大量针对不同类型双聚类的算法涌现出来,并对基因表达数据的分析起了重要的作用。趋势一致双聚类是隐藏在基因表达数据中最具有生物意义的一种双聚类类型,目前也有很多算法是针对此类型双聚类设计的。但是由于问题本身的复杂性,如何快速有效地识别数据中的趋势一致双聚类仍然是一大难题。本文中,我们提出了一种新的双聚类算法UniBic,它可以准确地识别矩阵数据中的趋势一致双聚类。算法的设计基于如下发现：在顺序一致的双聚类中,存在一个列的重排列,使得各行元素值在该重排列下是非降序排列的,且识别双聚类的关键就在于准确定位双聚类所在的列。UniBic的设计主要分为以下几步：首先,根据原始矩阵创建数据的索引矩阵,并根据所要寻找的双聚类的显著性信息将索引矩阵分组：随后,将最长公共子序列方法运用到索引矩阵每一分组的行对之间,以定位可以用来进一步扩增双聚类的种子序列；最后,将种子扩增为严格顺序一致的双聚类,并在允许误差存在时将严格顺序一致的双聚类扩增为趋势一致双聚类。索引矩阵的建立将在背景矩阵中寻找趋势一致双聚类的问题转化为在索引矩阵的行对之间寻找最长公共子序列的问题,使得原问题不那么棘手。此外,在处理如基因表达数据等的大规模矩阵数据时,我们通过对数据进行预处理,选择出起调控作用的部分数据进行分析,从而有效地减少了冗余数据及噪音数据对结果造成的影响。我们分别在模拟数据及真实数据上对比了UniBic与其余六种算法的性能。在不同类型的模拟数据上的测试结果表明,当嵌入的双聚类具有一定列数支持时,UniBic的表现明显优于其余所有算法,特别地,UniBic能够有效识别模拟矩阵数据中嵌入的趋势一致双聚类。同时,当模拟数据中嵌入的双聚类之间存在一定覆盖度时,UniBic的表现也优于其它算法。在真实数据的测试中,UniBic得到的结果也是平均GO富集度最高的。但我们的算法仍有不足之处,由于种子是从索引矩阵行对之间的最长公共子序列中寻找的,UniBic在一定程度上会忽略列数较少的窄形双聚类。目前已有算法是专门针对数据中的窄形双聚类设计的,但是此类型的算法不但时间复杂度普遍较高,而且当双聚类列数较多时表现十分不理想。考虑到双聚类算法的复杂性,我们很难设计一种算法来高效地寻找所有类型的双聚类,不过我们提出了一种可行的方法来弥补现有算法的不足,并作为后续的研究课题。文章的最后我们介绍了一个简单的聚类算法Peg,并在梭状芽孢杆菌基因组数据中将其与层次聚类算法进行对比。结果表明我们的算法可以较好地反映基因组的分组状态。UniBic已用C语言实现为开源软件,下载地址为：http://sourceforge.net/projects/unibic/files/?source=navbar.本文所用测试数据及测试结果也可从该地址下载。