文摘

保序子矩阵(OPSMs)已经应用在许多领域,如DNA微阵列数据分析,自动推荐系统,和目标市场营销系统,作为一种重要的非监督学习模型。不幸的是,大多数现有的方法是启发式算法无法揭示OPSMs完全np完全问题。特别是深OPSMs,对应于长模式很少有支持序列,产生爆炸计算成本和完全修剪最受欢迎的方法。在本文中,我们提出一个精确的方法来发现所有OPSMs基于频繁序列模式挖掘。首先,现有的算法调整披露所有公共子序列(ACS)每两行之间的序列,因此所有深OPSMs不会错过了。然后,一种改进的使用前缀树的数据结构来存储和遍历ACS,和先验的原则来有效地挖掘频繁序列模式。最后,实验上实现基因和合成数据集。结果证明了该方法的有效性和效率。

1。介绍

最近许多高通量DNA芯片的发展产生巨大的基因表达的结果,表示为矩阵实数的行(对象)来表示基因和列(属性)来表示不同的环境条件,不同的器官,甚至不同的个体。每个元素或条目代表一个特定条件下基因的表达水平。

分析基因表达数据聚类被广泛用于收集到不同的集群基于相似的对象。在同一集群的对象尽可能相似。基因在同一集群可能显示细胞功能或表达模式相似,这意味着他们更有可能参与相同的细胞过程。相似度测量主要是基于距离函数,包括欧氏距离和曼哈顿距离。然而,这些不适当的测量距离函数对象相关的基因矩阵(1]。此外,只有一小部分基因参与任何感兴趣的细胞过程,和细胞过程只发生在样品的一个子集,需要biclustering或捕获的子空间聚类簇形成的基因在样品的一个子集的一个子集2]。

表1显示了一个示例的原始5×6数据矩阵和相应的图如图1(一)。如果所有的行或列被认为是,然后共同模式不能被发现。然而,如果被认为是前五列,然后第二,第三,第四行显示同样的趋势在这五个列,如图1 (b)。

基因表达分析的问题尤其如此,因为基因表达矩阵通常有很高的尺寸(1]。然而,传统的聚类等——(3和层次聚类4很难用确定这些子集。鉴于这种观察对高维数据集,这些嵌入集群吸引广泛关注近年来(5- - - - - -7),和许多biclustering算法已经提出解决这个问题(8- - - - - -11]。其中,基于模式的子空间聚类,这是基于模式相似而不是相似的距离,已被广泛应用于基因表达分析、推荐系统、目标销售,等等。

典型的微阵列数据有时有高水平的噪音。Coregulation基因不一定有相同的绝对的表达水平。所以做一个比较不同的基因在不同的实验中,相对表达水平比他们的绝对值更有意义。有趣的生物知识通常隐藏在基因,这显示了类似的模式在不同的实验条件(上升和下降)。

本文基于模式的子空间聚类,也称为保序子矩阵(OPSM)模型。一个非连续的子矩阵是OPSM提供列排列存在,这样所有的子矩阵的行中的值严格单调递增。元素之间的趋势更重要比实际值模型。图2显示列新秩序下的序列是单调递增鉴于列排列。在生物学领域,OPSM模型已被接受作为一个生物意义的集群模型。此外,该模型还可以用于业务预测。例如,客户分为几大类根据电信客户评分关税包。属于同一类的客户有相同的需要互联网连接和浏览速度等。市场经理可以为不同的客户设计不同的市场策略组基于结果。

如果每一行向量与列的升序排序指标替换原有的价值,那么原始矩阵转换成数据组序列和OPSM挖掘问题简化为一个特例的频繁序列模式挖掘12]。频繁序列模式是唯一地定义为OPSM与所有支持序列行。一个序列的长度模式所包含的列数。支持计数是包含序列的行数。的顺序模式支持计数超出最小支持度阈值,分吃晚饭,也被称为频繁序列模式。因此,重要的数据挖掘问题OPSM相当于寻找成套频繁序列模式。

