Result: Optimal protein threading by cost-splitting
Title:
Optimal protein threading by cost-splitting
Authors:
Source:
Algorithms in bioinformatics (5th international workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005, proceedings)Lecture notes in computer science. :365-375
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 20 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Bioinformatics, Bioinformatique, Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Alignement séquence, Sequence alignment, Alineación secuencia, Bioinformatique, Bioinformatics, Bioinformática, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Lagrangien, Lagrangian, Lagrangiano, Méthode polynomiale, Polynomial method, Método polinomial, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Problème combinatoire, Combinatorial problem, Problema combinatorio, Programmation en nombres entiers, Integer programming, Programación entera, Programmation mathématique, Mathematical programming, Programación matemática, Repliement, Refolding, Repliegue, Résolution problème, Problem solving, Resolución problema, Solution optimale, Optimal solution, Solución óptima
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
IRISA, Campus de Beaulieu, 35042 Rennes, France
University of Valenciennes, 59313 Valenciennes, France
University of Valenciennes, 59313 Valenciennes, France
ISSN:
0302-9743
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17265770
Database:
PASCAL Archive
Further Information
In this paper, we use integer programming approach for solving a hard combinatorial optimization problem, namely protein threading. For this sequence-to-structure alignment problem we apply cost-splitting technique to derive a new Lagrangian dual formulation. The optimal solution of the dual is sought by an algorithm of polynomial complexity. For most of the instances the dual solution provides an optimal or near-optimal (with negligible duality gap) alignment. The speed-up with respect to the widely promoted approach for solving the same problem in [17] is from 100 to 250 on computationally interesting instances. Such a performance turns computing score distributions, the heaviest task when solving PTP, into a routine operation.