Fortgeschrittene Methoden in der Bioinformatik (10-INF-BIO4)

Thema: Graph Alignments

Themenübersicht der Vorlesungen

VLDatumRaumUhrzeitThemaLiteratur
VL 01Mo 01.04.19 R 109 14:00-17:00 Formale Struktur von Alignments
VL 02Fr 05.04.19 R 109 14:00-17:30 Verallgemeinerung des Alignment Begriffs Manuscript
VL 03Mo 08.04.19 R 109 14:00-17:00 Maximum Induced Subgraphs H. G. Barrow, R. M. Burstall, Subgraph isomorphism, matching relational structures and maximal cliques, Inf. Proc. Lett. 4 (1976) 83–84.
Duesbury, E., Holliday, J.D. and Willett, P. Maximum Common Subgraph Isomorphism Algorithms. MATCH Communications in Mathematical and in Computer Chemistry, 77 (2). pp. 213-232.
VL 04Fr 12.04.19 R 109 14:00-17:30 Efficient Maximal Clique Enumeration A note on the problem of reporting maximal cliques. F.Cazals, C.Karande. Theor. Comp. Sci. 407: 564-568 (2008).
VL 05Mo 15.04.198 R 109 14:00-17:00 Subgraph-Isomorphie An Improved Algorithm for Matching Large Graphs, LP Cordella, P Foggia, M Vento. 3rd IAPR-TC15 workshop on graph-based representations in pattern recognition. 2001
Besprechung 1Mo 06.05.19 R 109 14:00-17:00 Format fuer Graphen; Implementation des ersten Algorithmus; Probleme?

Aufgaben

(2019-08-19: nochmal Aufgaben zusammengefasst)
  • generisches Tool fuer progressive, multiple Graph-Alignments
  • Input: eine Menge von Graphen (V,E,c,f): V: Vertices, E: Edges, c: vertex labels, f: edge labels
    • vertex und edge labels sind optional
    • Graphen koennen gerichtet oder ungerichtet sein, bei ungerichteten Graphen soll es reichen nur {a,b} anzugeben, also nicht (a,b), (b,a) noetig sein
  • progressiv: definiere paarweise Graph-Alignments als 'maximal common induced subgraph alignments'
  • Regeln welche Knoten nach ihren labels 'c' und welche Kanten nach ihren label 'f' matchen duerfen
  • Implementation von
    • B.-K. mit pivoting
    • Matching basiert auf Cordella
  • (viel) spaeter: Vergleich zufaeeliger guide tree vs greedy trees ala clustal
  • Ausrechnen: Graph-Aehnlichkeiten, Tool oder selbst ausrechnen
  • Beispieldaten: erstmal selbst bauen!
  • "erstmal selbst bauen" heisst: Tool das zufaellige, kleine Graphen generiert. Extra: "regelmaessige Graphen" mit fehlenden Knoten+Kanten (zB Schachbrett-artig) generieren
  • chemische Graphstrukturen aus der pubchem verarbeiten in multiplen Alignments

Wichtig

ab 14.06.2019
Chemische Graphstrukturen
  • Graphstrukturen chemischer Molekuele: die pubChem enthaelt viele Strukturen, hier das Beispiel Aspirin.
  • Nehmt eine Menge (>2) von Molekuelen, zB Aspirin-Aehnliche und downloaded die 2D Struktur.
  • Schreibt oder benutzt einen Parser fuer eines der gegebenen Formate um die Graphstruktur zu generieren. Beachtet die Codierung der Elements und Bonds, so das die Labels passen.
  • Konstruiert multiple Alignments von interessanten Molekuelen.
Grosse Graphen
  • Hier Stanford Large Network Dataset Collection ist eine Datenbank mit grossen Netzweken.
  • Einige Graphen sind eventuell klein genug, um interessante Fragen zu stellen, wie "Gibt es K_n (vollstaendige Graphen mit n Knoten) im Facebook graph?
  • Achtung: die Graphen sind so gross, das die Algorithmen eventuell nicht in vertretbarer Zeit terminieren!
ab 13.04.2019
  • Gruppen bis max. 3 Teilnehmer
  • Freie Wahl der Programmiersprache pro Gruppe
  • Dies ist kein Programmierkurs, sie sollten die Sprache der Wahl bereits beherrschen

Literatur

Daten