The BiMax algorithm

Thu 12 September 2013 by Kemal Eren

Introduction

The focus of this post is BiMax, a method developed to serve as a baseline in a comparison of biclustering algorithms [1]. Because BiMax was developed as a reference method, its objective is intentionally simple: it finds all biclusters consisting entirely of 1s in a binary matrix.

Specifically, BiMax enumerates all inclusion-maximal biclusters, which are biclusters of all 1s to which no row or column can be added without introducing 0s. More formally, an inclusion-maximal bicluster of \(m \times n\) binary matrix \(M\) is a set of rows and a set of columns \((R, C)\) , with \(R \in 2 ...

read more

Cheng and Church

Thu 08 August 2013 by Kemal Eren

Introduction

The subject of today’s post is a biclustering algorithm commonly referred to by the names of its authors, Yizong Cheng and George Church [1]. It is one of the best-known biclustering algorithms, with over 1,400 citations, because it was the first to apply biclustering to gene microarray data. This algorithm remains popular as a benchmark: almost every new published biclustering algorithm includes a comparison with it.

Cheng and Church were interested in finding biclusters with a small mean squared residue, which is a measure of bicluster homogeneity. To define the mean squared residue, the following notation will ...

read more

Spectral biclustering, part 2

Fri 12 July 2013 by Kemal Eren

Introduction

Continuing the discussion of spectral biclustering methods, this post covers the Spectral Biclustering algorithm (Kluger, et. al., 2003) [1]. This method was originally formulated for clustering tumor profiles collected via RNA microarrays. This section introduces the checkerboard bicluster structure that the algorithm fits. The next section describes the algorithm in detail. Finally, in the last section we will see how it can be used for clustering real microarray data.

The data collected from a gene expression microarray experiment may be arranged in a matrix \(A\) , where the rows represent genes and the columns represent individual microarrays. Entry \(A_{ij ...

read more

Spectral biclustering, part 1

Thu 04 July 2013 by Kemal Eren

Introduction

This is the second entry in the series on biclustering algorithms, this time covering spectral biclustering. This is the first part, focusing on the Spectral Co-Clustering algorithm (Dhillon, 2001) [1]. The next part will focus on a related algorithm, Spectral Biclustering (Kluger et. al., 2003) [2].

To motivate the spectral biclustering problem, let us return to our friend Bob, who hosted the party in the previous article. Bob is thinking about music again, but this time he is writing song lyrics. Bob plans to imitate popular songs by including similar words in his lyrics. To learn which words to ...

read more

An introduction to biclustering

Tue 25 June 2013 by Kemal Eren

Introduction

This is the first in my series of biclustering posts. It serves as an introduction to the concept. The later posts will cover the individual algorithms that I am implementing for scikit-learn.

Before talking about biclustering, it is necessary to cover the basics of clustering. Clustering is a fundamental problem in data mining: given a set of objects, group them according to some measure of similarity. This deceptively simple concept has given rise to a wide variety of problems and the algorithms to solve them. scikit-learn provides a number of clustering methods, but these represent only a small fraction ...

read more

Google Summer of Code 2013

Thu 06 June 2013 by Kemal Eren

This summer I will be participating in the Google Summer of Code by implementing biclustering algorithms for scikit-learn. As required by the Python Foundation, I will be reporting my progress on this blog.

read more

Biclustering paper accepted

Mon 21 May 2012 by Kemal Eren

Our paper, A Comparative Analysis of Biclustering Algorithms for Gene Expression Data has been accepted by Briefings in Bioinformatics.

read more

New position at Heidelberg University

Thu 29 March 2012 by Kemal Eren

On 7 March 2012 I successfully defended my Master’s Thesis, Application of biclustering algorithms to biological data, which will soon be available at the OhioLINK ETD Center.

Next month I will officially begin a new position in the Multidimensional Image Processing lab at Heidelberg University.

read more

New software: BiBench

Tue 13 December 2011 by Kemal Eren

My associates and I at the HPC Lab have just released some new software: BiBench, a Python package for biclustering. In addition to lots of other functionality, It provides a common interface to twelve biclustering algorithms, including our own CPB algorithm.

BiBench makes biclustering gene expression datasets easy. In only a few lines of code you can download a GDS dataset, bicluster it, and perform GO enrichment analysis on the genes of the resulting biclusters. Though we developed BiBench to specifically target gene expression data, it is useful for any data that may be meaningfully biclustered.

A download link, installation ...

read more

We got runner up for best poster at ACM BCB 2011

Sun 07 August 2011 by Kemal Eren

I just got back from presenting a poster at the ACM Conference on Bioinformatics, Computational Biology and Biomedicine in Chicago, IL. We were voted runner up for best poster! The poster will soon be available at the HPC lab website.

read more