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

News

  • Additional info on the input under Topic
  • Open Graph Drawing Framework might be of use
  • On Monday, 23.05.2016 we will discuss both, the state of your pebble game implementations (show us what you did) and the final project for you to work on during the semester.
  • added ABBIE paper under "the real project"
  • data base with molecules under "the real project"

    Topic

    Topic: Rigid graphs and 3D embeddings of graphs

  • When can an object determined by internal distances be embedded in space?
  • What if only a some distances are given?
  • The input is the set of all pairwise distances between atoms. We have distances between atoms independent of if there is an actual chemical bond or not. (For example, we have three distances between the atoms in H2O).
  • From this upper triangular matrix of all pairwise distances, we then only have a subset of distances availables (Randomly drawn. Say, for H2O, we have the distance H-1 to O, and H-1 to H-2).
  • Then we run the pebble game and the force field embedder (cf. the ABBIE paper and Lee, 2007, as well as the other papers).
  • For the final embedding (or embeddings in case of ambiguities) of atoms in 3-space, we are then able to deduce actual chemical bonds. This will depend on distances and angles between atoms.
    • These questions directly lead to rigidity theory. We will first consider the 2D case in some detail:

    PDF

    As it turns out, the 3D case is difficult in general
    PFDF   LINK   LINK  

    Warm-up project:

  • For a given graph, determine whether it is rigid in 2D. If not, find its ridig components.
  • Embed a rigid 2D graph in the plane. (a) in the minimally rigid case, (b) in the stressed case.
    • Original 2D algorithm by Jacobs and Hendrickson: [    PDF]

    The real project

    ... now we try the same in 3D ...
  • General theory of pebble games [PDF] ( Discr. Math 308: 1425-1437 (2008)
  • 3D body-and-bar pebble game [PDF]
  • another interesting paper [PDF]
  • The ABBIE paper [PDF]
  • the pubchem database has many molecules in SDF format (download, 3d conformer, sdf) which is pretty self-explanatory [water] and [caffeine (requires 'N')], as well as ketene
  • pubchem has 2d conformer sdf files as well. These provide all molecular bounds, but only two of the three dimensions are 'correct'. This should help with the 3d embedding
  • we do not provide an 'official' format, but suggest sdf for now as it is used by pubchem for molecule data

    Registration

    Hier regestrieren!

    Vorlesung und Praktikum

    Fortgeschrittene Methoden in der Bioinformatik

    Uhrzeit:14-17 Uhr
    Vorlesung:Raum 109, Härtelstr. 16-18 Termine siehe Tabelle unten
    Praktikum:Raum 109, Härtelstr. 16-18
    Prüfungto be announced

    VLDatumRaumZeit
    11.04.16 (Montag) R 109 14:00 The embedding problem; molecules; rigidity in 2D
    18.04.16 (Montag) R 109 14:00
    25.04.16 (Montag) R 109 14:00
    02.05.16 (Montag) R 109 14:00
    09.05.16 (Montag) R 109 14:00 ABBIE (Hendrickson)
    23.05.16 (Montag) R 109 14:00 Pebble game and final project discussion

    Literatur

    to be announced

    Gruppen

  • Yves Amanias, Kathleen Wende, Jeremias Schelera, Marcel Winter
  • Marius Brunnert, Simon Johanning, Kai Hainke
  • Alexander Engler, Markus Michaelis, Christian Heide, Sophie Wolf
  • Michael Rode, Alexander Scholz, Joerg Walter, Anastasia Wolschewski
  • Deisy Gysi, Janine Rauch, Jiehang Li (?)
  • Fei Pu, Adarclys Andrades, Ye Chen