## Invited Session Tue.2.H 2033

#### Tuesday, 13:15 - 14:45 h, Room: H 2033

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

### Bioinformatics and combinatorial optimization II

**Chair: Gunnar W. Klau**

**Tuesday, 13:15 - 13:40 h, Room: H 2033, Talk 1**

**Johannes Köster**

Protein hypernetworks

**Coauthors: Sven Rahmann, Eli Zamir**

**Abstract:**

Protein interactions are fundamental building blocks of biochemical reaction systems underlying cellular functions.

The complexity and functionality of such systems emerge not only from the protein interactions themselves but mainly from the dependencies between these interactions, e.g., due to allosteric regulation or steric hindrance.

Therefore, a comprehensive approach for integrating and using

information about such dependencies is required.

We present an approach for endowing protein networks with interaction dependencies using propositional logic, thereby obtaining protein hypernetworks.

As can be expected, this framework straightforwardly improves the prediction of protein complexes.

We found that modeling protein perturbations in hypernetworks, rather

than in networks, allows to better infer also the functional necessity

and synthetic lethality of proteins in yeast.

**Tuesday, 13:45 - 14:10 h, Room: H 2033, Talk 2**

**Gunnar W. Klau**

Charge group partitioning in biomolecular simulation

**Coauthors: Stefan Canzar, Mohammed El-Kebir, Khaled Elbassioni, Daan Geerke, Alpesh Malde, Alan Mark, René Pool, Leen Stougie**

**Abstract:**

Molecular simulation techniques are increasingly being used to study biomolecular systems at an atomic level. Such simulations rely on empirical force fields to represent the intermolecular interactions. There are many different force fields available, each based on a different set of assumptions and thus requiring different parametrization

procedures. Recently, efforts have been made to fully automate the assignment of

force-field parameters, including atomic partial charges, for novel molecules. In this work, we focus on a problem arising in the automated parametrization of molecules for use in combination with the GROMOS family of force fields: namely, the assignment of atoms to charge groups such that for every charge group the sum of the partial charges is ideally equal to its formal charge. In addition, charge groups are required to have size at most *k*. We show NP-hardness and give an exact algorithm capable of solving

practical problem instances to provable optimality in a fraction of a second.

**Tuesday, 14:15 - 14:40 h, Room: H 2033, Talk 3**

**Rumen Andonov**

Optimal DALI protein structure alignment

**Coauthors: Gunnar W. Klau, Inken Wohlers**

**Abstract:**

We present a mathematical model and exact algorithm for optimally aligning protein structures using DALI score, which is an NP-hard problem. DALI score is based on comparing the inter-residue distance matrices of proteins, and is the scoring model of a widely used heuristic. We extend an integer linear programming approach which has been previously applied for the related, but simpler, contact map overlap problem. To this end, we introduce a novel type of constraint that handles negative score values and relax it in a Lagrangian fashion. The new exact algorithm is thus applicable to any distance matrix-based scoring scheme. Using four known data sets of varying structural similarity, we compute many provably optimal alignments. Thus, for the first time, we evaluate and benchmark the popular heuristic in sound mathematical terms. The results indicate that usually the heuristic computes optimal or close to optimal alignments. However, we detect an important subset of small proteins for which DALI fails to generate any significant alignment, although such alignments do exist.