Skip to Main content Skip to Navigation
Journal articles

Algorithm engineering for optimal alignment of protein structure distance matrices

Inken Wohlers 1, * Rumen Andonov 2 Gunnar W. Klau 1
* Corresponding author
2 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Protein structural alignment is an important problem in computational biology. In this paper, we present first successes on provably optimal pairwise alignment of protein inter-residue distance matrices, using the popular Dali scoring function. We introduce the structural alignment problem formally, which enables us to express a variety of scoring functions used in previous work as special cases in a unified framework. Further, we propose the first mathematical model for computing optimal structural alignments based on dense inter-residue distance matrices. We therefore reformulate the problem as a special graph problem and give a tight integer linear programming model. We then present algorithm engineering techniques to handle the huge integer linear programs of real-life distance matrix alignment problems. Applying these techniques, we can compute provably optimal Dali alignments for the very first time.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Inken Wohlers <>
Submitted on : Friday, April 15, 2011 - 10:53:19 AM
Last modification on : Friday, July 10, 2020 - 4:24:39 PM
Long-term archiving on: : Saturday, July 16, 2011 - 2:30:23 AM


Files produced by the author(s)



Inken Wohlers, Rumen Andonov, Gunnar W. Klau. Algorithm engineering for optimal alignment of protein structure distance matrices. Optimization Letters, Springer Verlag, 2011, ⟨10.1007/s11590-011-0313-3⟩. ⟨inria-00586067⟩



Record views


Files downloads