An efficient voting algorithm for finding additive biclusters with random background

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1275-1293
Journal / PublicationJournal of Computational Biology
Volume15
Issue number10
Publication statusPublished - 1 Dec 2008

Abstract

The biclustering problem has been extensively studied in many areas, including e-commerce, data mining, machine learning, pattern recognition, statistics, and, more recently, computational biology. Given an n × m matrix A (n ≥ m), the main goal of biclustering is to identify a subset of rows (called objects) and a subset of columns (called properties) such that some objective function that specifies the quality of the found bicluster (formed by the subsets of rows and of columns of A) is optimized. The problem has been proved or conjectured to be NP-hard for various objective functions. In this article, we study a probabilistic model for the implanted additive bicluster problem, where each element in the n × m background matrix is a random integer from [0, L - 1] for some integer L, and a k × k implanted additive bicluster is obtained from an error-free additive bicluster by randomly changing each element to a number in [0, L - 1] with probability θ. We propose an O(n2m) time algorithm based on voting to solve the problem. We show that when k ≥ Ω (√n log n), the voting algorithm can correctly find the implanted bicluster with probability at least 1 - (9/n2). We also implement our algorithm as a C++ program named VOTE. The implementation incorporates several ideas for estimating the size of an implanted bicluster, adjusting the threshold in voting, dealing with small biclusters, and dealing with overlapping implanted biclusters. Our experimental results on both simulated and real datasets show that VOTE can find biclusters with a high accuracy and speed. © Mary Ann Liebert, Inc. 2008.

Research Area(s)

  • Additive bicluster, Computational biology, Gene expression data analysis, Polynomial-time algorithm, Probability model

Citation Format(s)