DALIX: optimal DALI protein structure alignment - Archive ouverte HAL Access content directly
Journal Articles IEEE/ACM Transactions on Computational Biology and Bioinformatics Year : 2013

DALIX: optimal DALI protein structure alignment

(1) , (2) , (1)
1
2

Abstract

We present a mathematical model and exact algorithm for protein structure alignment using dali scoring, which is an NP-hard problem. dali scoring is based on comparing the inter-residue distance matrices of proteins and is the scoring model of the widely used heuristic dali program. Our model and algorithm extend an integer linear programming approach previously used for the related contact map overlap problem. To this end, we introduce a novel type of constraint that handles negative structure scores and relax it in a Lagrangian fashion. We also review options that allow to consider less pairs of inter-residue distances explicitly, because their large number makes it difficult to optimize dali scoring optimally. We use our exact algorithm DALIX to compute many provably score-optimal DALI alignments for the first time, using four data sets of varying structural similarity. Further, using our exact DALIX alignments, it is for the very first time possible to qualitatively benchmark the heuristic DALI program in sound mathemat- ical terms. The results indicate that DALI often computes optimal or close to optimal alignments, but also that in cases of aligning small proteins it tends to fail generating any significant alignment although such an alignment exists.
L'article présente le modèle mathématique et un algorithme exacte pour aligner des structures protéiques à la base du score DALI.
Fichier principal
Vignette du fichier
RR-7915.pdf (431.31 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00685824 , version 1 (06-04-2012)
hal-00685824 , version 2 (26-04-2012)

Identifiers

  • HAL Id : hal-00685824 , version 2

Cite

Inken Wohlers, Rumen Andonov, Gunnar W. Klau. DALIX: optimal DALI protein structure alignment . IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2013, IEEE/ACM Transactions on Computational Biology and Bioinformatics 10 (1), pp.20. ⟨hal-00685824v2⟩
297 View
614 Download

Share

Gmail Facebook Twitter LinkedIn More