Markov Cluster Algorithmus

In dieser Vorlesung lernen wir ein Verfahren des Graphen-Clustering kennen, das sogenannte Markov Clustering (MCL). Über das Modell des Clusterings in einem Flussnetzwerk sehen wir uns zunächst an, wie Knoten in Teilgraphen mit starken Verbindungen durch die Simulation zufälliger Läufe im Netzwerk ermittelt werden können. Schließelich stellen wir fest, dass die Zerlegung in stark miteinander verbundene Teilgraphen schrittweise über die Matrixmultiplikation (Expansion) mit anschließender Inflationsoperation möglich ist. Das Verfahren erlaubt die Zerlegung von Millionen von Proteinsequenzen über ihre paarweise Ähnlichkeit in Proteinfamilien.