Identification of Regulatory Modules in Time Series Gene Expression Data Using a Linear Time Biclustering Algorithm
- 31 March 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 7 (1) , 153-165
Abstract
Although most biclustering formulations are NP-hard, in time series expression data analysis, it is reasonable to restrict the problem to the identification of maximal biclusters with contiguous columns, which correspond to coherent expression patterns shared by a group of genes in consecutive time points. This restriction leads to a tractable problem. We propose an algorithm that finds and reports all maximal contiguous column coherent biclusters in time linear in the size of the expression matrix. The linear time complexity of CCC-Biclustering relies on the use of a discretized matrix and efficient string processing techniques based on suffix trees. We also propose a method for ranking biclusters based on their statistical significance and a methodology for filtering highly overlapping and, therefore, redundant biclusters. We report results in synthetic and real data showing the effectiveness of the approach and its relevance in the discovery of regulatory modules. Results obtained using the transcriptomic expression patterns occurring in Saccharomyces cerevisiae in response to heat stress show not only the ability of the proposed methodology to extract relevant information compatible with documented biological knowledge but also the utility of using this algorithm in the study of other environmental stresses and of regulatory modules in general.Keywords
This publication has 37 references indexed in Scilit:
- The Graphical Query Language: a tool for analysis of gene expression time-coursesBioinformatics, 2005
- Identifying time-lagged gene clusters using gene expression dataBioinformatics, 2004
- Biclustering algorithms for biological data analysis: a surveyIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- Mining gene expression data for positive and negative co-regulated gene clustersBioinformatics, 2004
- Analyzing time series gene expression dataBioinformatics, 2004
- The maximum edge biclique problem is NP-completeDiscrete Applied Mathematics, 2003
- Inference of transcriptional regulation relationships from gene expression dataBioinformatics, 2003
- Stress tolerance in a yeast sterol auxotroph: role of ergosterol, heat shock proteins and trehaloseFEMS Microbiology Letters, 1998
- On-line construction of suffix treesAlgorithmica, 1995
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976