大多数现有的序列模式挖掘方法依赖于缩小搜索空间设置最小支持度阈值的方法。鉴于小支持阈值将导致爆炸性增长的计算成本,大多数现有的方法提高算法的效率,通过设置一个相对较大的阈值。然而,大找不到深OPSM支持阈值。深OPSM长模式的概念和小支持行数首次提出了高et al。12]。深OPSMs重要生物学家,因为他们的基因可能代表小组紧密coregulated在某些条件。在一些重要的生物过程,如蛋白质相互作用,和生物通路成员,只有数量有限的基因是参与这些过程。然而,一般的频繁序列模式挖掘算法通常忽略这种OPSMs。

解决上述问题,本文首先将OPSM转换成频繁序列模式,然后一个精确的算法搜索OPSMs基于频繁的公共子序列挖掘。它可以我所有OPSMs嵌入在一个给定的矩阵和为行和列支持提供的灵活性,它允许深OPSMs的发现。

提出一种算法calACS小王和林13)是改善来确定两个序列之间的所有常见的子序列。然后,介绍了先验的规则来缩小搜索空间,和前缀树构建存储和遍历序列模式来降低时间和空间复杂度。最后,所有OPSMs满足定义的阈值。在我们的算法中,计算成本不会增加巨大即使阈值的值非常小。

本文的其余部分组织如下。节2,我们回顾一些相关的工作。部分3定义OPSM。部分4描述了算法和数据结构。部分5实验结果报告。部分6总结了纸。

2。相关工作

子空间聚类确定嵌入集群在高维数据集。哈14)首次提出集群同时行和列。程和教堂15应用它对知识发现基因的表达数据。该方法克服了传统聚类方法的缺点,允许同时聚类的基因和条件。如果子矩阵的均方误差小于,然后子矩阵是一个bicluster。一个贪婪算法来搜索子矩阵均方误差较低的基因表达矩阵,biclusters是一致的。这些子矩阵来确定coregulation模式基因表现良好和属性(15]。

Ben-Dor et al。16)首次提出OPSM挖掘模型,开门入口的相对价值,而不是实际的价值。OPSM本质上是一种基于模式的子空间聚类。的子集矩阵OPSM当每一行的值是严格增加或减少在列排列。他们证明,提出的问题是np难和矿业OPSM贪婪启发式算法。该算法可以挖掘一些OPSMs大行支持,但不能保证所有OPSMs可以发现。

张等人。1)提出了一个最大OPSM模型,将OPSM问题转化为一个序列模式挖掘的问题。我所有与候选人最大OPSMs generation-and-test框架,一个新的数据结构树首尾相接。然而,他们的算法是基于先验的原则,因此最大的数量OPSMs受支持行阈值,从而增加与数据库的大小比例。

高et al。12)提出了一种新的模型也称为深OPSM,指长一些支持序列模式。深OPSMs具有生物学意义。提出了一个框架猕猴桃有效开采深度OPSMs大规模数据集。两个参数和被利用绑定现有计算资源并确定尽可能多的深OPSMs。然而,启发式算法,不能保证所有深OPSMs的发现。

3所示。OPSM问题

在本节中,我们定义OPSM和详细的过程将OPSM转换为挖掘频繁的公共子序列的问题。

考虑数据矩阵,在那里行设置和吗列设置在吗。条目的行标签是吗和列标签。一个集群的子矩阵,在那里是的一个子集行和是的一个子集列。行和列不需要是连续的。

定义1。余子式OPSM如果存在一个排列的。每一行的条目严格单调递增。例如,表1显示一个5×6矩阵。如果行2、3和4在增加来,然后()是OPSM。基本目标是找到所有重要OPSMs在给定的数据矩阵。

