The interaction of proteins is mainly determined by their spatial structure. Hence, it is essential to understand how the chain of chemical components that constitute a protein is folded in the three-dimensional space. Hydrogen Deuterium Exchange (HDX) experiments are used to examine the solvent accesibility of the surface of a proteine and thereby to obtain information about the spatial structure. To this end, a protein is put into heavy water, and the amount of deuterium atoms that have exchanged with residual hydrogen atoms are measured for several timesteps. This can be achieved by mass spectroscopy after digesting, i.e. cutting, the protein into fragments. However, this method only provides only bulk information on the fragments. But there are a lot of overlapping fragments since the digestion does not always happen at the same places. By solving the so-called interval constrained coloring problem, exchange rates of single residues can be computed out of the bulk data.
Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità, “The interval constrained 3-coloring problem“, LATIN, 2010, accepted
E. Althaus, S. Canzar, C. Ehrler, M. R. Emmett, A. Karrenbauer, A. G. Marshall, A. Meyer-Baese, J. Tipton, H. Zhang, “Discrete Fitting of HDX-data of Overlapping Fragments”, BIOCOMP, 2009
E. Althaus, S. Canzar, K. Elbassioni, A. Karrenbauer, J. Mestre, “Approximating the interval constrained coloring problem“, SWAT, 2008, pp. 210-221
E. Althaus, S. Canzar, M. R. Emmett, A. Karrenbauer, A. G. Marshall, A. Meyer-Baese, H. Zhang, “Computing of H/D-Exchange Speeds of Single Residues form Data of Peptic Fragments”, SAC, 2008, pp. 1273-1277