A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series
See where this sits in the topic map →Summary AI-generated
- TL;DR
- We propose e-CCC-Biclustering, an efficient polynomial-time algorithm for discovering approximate local expression patterns in gene expression time series data.
- Problem
- While most formulations of the biclustering problem are NP-hard, restricting the search to contiguous columns in time series data makes the problem tractable and allows for efficient algorithms to identify coherent biclusters.
- Method
- The e-CCC-Biclustering algorithm finds all maximal contiguous column coherent biclusters with approximate expression patterns in polynomial time by using efficient string processing techniques on a discretized version of the original matrix. It also includes extensions for handling missing values, discovering anticorrelated and scaled patterns, and scoring results using statistical significance and overlap similarity.
- Results
- Experiments on real data demonstrate the algorithm's effectiveness in discovering regulatory modules of Saccharomyces cerevisiae responding to heat stress, showing the clear advantage of approximate patterns over methods that require exact matching.
- Contributions
- The introduction of the e-CCC-Biclustering algorithm, its polynomial-time complexity via string processing techniques, and extensions for handling missing values, anticorrelated patterns, scaled patterns, and custom error computations and scoring criteria.
- Limitations
- Not specified in the abstract.
- Takeaways
- Efficiently identifying sets of genes with similar expression patterns is instrumental in uncovering biological phenomena and providing convincing evidence of specific regulatory mechanisms.
- Applications
- Analyzing gene expression time series from microarray experiments to understand complex biological processes and gene regulatory networks.
- Topics
- Bioinformatics, Biclustering Algorithms, Gene Expression Analysis, Time Series Data, String Processing
- For industry
- Biotechnology and Life Sciences
- Why it matters
- Advances our understanding of complex biological processes and gene regulatory mechanisms by enabling the efficient discovery of local expression patterns.
Abstract
BACKGROUND: The ability to monitor the change in expression patterns over time, and to observe the emergence of coherent temporal responses using gene expression time series, obtained from microarray experiments, is critical to advance our understanding of complex biological processes. In this context, biclustering algorithms have been recognized as an important tool for the discovery of local expression patterns, which are crucial to unravel potential regulatory mechanisms. Although most formulations of the biclustering problem are NP-hard, when working with time series expression data the interesting biclusters can be restricted to those with contiguous columns. This restriction leads to a tractable problem and enables the design of efficient biclustering algorithms able to identify all maximal contiguous column coherent biclusters. METHODS: In this work, we propose e-CCC-Biclustering, a biclustering algorithm that finds and reports all maximal contiguous column coherent biclusters with approximate expression patterns in time polynomial in the size of the time series gene expression matrix. This polynomial time complexity is achieved by manipulating a discretized version of the original matrix using efficient string processing techniques. We also propose extensions to deal with missing values, discover anticorrelated and scaled expression patterns, and different ways to compute the errors allowed in the expression patterns. We propose a scoring criterion combining the statistical significance of expression patterns with a similarity measure between overlapping biclusters. RESULTS: We present results in real data showing the effectiveness of e-CCC-Biclustering and its relevance in the discovery of regulatory modules describing the transcriptomic expression patterns occurring in Saccharomyces cerevisiae in response to heat stress. In particular, the results show the advantage of considering approximate patterns when compared to state of the art methods that require exact matching of gene expression time series. DISCUSSION: The identification of co-regulated genes, involved in specific biological processes, remains one of the main avenues open to researchers studying gene regulatory networks. The ability of the proposed methodology to efficiently identify sets of genes with similar expression patterns is shown to be instrumental in the discovery of relevant biological phenomena, leading to more convincing evidence of specific regulatory mechanisms. AVAILABILITY: A prototype implementation of the algorithm coded in Java together with the dataset and examples used in the paper is available in http://kdbio.inesc-id.pt/software/e-ccc-biclustering.