在数据预处理,每一行是一个升序排序,和值取代了原来的列标签。然后,原始矩阵转化为序列的数据集。表的原始数据矩阵1被修改的数据集序列见表2。如果连续两个条目的值是相同的,然后出现之前的一个放置在前面。时频繁序列模式的支持,大于一个预定义的序列最小支持度阈值的最小一口。因此,OPSM采矿问题可以简化为一个特例的频繁序列模式挖掘。独特的频繁序列模式定义OPSM,序列模式是由OPSM列,和支持序列包括OPSM的行。

大多数现有的序列模式挖掘方法搜索OPSMs找到所有的序列支持大于给定的最小支持度阈值。挖掘算法的效率是非常敏感的最小支持度阈值。一个较大的阈值采用缩小搜索空间,降低算法的复杂性,因为一个小阈值导致的高成本计算。然而,这种方法忽略了一些统计和生物重大OPSMs OPSMs深处。深OPSMs OPSMs相对更多的列和行更少,不能有效地发现传统方法(12]。

为了解决这个问题,本文提出了一种新的精确算法。的第一步是确定所有常见序列中的每个两行数据集形成候选模式任意长度的支持至少是2。然后,数据库扫描计算行支持候选模式的长度是2找出所有的频繁序列模式长度为2。第三步是前缀树构造和存储频繁序列模式(2)长度。第四步是遍历前缀树和插入节点分支基于先验的原则和计算支持再次获得频繁序列模式的长度是3。迭代算法运行,直到所有OPSMs能找到满足最小支持度阈值的方法。在这个过程中,如果更大支持阈值是不习惯修剪,那么结果将包含所有OPSMs深处。

4所示。算法

4.1。所有常见的子序列

所有公共子序列(ACS) (17是传统的最长公共子序列的变异(LCS)。LCS是一个经典问题的目标来确定LCS的序列(通常两个序列)。王(17]提出这种新方法来计算两个序列之间的相似性。不同于之前的LCS的方法,该方法基于所有常见的数量计算相似度两个序列之间的序列。calACS [13)是一种新的方法来计算之间的ACS序列的数量和。我们改进calACS获得两个序列之间的所有常见的子序列。改进calACS算法的伪代码显示为算法1。

伪代码所示,商店是元素的公共子序列(第6行)。只要公共子序列中的任何两个项目仍在同一顺序序列和,对于任何如果项目在序列条目之前安排,同样的顺序序列保留(第17行)。因此,公共子序列的结局必须包含公共子序列的结局。他们融合在一起形成新的共同序列和所有的公共子序列和的联盟(第18行)。

我们用一个前缀树来存储和遍历所有常见的序列。不同的传统方法解决OPSM问题,频繁的公共子序列可以通过遍历频繁前缀树而不是列。

前缀树,也被称为单词查找树是有序树用于存储字符串或关联数组,从根到叶节点的路径。根节点为空对应一个空序列。普通节点存储列指数和叶节点保留行指标,支持分支(一个分支是一种常见的子序列)。序列组成节点被称为序列如图4。一个正确的道路树和叶子节点保存这个号码。也就是说,行3,4,5公共子序列。

假设一套完整的ACS,等。代表的行标签和。是元素和公共子序列的长度,表明是有序的。我们插入序列到前缀树的路径并记录在叶节点支持序列。

传统方法构造一个前缀树是描述在随后的段落。

首先,我们由前序遍历前缀树。如果第一个前缀长度序列长度是一样的前缀树中的路径节点将被添加到前尾叶节点的路径。的长度序列是不同的长度序列,相应的叶节点将修订,并将讲述行获得长度的支持路径。

然而,如果数据集高维度和非常密集12),然后前缀树将成为巨大的新序列添加时占据一个巨大的空间。遍历和交叉操作也耗时。因此,减少了计算复杂度是必要的。在本文中,我们开发两种前缀树,即候选人和频繁树,保存候选频繁序列模式,使用先验的原则来缩小搜索空间的模式。

根据先验的原则,如果一个长度序列是频繁的,那么所有的必须频繁子序列;换句话说,如果一个长度序列长度子序列不频繁,那么长不能频繁序列。因此,如果长度子序列是由第一个项目的长度序列不是频繁树中的一个分支,长度序列不应该插入到候选树。

