Local protein threading by Mixed Integer Programming

Guillaume Collet 1 Rumen Andonov 2, * Jean-François Gibrat 3 Nicola Yanev 4
* Corresponding author
1 LCV - Laboratoire Chimie pour le Vivant, ingénierie moléculaire pour la santé
SIMOPRO - Service d'Ingénierie Moléculaire des Protéines : DRF/JOLIOT
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 : During the last decade, significant progress has been made in solving the Protein Threading Problem (PTP). However, all previous approaches to PTP only perform global sequencestructure alignment. This obvious limitation is in clear contrast with the world of sequences, where local sequencesequence alignments are widely used to find functionally important regions in families of proteins. This paper presents a novel approach to PTP which allows to align a part of a protein structure onto a protein sequence in order to detect local similarities. We show experimentally that such local sequence-structure alignments improve the quality of the prediction. Our approach is based on Mixed Integer Programming (MIP) which has been shown to be very successful in this domain. We describe five MIP models for local sequence-structure alignments, compare and analyze their performances by using ILOG CPLEX 10 solver on a benchmark of proteins.
Complete list of metadatas

https://hal.inria.fr/inria-00536537
Contributor : Rumen Andonov <>
Submitted on : Monday, November 29, 2010 - 12:44:49 PM
Last modification on : Friday, April 12, 2019 - 1:33:15 PM

Links full text

Identifiers

Citation

Guillaume Collet, Rumen Andonov, Jean-François Gibrat, Nicola Yanev. Local protein threading by Mixed Integer Programming. Discrete Applied Mathematics, Elsevier, 2011, 159 (16), pp.1707-1716. ⟨10.1016/j.dam.2010.05.024⟩. ⟨inria-00536537⟩

Share

Metrics

Record views

325