从基因表达数据中发现知识摘要OPSM模型作为一种基于模式的双聚类方法，在分析基因数据矩阵等方面被广泛的应用。
在一个OPSM聚类中，形成聚类的若干基因在特定的条件子集下有一致的表达模式。
这种关联的共同表达隐含着基因的关联调控。
所以在基因数据矩阵上进行的双聚类分析有极大的生物意义。
将挖掘OPSM聚类，转化为序列模式挖掘，双聚类问题就转化为频繁项集的挖掘问题。
然而随着越来越多的基因被发现，基因数据矩阵变得越来越庞大。
目前针对基因表达数据的双聚类算法都存在时间效率较低的问题。
这给频繁项集的发现带来了困难。
特别是一些支持度较小的长频繁项集，更是以往的双聚类方法难以发现的有意义信息。
Deep-OPSM问题，针对基因数据矩阵中一些支持度较小的长频繁模式的挖掘。
将在基因数据分析上有更大的生物意义。
但现有的双聚类模型，在针对大型基因数据矩阵的分析时，性能都会受到严重影响。
以致于一些隐含在大型基因数据矩阵的深层意义信息难以被发现。
所以亟需更加高效的寻找OPSM的方法。
本文根据OPSM模型，建立了一个快速有效的精确性寻找方法，来挖掘分散在基因数据矩阵中的OPSM聚类。
首先在基因数据矩阵中的每两行寻找其公共子序列，然后利用STL map，在整个基因数据矩阵的范围内，对找到的公共子序列进行支持度的统计，并将达到支持度阈值的OPSM聚类输出。
实验证明该方法能够快速地找到符合条件的OPSM聚类，并且能够通过条件存储，针对长频繁模式进行寻找分析，挖掘出更具生物意义的Deep-OPSM聚类。
此外，通过条件存储，可以在多台计算机上实现并行计算，提高分析处理速度，适应大型数据矩阵的分析需求。
最后从生物学的角度，验证了该方法的可行性。
关键词：OPSM，序列模式，Deep-OPSM，STL mapMine the knowledge from the gene expression dataA bstractOrder-preserving submatrix (OPSM) has been widely accepted as a biologically meaningful cluster model, capturing the general tendency of gene expression across a subset of experiments. In an OPSM, the expression levels of all genes induce the same linear ordering of the experiments. The OPSM problem is to discover those statistically significant OPSMs from a given data matrix. The problem is reducible to a special case of the sequential pattern mining problem, where a pattern and its supporting sequences uniquely specify an OPSM. However, as more and more genes are discovered, data sets containing more and more experiments and genes. And existing methods do not scale well to massive data sets containing many experiments and hundreds of thousands of genes because of the low efficiency problem. It makes it difficult to discovery OPSM in a massive data sets. In particular, deep OPSMs, corresponding to long patterns with few supporting sequences, incur explosive computational costs in their discovery and are completely pruned off by existing methods. Deep-OPSM problem is to discover long-frequent patterns with few supporting sequences in a data sets. It will have greater biological significance in the analysis of data matrix. Therefore it is needed to find more efficient ways to find OPSMs.In this paper, We propose a accuracy method that is rapid and efficiency, to find all OPSMs in a data sets , as well as Deep-OPSMs. Firstly, we find the all the common subsequence in the data matrix for each of its two rows, and then we use the STL map, to count the supports of every common subsequence in the range of the data matrix. If the support of the common subsequence is grater than the support threshold , we find a OPSM. Experimental results show that this method can quickly find qualified OPSMs. And we can only digging out more Deep-OPSMs with more biological significance by selecting the long frequent patterns according to their lengths. In addition, because of the storage conditions(the length of the commonsubsequence), we can achieve parallel computing on multiple computers, improving analysis speed. That is good for anglicizing large data matrix. Finally extensive biological and computational evaluations on real data sets demonstrate the feasibility of the method.Key words：OPSM，sequential pattern，Deep-OPSM，STL map目录摘要 (1)1 引言 (5)2 相关工作 (7)3 基本概念和定义 (8)3.1 基因表达数据集 (8)3.2 公共子序列 (9)3.3 OPSM与Deep-OPSM (9)4 找OPSM的算法 (10)4.1. 寻找公共子序列的算法 (13)4.2 统计频繁项集的方法 (16)5 实验结果分析 (21)6结论 (23)参考文献 (24)1 引言随着DNA微阵列和寡核苷酸芯片等高通量检测技术的发展, 人们可以从全基因组水平定量检测基因转录产物mRNA, 产生的基因表达数据呈现爆炸性增长态势. 如何对基因表达数据进行有效的分析, 挖掘出有用的信息已经成为后基因组时代的研究热点（蔡，郭2010）。
通过基因芯片或微阵列技术产生了大量的基因表达数据，这些数据集通常是一个二维矩阵的形式，表示每个基因（行）在每个条件（列）下的表达水平。
在基因表达数据分析中,聚类曾是最流行的方法之一。
根据基因表达谱中的各基因的表达值,通过使用聚类方法把某一些有着相似表达行为的基因聚成一块,或者在基因基础上对条件进行聚类。
在使用以往的聚类方法得到的结果中,这些传统的方法要求这些基因必须满足在所有条件下的表达行为都要相似。
而实际上，共调控的基因并不是在所有的实验条件下都相关的，这使得传统的聚类方法已经不能适应对基因矩阵数据的分析要求。
为了克服传统聚类方法的这种局限性,一种新的方法—双聚类算法应运而生。
双聚类方法就可以把一些只在部分条件下有着相似表达行为的基因聚在一起,它和传统聚类算法的本质区别在于它可以对基因表达数据矩阵的行和列同时进行聚类,可以挖掘基因表达数据中的局部信息。
从而确定在一个实验条件子集下表现出相似行为的一组基因。
这种无监督模式识别和数据挖掘技术是发现基因之间共表达或共调控关系、预测基因功能、分析转录调控、阐释生物学通路和提供疾病机理等的重要手段。
图1 基因谱曲线举个例子，如果我们有一个包含5个基因的基因表达数据矩阵。
我们可以分别根据各个基因的基因谱表达做出其表达曲线如图1所示。
其中纵轴表示的是基因表达水平，横轴代表的是众多的实验条件或时间点。
如果我们把所有列的数据纳入考虑，很难观察出其中明显的模式。
但是如果只考虑列标的某个子集的数据，如列标的某个集合{‘a’，‘b’，‘c’，‘d’，‘e’}，我们就可以观察到这个行数据在数值大小上调或下调时表现出一致，如图2（a）所示。
如果再根据表达数据的大小对相应的列标进行排序，这种数据的表达模式一致性将更加明显，如图2（b）所示。
据此，我们在对基因矩阵数据进行分析之前，必须对基因矩阵数据做数据预处理，这种预处理有两个目的，一是使基因表达数据的升降模式更加明显，二是对基因数据矩阵中原本缺失的数据进行填充。
因为基因数据矩阵中缺失数据会对实验结果做成干扰，所以在数据预处理阶段，我们将缺失的数据填充为零。
（a）(b)图2部分条件下基因谱曲线因为多个基因在关联表达时，其各自的表达数据大小不需要完全相同（Byron J. Gao et.el 2012），所以对比基因表达水平的升降模式比对比基因的精确表达水平更加有意义。