Local protein threading by Mixed Integer Programming

Guillaume Collet; Rumen Andonov; Jean-François Gibrat; Nicola Yanev

inria-00536537, version 1

Local protein threading by Mixed Integer Programming

Guillaume Collet^a^, 1, Rumen Andonov ( Auteur à contacter de préférence )^a^, 2, Jean-François Gibrat () ³, Nicola Yanev () ⁴

Discrete Applied Mathematics 159, 16 (2011) 1707-1716

Résumé : 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.

a – Université de Rennes I
1 : Laboratoire Chimie pour le Vivant (LCV)
CEA : DSV/IBITECS
2 : SYMBIOSE (INRIA - IRISA)
CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
3 : Unité Mathématique Informatique et Génome (MIG)
Institut national de la recherche agronomique (INRA)
4 : University of Sofia
Bulgarian Academy of Sciences

inria-00536537, version 1
http://hal.inria.fr/inria-00536537
oai:hal.inria.fr:inria-00536537
Contributeur : Rumen Andonov <>
Soumis le : Lundi 29 Novembre 2010, 12:44:49
Dernière modification le : Lundi 21 Novembre 2011, 15:52:50

Voir la fiche détaillée

Documents associés

DOI : 10.1016/j.dam.2010.05.024

Texte intégral chez l'éditeur

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00536537"><analytic>
<author><persName><forename>Guillaume</forename><surname>Collet</surname></persName>
<affiliation>
<orgName type="laboratory">LCV</orgName>
<orgName type="team">Laboratoire Chimie pour le Vivant</orgName>
<country>FR</country>
<orgName type="institution">CEA : DSV/IBITECS</orgName>
</affiliation>
</author>
<author><persName><forename>Rumen</forename><surname>Andonov</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">SYMBIOSE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-François</forename><surname>Gibrat</surname></persName>
<affiliation>
<orgName type="laboratory">MIG</orgName>
<orgName type="team">Unité Mathématique Informatique et Génome</orgName>
<country>FR</country>
<orgName type="institution">Institut national de la recherche agronomique (INRA)</orgName>
</affiliation>
</author>
<author><persName><forename>Nicola</forename><surname>Yanev</surname></persName>
<affiliation>
<orgName type="team">University of Sofia</orgName>
<country>BG</country>
<orgName type="institution">Bulgarian Academy of Sciences</orgName>
</affiliation>
</author>
<title type="main" level="a">Local protein threading by Mixed Integer Programming</title></analytic><monogr><title level="j" type="main">Discrete Applied Mathematics</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="vol">159</biblScope><biblScope type="issue">16</biblScope><biblScope type="pp">1707-1716</biblScope></imprint></monogr><idno type="doi">10.1016/j.dam.2010.05.024</idno><idno type="HALid">http://hal.inria.fr/inria-00536537</idno></biblStruct>
</listBibl>
</listBibl>