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

**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.

Talk 3 of the invited session Tue.2.H 2033

**"Bioinformatics and combinatorial optimization II"** [...]

Cluster 12

**"Life sciences & healthcare"** [...]