节4.1获得ACS calACS介绍,任何两个序列之间。公共子序列长度为2是用来生成2-candidate前缀树。2-candidate树构造与每个路径保留通过遍历和插入列指标,和所有的叶子节点存储相应的支持行指标,以及支持的行数。此外,我们使用的支持行数来确定(即一个分支。,一个路径)是频繁。如果分支满足支持阈值(分钟吃晚饭),保存;否则,它是修剪。毕竟执行删除操作,2-frequent树,这是第一次迭代。

下一步是添加公共子序列长度为3的2-frequent树。这个过程如下。

前序遍历2-frequent树。如果前两个的前缀长度3公共子序列是一样的一个分支在2-frequent树,然后第三个节点添加到尾部的树枝和叶子节点同时更新,恢复支持行指数和叙述的行数。

相比之下,如果前两个前缀长度3公共子序列不匹配任何路径2-frequent树,根据先验的原则,然后3公共子序列长度不能频繁,不应作为路径添加前缀树。这个过程减少了不必要的遍历和比较序列,这是非常耗时的在一个大前缀树。此后,我们获得3-candidate树。树修剪罕见的分支后,经常是收购。

重复上面的过程来生成候选人的树频繁的树。修剪树枝来获取不满足最小支持度阈值的方法频繁树,每个路径或分支是一个频繁序列。这个项目不是终止,直到访问长度最长公共子序列。最终结果是一个树的最长路径满足支持。每条路径中的节点表示列指标,和每个叶节点的路径存储相应的行索引。因此,所有可以找到OPSMs。

我们算法的流程图如图3。

4.2。一个例子找到ACS

给定一个初始数据矩阵,在那里代表了基因的表达水平条件下一个矩阵,如表所示3。当矩阵中的每一行在一个升序排序和它们的值替换为相应的列索引,矩阵被替换为一个新的矩阵如表所示4。ACS可以通过应用改进calACS算法获得矩阵。

公共子序列从任意两行如表所示5。然而,相对较大的空间复杂性导致的不便后来遍历,存储和计算的支持。因此,一个前缀树采用更快的操作来减少空间的复杂性。

4.3。构造常见的前缀树

首先,候选人前缀树会产生的候选人子序列矩阵。图4说明了2-candidate前缀树在发现ACS操作。前缀树的叶节点存储的标签的行公共子序列(分支)。例如,叶子节点的分支图4记录,这意味着行3,4,5列头的公共子序列5和4。

叶节点的序列候选人前缀树不一定必须频繁的因为候选人将用于生成前缀树常见的前缀树的叶节点频繁子序列长度。

常见的前缀树是由删除不满足最低的罕见的子序列的支持。图5就是一个例子常见的前缀树()。

4.4。构建常见的前缀树

具体步骤是详细的构造候选人前缀树。基于先验的原则,如果一个序列是频繁的,那么它的所有子序列必须频繁。只有频繁序列可以生成超层序。

构建常见的前缀树,首先常见的th元素子序列插入th层常见的前缀树。与此同时,叶节点常见的前缀树修改。第二,罕见的子序列候选人前缀树被拒绝这样频繁的前缀树建立。此外,候选人前缀树和常见的前缀树的例子如图6。

5。实验和结果

5.1。实验的基因数据集

的算法在MATLAB平台上实现R2011b i3 380 cpu和4 g内存,操作系统是Windows Server 2007。真正的数据集是酵母半乳糖的数据(18,19),真正的基因微阵列数据集从一项研究获得应对各种基因的敲除半乳糖利用面包酵母(加)通路,行和列对应于淘汰赛条件对应的基因表现出对淘汰赛的反应。实验数据集微阵列数据集通过删除45相邻行和40列从原始矩阵。

5.1.1。重叠

BicAT软件和MATLAB被用于我们的实验20.),和重叠是定义如下21]。

让在biclusters两套基因。的重叠和他们的交集除以联盟,1意味着模块身份和0意味着没有重叠。考虑

