Algorithm engineering for optimal alignment of protein structure distance matrices

Inken Wohlers 1, * Rumen Andonov 2 Gunnar W. Klau 1
* Auteur correspondant
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.
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00586067
Contributeur : Inken Wohlers <>
Soumis le : vendredi 15 avril 2011 - 10:53:19
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : samedi 16 juillet 2011 - 02:30:23

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Inken Wohlers, Rumen Andonov, Gunnar W. Klau. Algorithm engineering for optimal alignment of protein structure distance matrices. Optimization Letters, Springer Verlag, 2011, 〈http://www.springerlink.com/content/86625t062m213141/〉. 〈10.1007/s11590-011-0313-3〉. 〈inria-00586067〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

251