Biclustering

Sei ${\displaystyle A=(a_{ij})_{m\times n}}$ eine Datenmenge in Form einer rechteckigen Matrix, die sich aus ${\displaystyle n}$ Spalten und ${\displaystyle m}$ Zeilen zusammensetzt. Jede Spalte steht für ein Sample (Datenprobe) und jede Zeile für ein Feature (Komponente eines Samples).[4] Jedem Sample ist somit eine Serie von Features zugeordnet.[5] Das Element ${\displaystyle a_{ij}}$ repräsentiert die Expression des ${\displaystyle i}$-ten Features im ${\displaystyle j}$-ten Sample.[4]

Weiters seien die Klassen ${\displaystyle S_{1},...,S_{r}}$ eine Klassifikation der Samples und die Klassen ${\displaystyle F_{1},...,F_{r}}$ eine Klassifikation der Features.[4] Eine Submatrix von ${\displaystyle A}$, die als Paar ${\displaystyle (S_{k},F_{k})}$ mit ${\displaystyle k\in \{1,...,r\}}$ dargestellt wird, wird als Bicluster bezeichnet.[4][5]

Beim Biclustering entsteht eine Partition ${\displaystyle B=\{(S_{1},F_{1}),...,(S_{r},F_{r})\}}$ von ${\displaystyle A}$, bestehend aus ${\displaystyle r}$ Biclustern.[5] Manche Biclustering-Methoden erlauben Bicluster, die Sample- und Feature-Klassen mit unterschiedlichen Indizes beinhalten (das sind Paare ${\displaystyle (S_{k},F_{l})}$ mit ${\displaystyle k,l\in \{1,...,r\}}$ und ${\displaystyle k\neq l}$).[4]

Die Komplexität des Biclustering-Problems ist abhängig von der exakten Problemformulierung, insbesondere von der Gütefunktion, die zur Evaluierung der Qualität des gegebenen Biclusters verwendet wird. Die interessantesten Varianten dieses Problems sind jedoch NP-vollständig und erfordern entweder einen hohen Rechenaufwand oder die Verwendung einer verlustbehafteten Heuristik, um die Berechnung zu verkürzen.[6]

Verschiedene Biclustering-Algorithmen haben verschiedene Definitionen für den Bicluster:[6]

1. Bicluster mit konstanten Werten (a),
2. Bicluster mit konstanten Zeilenwerten (b) oder Spaltenwerten (c),
3. Bicluster mit kohärenten Werten (d, e).

Die Beziehung zwischen diesen Clustermodellen und anderen Clusteringtypen, wie Correlation Clustering, wird diskutiert in.[7]

Zahlreiche Biclustering-Algorithmen wurden für die Bioinformatik entwickelt, darunter: Block Clustering, CTWC (Coupled Two-Way Clustering), ITWC (Interrelated Two-Way Clustering), δ-Bicluster, δ-pCluster, δ-Pattern, FLOC, OPC, Plaid Model, OPSMs (Order-preserving Submatrices), Gibbs, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis),[8] Robust Biclustering Algorithm (RoBA), Crossing Minimization,[9] cMonkey,[10] PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) und FABIA (Factor Analysis for Bicluster Acquisition).[11] Auch in anderen Anwendungsgebieten werden Biclustering-Algorithmen vorgeschlagen und eingesetzt. Dort sind sie unter den Bezeichnungen Co-Clustering, Bidimensional Clustering sowie Subspace Clustering zu finden.[6]

Biclustering hat sich zur Erkennung lokaler Muster in Zeitreihendaten als relevant gezeigt. Daher haben sich neueste Ansätze für Zeitreihendaten von Genexpressionen dem Biclustering-Problem gewidmet, mit dem interessante Bicluster auf Bicluster mit aneinander angrenzenden Spalten beschränkt werden können. Diese Einschränkung führt zu einem Problem, das in polynomieller Zeit gelöst werden kann. Zudem ermöglicht es die Entwicklung von effizienten erschöpfenden Enumerationsalgorithmen, wie CCC-Biclustering[12] und e-CCC-Biclustering.[13] Manche der neuesten Algorithmen haben versucht, zusätzliche Unterstützung für das Biclustering von rechteckigen Matrizen mit anderen Datentypen, darunter cMonkey, zu inkludieren.