实验结果中筛选两个步骤。(1)如果bicluster包含另一个,那么小bicluster将废弃。(2)列设置阈值。例如,如果阈值是6,那么列数字的biclusters不到六将被丢弃。

最后,我们获得的所有biclusters对应列阈值6。的总数OPSMs获得表所示6。我们可以我所有OPSMs满足行阈值因为我们的算法是准确的。OPSMs减少的数量随着行数量的阈值增加。

此外,图7统计图表显示了在771年的重叠分布biclusters的行和列的阈值是10阈值是6。

图7显示没有重叠biclusters占总数的60.42%,和之间的重叠程度,0和0.1(0除外)占总数的35.54%。因此,重叠的biclusters是0和0.1之间(包括0)占95.96%。也就是说,biclusters没有重叠或非常小的重叠。

5.1.2中。OPSMs开采的一个例子

数据8(一个)和8 (b)显示OPSMs包含一行时的最大列数阈值设置为5和8。图8(一个)显示了五个基因的表达式值展览同时兴衰在10个不同的实验。图8 (b)显示的最大列数确定OPSM当行阈值是8。

5.1.3。浓缩

实验数据集酵母数据集。我们首先使用CC,盐酸,则,OPSM xMotif模型BicAT工具箱获取结果。然后,我们运行我们的程序来获得相应的结果。获得的结果分别打包,在分析工具(http://go.princeton.edu/cgi-bin/GOTermFinder)来获取他们的值。最后,所有结果排序和分析。图9比较富集的结果(22,23]。

图9显示的浓缩算法明显高于CC的浓缩,盐酸,则,OPSM。特别是小值可以展示我们的优势。xMotif算法的结果接近我们,但略少。

5.2。实验合成数据集

5.2.1。噪声的影响

模拟数据的生成如下。首先,我们生成的标准正态分布矩阵作为初始矩阵嵌入了五个不重叠的OPSMs行和列的记录集。然后,我们产生不同程度的噪声,其手段是0和方差是0,0.002,0.004,0.006,0.008,和0.01,分别。噪声将被添加到初始矩阵。最后,我们获得了6个输入矩阵不同的噪音水平。

我们介绍了匹配分数评估算法(22]。让和是两个bicluster集。然后,基因匹配得分关于被定义为

它显示的平均值最大的基因中所有biclusters匹配分数关于biclusters。可以解释为整体匹配分数,在那里是相应的条件匹配分数。

我们计算不同bicluster的匹配分数结果,比较如图10(22]。

我们的算法的匹配分数比其他的要好。随着噪声级的增加,总比赛得分下降缓慢。

5.2.2。重叠

首先,我们生成的标准正态分布矩阵嵌入了5OPSMs行和列的记录集。同样的,我们获得了5个输入矩阵与不同的重叠的水平。重叠的水平,,,,对应于0,0.087,0.1905,0.3158,和0.4706,分别。合成不同的算法进行了测试的数据,这场比赛得分的计算结果。如图所示的性能比较11(22]。

图11表明,我们的算法的匹配分数比其他算法。其他算法的参数设置是基于最好的实验结果。

6。结论

OPSMs被接受作为一个生物学意义bicluster模型。深OPSMs组成的少数基因共享表达模式在许多生物学家条件是非常有趣的。

在这篇文章中,一个精确的算法,提出了基于频繁序列模式挖掘不仅OPSMs, OPSMs还深。基因数据集上的实验表明,这种方法可以发现生物重要OPSMs和深OPSMs详尽。此外,合成数据集的实验结果证明了我们的方法可以有效地挖掘植入biclusters在不同噪声和重叠的水平。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者感谢同事参与了这项研究,提供了宝贵的技术支持。支持的工作是由广东省科学技术厅批准号2012 b091100349,广东经贸委员会批准号GDEID2010IS034,广州越秀区下科技局批准号2012 - gx - 004,国家自然科学基金(批准号。71102146,71102146)。