Skip to Main content Skip to Navigation
Journal articles

DALIX: optimal DALI protein structure alignment

Inken Wohlers 1, * Rumen Andonov 2 Gunnar W. Klau 1
* Corresponding author
2 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
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.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00685824
Contributor : Rumen Andonov <>
Submitted on : Thursday, April 26, 2012 - 2:29:04 AM
Last modification on : Thursday, December 19, 2019 - 1:10:03 AM
Document(s) archivé(s) le : Friday, July 27, 2012 - 2:22:57 AM

File

RR-7915.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00685824, version 2

Relations

Citation

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

Share

Metrics

Record views

595

Files downloads

571