Invited Session Fri.2.MA 376

Friday, 13:15 - 14:45 h, Room: MA 376

Cluster 12: Life sciences & healthcare [...]

Cell biology


Chair: Stefan Canzar



Friday, 13:15 - 13:40 h, Room: MA 376, Talk 1

Xin Gao
Towards automatic NMR protein structure determination


Protein three-dimensional structure determination is the key towards the understanding of protein functions. Nuclear magnetic resonance (NMR) is one of the two main methods for protein structure determination. Current processes are time consuming and heavily depend on expert knowledge. If we could fully automate this process, this would significantly speedup the structural biology research. In this talk, we will identify the key obstacles in this process and propose solutions by computational methods. We developed peak picking methods based on signal processing techniques, a resonance assignment method based on optimization techniques, and a structure calculation method based on machine learning techniques. Each of these methods subtly handles the noise and imperfection of the others and significantly outperforms the state-of-the-art approaches. Our final system has succeeded in determining high resolution protein structures from a small set of NMR spectra, in a day.



Friday, 13:45 - 14:10 h, Room: MA 376, Talk 2

Julian Mestre
Tree-constrained matching

Coauthors: Stefan Canzar, Khaled Elbassioni, Gunnar W. Klau


We study a generalization of maximum weight bipartite matching, where
we are given in addition trees over each side of the bipartition and
we add the additional requirement that the matched vertices on each
side are not comparable under the ancestor-descendant relation. The
problem arises in the interpretation of live cell video data. We give
approximation algorithms and hardness for the problem.
Our algorithm is based on the fractional local ratio technique. In
order to obtain a good approximation ratio we uncover and exploit
properties of the extreme points of a linear program formulation
for our problem.



Friday, 14:15 - 14:40 h, Room: MA 376, Talk 3

Sandro Andreotti
De novo peptide sequencing with mathematical programming

Coauthors: Gunnar W. Klau, Knut Reinert


Peptide sequencing from mass spectrometry data is a key step in proteome research. Especially de novo sequencing, the identification of a peptide from its spectrum alone, is still a challenging problem.
We developed a fast and flexible algorithm based on mathematical programming.
It builds on the widely used spectrum graph model and can be combined with a variety of scoring schemes.
In the graph theoretical formulation the problem corresponds to the longest antisymmetric path problem in a directed acyclic graph.
Other algorithms like PepNovo or NovoHMM can solve this problem only for the special case where conflicting node-pairs are non-interleaving.
We combine Lagrangian relaxation with an adaptation of Yen's k-shortest paths algorithm to compute suboptimal solutions.
This approach shows a significant improvement in running time compared to mixed integer optimization approach with previous solutions being cut off using additional constraints and performs at the same speed like existing de novo sequencing tools.
Further we implement a generic probabilistic scoring scheme that can be trained for a dataset of annotated spectra and is independent of the mass spectrometer type.


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.