HAL - INRIA :: [inria-00090635, version 2] Lagrangian Approaches for a class of Matching Problems in Computational Biology

inria-00090635, version 2

Lagrangian Approaches for a class of Matching Problems in Computational Biology

Nicola Yanev ()^a^, 1, Rumen Andonov ()^b^, 1, Philippe Veber^c^, 1, Stefan Balev ()^d^, 2

N° RR-5973 (2006)

Abstract: This paper presents efficient algorithms for solving the problem of aligning a protein structure template to a query amino-acid sequence, known as protein threading problem. We consider the problem as a special case of graph matching problem. We give formal graph and integer programming models of the problem. After studying the properties of these models, we propose two kinds of Lagrangian relaxation for solving them. We present experimental results on real life instances showing the efficiency of our approaches.

a – University of Sophia
b – Université Rennes I
c – INRIA
d – Université du Havre
1: SYMBIOSE (INRIA - IRISA)
CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
2: Laboratoire d'informatique du Havre (LIH EA3219)
Université du Havre

inria-00090635, version 2
http://hal.inria.fr/inria-00090635
oai:hal.inria.fr:inria-00090635
From: Rapport De Recherche Inria <>
Submitted on: Thursday, 7 September 2006 15:00:35
Updated on: Thursday, 7 September 2006 15:04:36

See detailed view

Associated documents

PS :

PDF :

arXiv: q-bio.QM/0609001

Export

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="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00090635"><monogr>
<author><persName><forename>Nicola</forename><surname>Yanev</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">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</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">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Philippe</forename><surname>Veber</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">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Stefan</forename><surname>Balev</surname></persName>
<affiliation>
<orgName type="laboratory">LIH EA3219</orgName>
<orgName type="team">Laboratoire d'informatique du Havre</orgName>
<country>FR</country>
<orgName type="institution">Université du Havre</orgName>
</affiliation>
</author>
<title type="main" level="m">Lagrangian Approaches for a class of Matching Problems in Computational Biology</title><title type="main" level="m">Lagrangian Approaches for a class of Matching Problems in Computational Biology</title><imprint><biblScope type="publicationDate">2006-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00090635</idno><idno type="HALFile">http://hal.inria.fr/inria-00090635/PDF/RR-5973.pdf</idno></biblStruct>
</listBibl>
</listBibl>