Discovering local structure in gene expression data: The order-preserving submatrix problem
Discovering local structure in gene expression data: The order-preserving submatrix problem
复制标题
DOI：
10.1089/10665270360688075
复制
发表时间：
2003-01-01
影响因子：
1.7
通讯作者：
Yakhini, Z
中科院分区：
文献类型：
--
作者：
Ben-Dor, A;Chor, B;Yakhini, Z
本文涉及基因表达矩阵模式的发现，其中每个元素给出了给定实验中给定基因的表达水平。大多数现有的模式发现方法是通过比较所有实验中的表达水平来聚类基因，或者通过比较所有基因的表达水平来聚类实验。我们的工作超越了这种全局方法，通过寻找局部模式，当我们同时关注基因的子集G和实验的子集T时，这些模式就会显现出来。具体来说，我们寻找保序子矩阵（OPSM），其中所有基因的表达水平诱导实验的相同线性顺序（我们表明，在最坏的情况下，OPSM搜索问题是np困难的）。例如，如果T中的实验代表疾病进展或细胞过程的不同阶段，并且G中所有基因的表达水平在各个阶段以相同的方式变化，则可能出现这种模式。我们定义了一个概率模型，其中OPSM隐藏在一个随机矩阵中。在此模型的指导下，我们开发了一种寻找随机矩阵中隐藏OPSM的有效算法。在根据模型生成的数据中，该算法以很高的成功率恢复了隐藏的OPSM。将这些方法应用于乳腺癌数据似乎揭示了重要的局部模式。
This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. Our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset G of the genes and a subset T of the experiments. Specifically, we look for order-preserving submatrices (OPSMs), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the OPSM search problem is NP-hard in the worst case). Such a pattern might arise, for example, if the experiments in T represent distinct stages in the progress of a disease or in a cellular process and the expression levels of all genes in G vary across the stages in the same way. We define a probabilistic model in which an OPSM is hidden within an otherwise random matrix. Guided by this model, we develop an efficient algorithm for finding the hidden OPSM in the random matrix. In data generated according to the model, the algorithm recovers the hidden OPSM with a very high success rate. Application of the methods to breast cancer data seem to reveal significant local patterns.