Es gibt eine fortlaufende Debatte über die Beurteilung der Ergebnisse dieser Methoden, da Biclustering die Überlappung von Clustern erlaubt und manche Algorithmen die Exklusion schwierig vereinbarter Spalten/Bedingungen erlauben. Nicht alle der verfügbaren Algorithmen sind deterministisch. Der Analytiker muss die Aufmerksamkeit auf das Ausmaß jener Ergebnisse richten, die stabile Minima darstellen. Da sich das Problem auf unüberwachtes Lernen bezieht, erweist sich die Fehlererkennung in den Ergebnissen wegen des fehlenden Goldstandards als schwierig. Ein Ansatz ist die Anwendung mehrerer Biclustering-Algorithmen, deren Mehrheit oder qualifizierte Mehrheit das beste Ergebnis ermittelt. Eine andere Möglichkeit ist eine Qualitätsanalyse der Shifting- und Scaling-Pattern von Biclustern.[14] Biclustering wird auch im Bereich des Text Mining (oder der Klassifizierung) unter dem Begriff Co-Clustering eingesetzt.[15] Textkorpora werden in Vektorform als eine Matrix D dargestellt, deren Zeilen für die Dokumente und deren Spalten für die Wörter eines Wörterbuches stehen. Die Matrix-Elemente D_ij bezeichnen das Vorkommen des Wortes j im Dokument i. Co-Clustering-Algorithmen werden anschließend zur Erkennung von Blöcken in D angewandt, welche einer Gruppe von Dokumenten (Zeilen) entsprechen, die durch eine Gruppe von Wörtern (Spalten) gekennzeichnet sind.

Mehrere Ansätze wurden basierend auf den Informationsinhalten der erhaltenen Blöcke vorgeschlagen: Matrix-basierte Ansätze, wie SVD und BVD sowie Graph-basierte. Informationstheoretische Algorithmen weisen iterativ jeder Zeile einen Cluster von Dokumenten und jeder Spalte einen Cluster von Wörtern zu, sodass die gegenseitige Information maximiert wird. Matrix-basierte Methoden fokussieren sich auf die Dekomposition von Matrizen in Blöcke, damit der Fehler der Dekomposition zwischen der ursprünglichen Matrix und den neu gebildeten Matrizen minimiert wird. Graph-basierte Methoden neigen dazu, die Überschneidungen zwischen den Clustern zu minimieren. Sind zwei Gruppen von Dokumenten d₁ und d₂ gegeben, kann die Anzahl der Überschneidungen anhand der Anzahl der Wörter, die in Dokumenten der Gruppen d₁ und d₂ auftreten, gemessen werden.

Bisson und Hussain[15] haben einen neuen Ansatz zur Verwendung der Ähnlichkeit zwischen Wörtern und der Ähnlichkeit zwischen Dokumenten zum Co-Clustering einer Matrix vorgeschlagen. Ihre Methode χ-Sim (Cross Similarity) basiert auf dem Finden einer Ähnlichkeit zwischen Dokumenten und Wörtern und der anschließenden Verwendung von klassischen Clusteringmethoden, wie dem hierarchischen Clustering.

• Formale Begriffsanalyse
• Galoisverbindung

• Amos Tanay, Roded Sharan, Ron Shamir: Biclustering Algorithms: A Survey. In: Srinivas Aluru (Hrsg.): Handbook of Computational Molecular Biology. Chapman, 2004.
• Yuval Kluger, Ronen Basri, Joseph T. Chang, Mark Gerstein: Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions. In: Genome Research. 13. Jahrgang, Nr. 4, 2003, S. 703–716, doi:10.1101/gr.648603, PMID 12671006, PMC 430175 (freier Volltext).

