Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11557067_30 | WABI |
Keywords | Field | DocType |
optimal protein,polynomial complexity,negligible duality gap,heaviest task,hard combinatorial optimization problem,optimal solution,new lagrangian dual formulation,dual solution,sequence-to-structure alignment problem,integer programming approach,computationally interesting instance,protein threading,structure alignment | Duality gap,Mathematical optimization,Combinatorics,Combinatorial optimization problem,Lagrangian,Computer science,Threading (protein sequence),Algorithm,Combinatorial optimization,Integer programming,Polynomial complexity,Lagrangian relaxation | Conference |
Volume | ISSN | ISBN |
3692 | 0302-9743 | 3-540-29008-7 |
Citations | PageRank | References |
5 | 0.41 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. Veber | 1 | 5 | 0.41 |
| N. Yanev | 2 | 32 | 2.92 |
| R. Andonov | 3 | 51 | 5.97 |
| Vincent Poirriez | 4 | 89 | 7.64 |