## 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

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üfung** | | to be announced |

VL | Datum | Raum | Zeit |

| 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