1. Iven Van Mechelen, Hans-Hermann Bock, Paul De Boeck: Two-mode clustering methods:a structured overview. In: Statistical Methods in Medical Research. 13. Jahrgang, Nr. 5, 2004, S. 363–94, doi:10.1191/0962280204sm373ra, PMID 15516031.
2. Boris Mirkin: Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996, ISBN 0-7923-4159-7.
3. J.A. Hartigan: Direct clustering of a data matrix. In: Journal of the American Statistical Association. 67. Jahrgang, Nr. 337. American Statistical Association, 1972, S. 123–9, doi:10.2307/2284710.
4. Stanislav Busygin, Oleg Prokopyev, Panos M. Pardalos: Biclustering in data mining. In: Computers & Operations Research. 35. Jahrgang, Nr. 9, 2008, S. 2964–2987, doi:10.1016/j.cor.2007.01.005.
5. Antonio Mucherino, Sonia Cafieri: A New Heuristic for Feature Selection by Consistent Biclustering. In: Cornell University. 2010, arxiv:1003.3279v1.
6. Sara C. Madeira, Arlindo L. Oliveira: Biclustering Algorithms for Biological Data Analysis: A Survey. In: IEEE Transactions on Computational Biology and Bioinformatics. 1. Jahrgang, Nr. 1, 2004, S. 24–45, doi:10.1109/TCBB.2004.2, PMID 17048406.
7. Hans-Peter Kriegel, Peer Kröger, Arthur Zimek: Clustering High Dimensional Data: A Survey on Subspace Clustering, Pattern-based Clustering, and Correlation Clustering. In: ACM Transactions on Knowledge Discovery from Data (TKDD). 3. Jahrgang, Nr. 1, März 2009, S. 1–58, doi:10.1145/1497577.1497578.
8. Amos Tanay, Roded Sharan, Martin Kupiec, Ron Shamir: Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data. In: Proc Natl Acad Sci USA. 101. Jahrgang, Nr. 9, 2004, S. 2981–2986, doi:10.1073/pnas.0308661100, PMID 14973197, PMC 365731 (freier Volltext).
9. Ahsan Abdullah, Amir Hussain: A new biclustering technique based on crossing minimization. In: Neurocomputing. 69. Jahrgang, Nr. 16–18, 2006, S. 1882–1896, doi:10.1016/j.neucom.2006.02.018 (elsevier.com).
10. David J. Reiss, Nitin S. Baliga, Richard Bonneau: Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks. In: BMC Bioinformatics. 2. Jahrgang, 2006, S. 280–302, doi:10.1186/1471-2105-7-280, PMID 16749936, PMC 1502140 (freier Volltext).
11. Sepp Hochreiter, Ulrich Bodenhofer, Martin Heusel, Andreas Mayr, Andreas Mitterecker, Adetayo Kasim, Tatsiana Khamiakova, Suzy Van Sanden, Dan Lin, Willem Talloen, Luc Bijnens, Hinrich W. H. Gohlmann, Ziv Shkedy, Djork-Arné Clevert: FABIA: factor analysis for bicluster acquisition. In: Bioinformatics. 26. Jahrgang, Nr. 12, 2010, S. 1520–1527, doi:10.1093/bioinformatics/btq227, PMID 20418340, PMC 2881408 (freier Volltext).
12. Sara C. Madeira, Miguel C. Teixeira, Isabel Sá-Correia, Arlindo L. Oliveira: Identification of Regulatory Modules in Time Series Gene Expression Data using a Linear Time Biclustering Algorithm. In: IEEE Transactions on Computational Biology and Bioinformatics. 1. Jahrgang, Nr. 7, 2010, S. 153–165, doi:10.1109/TCBB.2008.34.
13. Sara C. Madeira, Arlindo L. Oliveira: A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series. In: Algorithms for Molecular Biology. 4. Jahrgang, Nr. 8, 2009.
14. Jesús S. Aguilar-Ruiz: Shifting and scaling patterns from gene expression data. In: Bioinformatics. 21. Jahrgang, Nr. 10, 2005, S. 3840–3845, doi:10.1093/bioinformatics/bti641, PMID 16144809.
15. Gilles Bisson, Fawad Hussain: Chi-Sim: A new similarity measure for the co-clustering task. In: ICMLA. 2008, S. 211–217, doi:10.1109/ICMLA.2008.103.