Information Technology Reference
In-Depth Information
As we mentioned above, most of biclustering algorithms are unsupervised clas-
sification and it does not need to have any training sets. But supervised biclustering
methods are also useful in some cases of biomedicine applications [5, 4, 40].
In this chapter, an optimization prospective of biclustering will be studied, and
different objective functions will be used for different algorithms to satisfy part of
objectives above. There is no such algorithm that can satisfy all objectives, and
additionally, there is no such standard of justifying the algorithms. In distinct ap-
plications of biclustering, a specific or several objectives should be met so some
algorithms are designed to satisfy these requirements. There are some methods try-
ing to compare different algorithms, and we refer to [37, 44, 47, 61].
6.1.4 History
The first approach to biclustering is “direct clustering of data matrix” by Hartigan
[28] in 1972. But the term “biclustering” was famous after Cheng and Church [11]
using this technique to do gene expression analysis. After that, many biclustering
algorithms are designed in different areas' applications, such as biological network,
microarray data, word-document co-clustering, biomedical engineering, of which
the most popular applications are in microarray data and gene expression data.
In 2004, Madeira and Oliveira [37] surveyed the biclustering algorithms for bi-
ological data analysis. In this survey, they identified the biclusters into four major
classes: biclusters with constant values, with constant values on rows or columns,
with coherent values, and with coherent evolutions. The biclustering structures of
a data matrix are classified into nine groups according to algorithms: single biclus-
ter, exclusive row and column biclusters, checkerboard structure, exclusive rows
biclusters, exclusive columns biclusters, nonoverlapping biclusters with tree struc-
ture, nonoverlapping nonexclusive biclusters, overlapping biclusters with hierar-
chical structure, and arbitrarily positioned overlapping biclusters. In addition, the
authors have also divided the algorithms into five classes: Iterative row and col-
umn clustering combination, divide and conquer, greedy iterative search, exhaustive
bicluster enumeration, and distribution parameter identification. A comparison of
these algorithms according to the above three classes is given in this survey.
Another review about biclustering algorithms is by Tanay et al. in [55] in 2004.
In this survey, nine mostly used algorithms are reviewed and given with their pseu-
docodes. Mostly recent review of biclustering is by Busygin et al. in [5], and 16
algorithms are reviewed with their applications in biomedicine and text mining. In
this chapter, the authors mentioned that “many of the approaches rely on not mathe-
matically strict arguments and there is a lack of methods to justify the quality of the
obtained biclusters.”
In this chapter, we are trying to review and study the biclustering algorithms
in mathematical and optimization prospectives. Not all of the algorithms will be
covered, but most recent valuable algorithms are covered.
