Clustering, which involves dividing data elements into classes based on their observed properties, is one of the main tools in exploratory data analysis. It is used widely in the analysis of gene expression, where one searches for structures related to the underlying biological mechanisms. Clusters of gene expression patterns are a signature of a common regulatory process of the involved genes. Clusters of experimental conditions, e.g. tissues in an organism, imply similar states of cell differentiation. The latter property is used in the tumour sample classification. This thesis establishes a statistical grounding for cluster analysis in high-dimensional data. The methods used in the thesis are strongly influenced by solutions from the field of statistical mechanics. The basic concepts and computational methods of statistical mechanics are summarised in Chapter 2. In Chapter 3, we propose probabilistic models for vectors in high-dimensional real space. Motivated by the characteristics of gene expression data, we discuss different properties defining a cluster: point density, positional bias, and directional density (defined in Chapter 3). These properties are related to different choices of a similarity measure and of a background distribution for unclustered vectors. We consider several combinations of such background distributions and similarity measures, and we arrive at well-defined scoring schemes for clusters. Clusters in data usually arise due to an underlying functional mechanism. However, even unrelated vectors drawn from the background distribution can form agglomerations which by chance resemble clusters and yield high cluster scores. In Chapter 4, we address the problem of the statistical significance of clusters. For the scoring schemes proposed in Chapter 3, we compute the cluster score p-value, which tells how likely it is to observe a group of random vectors with the same or higher score. Our analytical solution is based on a mapping to a problem from the statistical mechanics of disordered systems. In an application to yeast gene expression data, we show that the cluster score p-value is in agreement with the biological significance of clustered genes, as measured by enrichment of considered clusters in gene ontology terms (i.e. known functional annotations of genes). In Chapter 5, we focus on another important aspect of the statistics of high-dimensional data: dependencies between vector components. Such dependencies are prevalent in gene expression data, for example between subsequent time points in time-course experiments. Correct estimation of such dependencies is crucial both for clustering of experimental conditions, and for computation of similarities of gene expression vectors. Here, we show that the estimation of vector-component dependencies requires accounting for an important confounding factor: the presence of clusters of data vectors. We propose a mixture-model-based inference method, which disentangles the spurious effect of clusters from the true signal. We successfully apply our method to the problem of tumour sample classification. In Chapter 6, we propose the significance-based clustering algorithm. The algorithm seeks the best representation of data as a mixture of the background and of clusters characterised by a statistically significant score. In the implementation of this approach, we draw from all concepts discussed in the preceding chapters of this thesis: In the process of finding clusters of vectors, the algorithm estimates the metric which accounts for dependencies between components of the vectors. Further, using the probabilistic framework of the mixture-model, it assigns low prior probability, and effectively penalises, clusters with high cluster score p-value. In application to gene-expression data of yeast and human, we show that the significance-constraint improves the biological significance of resulting clusters.
Clustering, das Gruppieren von Datenpunkten aufgrund ihrer beobachteten Eigenschaften, ist eines der wichtigsten Werkzeuge in der Datenanalyse. Es wird haeufig in der Analyse von Genexpressionsdaten verwendet, um Gene zu identifizieren, die aehnliche biologischen Funktionen haben. Cluster von Genexpressionsmustern lassen oft auf einen gemeinsamen regulatorischen Prozess der beteiligten Gene schliessen. Cluster von experimentellen Bedingungen, z.B. von unterschiedlichen Geweben in einem Organismus, sind ein Hinweis auf einen aehnlichen Zustand der Zelldifferenzierung. Die zuletzt genannte Eigenschaft wird haeufig zur Klassifikation von Tumordaten verwendet. Diese Dissertation etabliert statistische Grundlagen fuer Clustering in hochdimensionalen Daten. Die neu eingefuehrten Methoden basieren zu grossen Teilen auf Erkenntnissen der statistischen Mechanik. Zuerst werden deshalb in Kapitel 2 grundlegende Konzepte und Algorithmen der statistischen Mechanik eingefuehrt. In Kapitel 3 wird ein neues probabilistisches Model fuer Cluster im hochdimensionalen realen Raum vorgeschlagen. Motiviert durch die Merkmale von Genexpressionsdaten werden verschiedene Observablen eines Clusters definiert: Punktdichte, Positions-Bias und Richtungsdichte. Diese Observablen messen in verschiedener Weise Aehnlichkeiten zwischen Datenpunkten und beschreiben die Hintergrundverteilung zufaelliger Datenpunkte. Daraus wird eine sogenannte Score-Funktionen fuer Cluster abgeleitet. Obwohl Gene mit aehnlicher Funktion mit hoher Wahrscheinlichkeit Cluster in Genexpressionsdaten bilden, koennen auch zufaellig verteilte Datenvektoren Cluster bilden und hohe Cluster-Scores erhalten. In Kapitel 4 wird deshalb die statistische Signifikanz fuer Cluster behandelt. Fuer die Score-Funktionen aus Kapitel 3 werden Verfahren zur Berechnung eines sogenannten p-Wertes vorgestellt. Der Funktion p(S) gibt die Wahrscheinlickeit an, dass Zufallsvektoren einen Cluster-Score von mindestens S erhalten. Dieses Problem wir mit Methoden der statistischen Mechanik ungeordenter Systeme behandelt, die zu einer analytischen Loesung fuehren. In einer Anwendung auf Genexpressionsdaten aus Hefe wird gezeigt, dass Cluster- Scores p-Werte biologische Signifikanz von co-exprimierten Genen widerspiegeln; die biologische Signifikanz wird hierbei durch Gen-Ontologie- Parameter in den betrachteten Clustern gemessen. Dies zeigt, dass Gene mit aehnlichen biologischen Funktionen in der Tat als signifikante Cluster identifiert werden. In Kapitel 5 wird ein weiterer wichtiger Aspekt statistischer Methoden fuer hochdimensionale Daten behandelt: Abhaengigkeiten zwischen Vektorkomponenten. Solche Abhaengigkeiten sind haeufig in Genexpressiondaten zu finden, beispielweise verursacht durch zeitlich aufeinanderfolgende Experimente im Rahmen von Zeitreihenexperimenten. Eine korrekte Abschaetzung solcher Abhaengigkeiten ist sowohl fuer das Clustering von experimentellen Bedingungen als auch zur Berechnung der Aehnlichkeiten von Genen von entscheidender Bedeutung. Fuer die Abschaetzung von Abhaengigkeiten von Vektorkomponenten ist die Beruecksichtigung eines wichtigen Stoerfaktors notwendig: das Vorhandensein von Clustern von Datenvektoren. Wir schlagen eine Inferenzmethode basierend auf einer Mischverteilung vor, welche das zufaellige Auftreten von Clustern vom wahren Signal trennt. In unserem Ansatz verwenden wir die probabilistischen Modelle fuer Cluster aus Kapitel 3. Wir wenden diese Methode auf das Problem der Tumorprobenklassifizierung an. In Kapitel 6 wird der Algorithmus zur Berechnung von signifikanzbasiertem Clustering vorgestellt. Der Algorithmus sucht die beste Zerlegung der Daten als Mischung von zufaelligen Datenvektoren (aus der Hintergrundverteilung) und statistisch signifikanten Clustern im Sinne unserer Theorie. Beim Auffinden von Clustern von Datenvektoren schaetzt der Algorithmus ab, welches Aehnlichkeitsmass die Abhaengigkeiten zwischen Vektorkomponenten am besten bescheibt. Des weiteren erlaubt die probabilistische Mischverteilung die Verwendung von Ausgangwahrscheinlichkeiten, die Cluster mit grossen p-Werten bestraft. In einer Anwendung auf Genexpressionsdaten von Hefe und Mensch wird gezeigt, dass dieser Mischverteilungs-Ansatz die biologische Signifikanz der erhaltenen Cluster erhoeht.
