LateBiclustering: Efficient Heuristic Algorithm for Time-Lagged Bicluster Identification

Joana P. Gonçalves, Sara Cordeiro Madeira

Research output: Contribution to journalArticleScientificpeer-review

14 Citations (Scopus)

Abstract

Identifying patterns in temporal data is key to uncover meaningful relationships in diverse domains, from stock trading to social interactions. Also of great interest are clinical and biological applications, namely monitoring patient response to treatment or characterizing activity at the molecular level. In biology, researchers seek to gain insight into gene functions and dynamics of biological processes, as well as potential perturbations of these leading to disease, through the study of patterns emerging from gene expression time series. Clustering can group genes exhibiting similar expression profiles, but focuses on global patterns denoting rather broad, unspecific responses. Biclustering reveals local patterns, which more naturally capture the intricate collaboration between biological players, particularly under a temporal setting. Despite the general biclustering formulation being NP-hard, considering specific properties of time series has led to efficient solutions for the discovery of temporally aligned patterns. Notably, the identification of biclusters with time-lagged patterns, suggestive of transcriptional cascades, remains a challenge due to the combinatorial explosion of delayed occurrences. Herein, we propose LateBiclustering, a sensible heuristic algorithm enabling a polynomial rather than exponential time solution for the problem. We show that it identifies meaningful time-lagged biclusters relevant to the response of Saccharomyces cerevisiae to heat stress.
Original languageEnglish
Pages (from-to)801-813
Number of pages13
JournalIEEE - ACM Transactions on Computational Biology and Bioinformatics
Volume11
Issue number5
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Time series
  • time lag
  • biclustering
  • string matching
  • pattern recognition
  • local pattern
  • pattern matching

Fingerprint

Dive into the research topics of 'LateBiclustering: Efficient Heuristic Algorithm for Time-Lagged Bicluster Identification'. Together they form a unique fingerprint.

Cite this