A. Ernst-althaus, A. Bockmayr, M. Elf, T. Kasper, M. Jünger et al., SCIL ??? Symbolic Constraints in Integer Linear Programming, Algorithms -ESA 2002 : 10th Annual European Symposium, pp.75-87, 2002.
DOI : 10.1007/3-540-45749-6_11

E. Althaus and S. Canzar, A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem, Lecture Notes in Computer Science, vol.4616, pp.267-278, 2007.
DOI : 10.1007/978-3-540-73556-4_29

URL : https://hal.archives-ouvertes.fr/hal-00177224

E. Althaus and S. Canzar, A Lagrangian relaxation approach for the multiple sequence alignment problem, Journal of Combinatorial Optimization, vol.16, issue.2, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00177224

E. Althaus and S. Canzar, LASA: A Tool for Non-heuristic Alignment of Multiple Sequences, Proceedings of the 2nd Workshop on Algorithms in Molecular Biology, 2008.
DOI : 10.1007/978-3-540-70600-7_38

S. Ernst-althaus, K. M. Canzar, A. Elbassioni, J. Karrenbauer, and . Mestre, Approximating the Interval Constrained Coloring Problem, Lecture Notes in Computer Science, vol.5124, pp.210-221, 2008.
DOI : 10.1007/978-3-540-69903-3_20

S. Ernst-althaus, M. R. Canzar, A. Emmett, A. G. Karrenbauer, A. Marshall et al., Computing h/dexchange speeds of single residues from data of peptic fragments, SAC, pp.1273-1277, 2008.

A. Achterberg, SCIP -a framework to integrate constraint and mixed integer programming, 2004.

A. Ernst-althaus, H. Caprara, K. Lenhof, and . Reinert, Aligning multiple sequences by cutting planes, Mathematical Programming, pp.387-425, 2006.

T. [. Ahuja, J. B. Magnanti, and . Orlin, Network flows: theory, algorithms, and applications, 1993.
DOI : 10.21236/ADA594171

M. Brudno, B. Chapman, S. Göttgens, B. Batzoglou, and . Morgenstern, Fast and sensitive multiple alignment of large genomic sequences, BMC Bioinformatics, p.66, 2003.

J. E. Beasley, Lagrangian relaxation. Modern heuristic techniques for combinatorial problems, pp.243-303, 1993.

[. Bafna, E. L. Lawler, and P. A. Pevzner, Approximation algorithms for multiple sequence alignment, Theoretical Computer Science, vol.182, issue.1-2, pp.233-244, 1997.
DOI : 10.1016/S0304-3975(97)00023-6

[. Chang, T. Erlebach, R. Gailis, and S. Khuller, Broadcast scheduling, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008.
DOI : 10.1145/2000807.2000815

A. Caprara, M. Fischetti, and P. Toth, A Heuristic Method for the Set Covering Problem, Operations Research, vol.47, issue.5, pp.730-743, 1999.
DOI : 10.1287/opre.47.5.730

H. Carrillo and D. Lipman, The Multiple Sequence Alignment Problem in Biology, SIAM Journal on Applied Mathematics, vol.48, issue.5, pp.1073-1082, 1988.
DOI : 10.1137/0148063

H. Thomas, C. E. Cormen, R. L. Leiserson, C. Rivest, and . Stein, Introduction to Algorithms, Second Edition, McGraw-Hill Science/Engineering/Math, 2001.

D. [. Dantzig, S. Fulkerson, and . Johnson, Solution of a Large-Scale Traveling-Salesman Problem, Journal of the Operations Research Society of America, vol.2, issue.4, pp.393-410, 1954.
DOI : 10.1287/opre.2.4.393

]. R. Edgar, MUSCLE: multiple sequence alignment with high accuracy and high throughput, Nucleic Acids Research, vol.32, issue.5, pp.1792-1797, 2004.
DOI : 10.1093/nar/gkh340

URL : https://academic.oup.com/nar/article-pdf/32/5/1792/7055030/gkh340.pdf

D. Eppstein, Sequence comparison with mixed convex and concave costs, Journal of Algorithms, vol.11, issue.1, pp.85-101, 1990.
DOI : 10.1016/0196-6774(90)90031-9

[. Elbassioni and R. Raman, Saurabh Ray, and René Sitters. On the approximability of the maximum feasible subsystem problem with 0/1 coefficients . submitted, 2008.

M. Khaled, R. Elbassioni, Y. Sitters, and . Zhang, A quasi-PTAS for profit-maximizing pricing on line graphs, Proceedings of the 15th Annual European Symposium on Algorithms, pp.451-462, 2007.

L. Marshall and . Fisher, Comments on " the lagrangian relaxation method for solving integer programming problems, Manage. Sci, vol.50, issue.12

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979.

]. M. Gj79b, D. S. Garey, and . Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM, vol.53, issue.3, pp.324-360, 2006.
DOI : 10.1145/1147954.1147956

K. Sandeep, J. D. Gupta, A. A. Kececioglu, and . Schäffer, Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment, Journal of Computational Biology, vol.2, issue.3, pp.459-472, 1995.

]. S. Gks95b, J. D. Gupta, A. A. Kececioglu, and . Schaeffer, Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment, J. Comput. Biol, vol.2, pp.459-472, 1995.

D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, 1997.
DOI : 10.1017/CBO9780511574931

J. Håstad, Some optimal inapproximability results, STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp.1-10, 1997.

M. Held, R. M. Karp, and R. M. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees, Mathematical Programming, pp.1138-11626, 1970.
DOI : 10.1287/opre.18.6.1138

[. , I. Ilog, and . Cplex, High-performance software for mathematical programming and optimization, 2006.

[. Just, Computational Complexity of Multiple Sequence Alignment with SP-Score, Journal of Computational Biology, vol.8, issue.6, pp.615-623, 2001.
DOI : 10.1089/106652701753307511

]. S. Khj-+-06, A. M. Kang, K. L. Hawkridge, D. C. Johnson, P. E. Muddiman et al., Identification of subunit-subunit interactions in bacteriophage p22 procapsids by chemical cross-linking and mass spectrometry, Journal of Proteome Research, vol.5, issue.2, pp.370-377, 2006.

[. Katoh, H. Kei-ichi-kuma, T. Toh, and . Miyata, MAFFT version 5: improvement in accuracy of multiple sequence alignment, Nucleic Acids Research, vol.33, issue.2, p.511, 2005.
DOI : 10.1093/nar/gki198

S. [. Lipman, J. D. Altschul, and . Kececioglu, A tool for multiple sequence alignment., Proceedings of the National Academy of Sciences, vol.86, issue.12, pp.4412-4415, 1989.
DOI : 10.1073/pnas.86.12.4412

C. Lemaréchal, Lagrangian relaxation Multiple sequence alignment using partial order graphs, Computational Combinatorial Optimization, volume 2241 of Lecture Notes in Computer Science, pp.112-156452, 2001.

. T. Lle-+-02-]-t, J. K. Lam, M. R. Lanman, C. L. Emmett, M. A. Hendrickson et al., Mapping of protein:protein contact surfaces by hydrogen/deuterium exchange, followed by on-line high-performance liquid chromatography-electrospray ionization fourier-transform ion-cyclotronresonance mass analysis, Journal of Chromatography A, vol.982, issue.1, pp.85-95, 2002.

M. Lermen and K. Reinert, * Algorithm for Exact Multiple Sequence Alignment, Journal of Computational Biology, vol.7, issue.5, pp.655-673, 2000.
DOI : 10.1089/106652701446134

B. [. Larmore and . Schieber, Online dynamic programming with applications to the prediction of RNA secondary structure, Proceedings of the First Symposium on Discrete Algorithms, pp.503-512, 1990.

]. A. Luc92 and . Lucena, Steiner problem in graphs: Lagrangean relaxation and cuttingplanes, COAL Bulletin, vol.21, pp.2-8, 1992.

]. A. Luc93 and . Lucena, Tight bounds for the steiner problem in graphs, Dipartimento di Informatica, 1993.

K. Mehlhorn and S. Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, vol.38, issue.1, pp.96-102, 1995.
DOI : 10.1145/204865.204889

D. [. Notredame, J. Higgins, and . Heringa, T-coffee: a novel method for fast and accurate multiple sequence alignment 1 1Edited by J. Thornton, Journal of Molecular Biology, vol.302, issue.1, pp.205-217, 2000.
DOI : 10.1006/jmbi.2000.4042

C. Papadimitriou and M. Yannakakis, Optimization, approximation , and complexity classes, STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp.229-234, 1988.

]. K. Rei99 and . Reinert, A Polyhedral Approach to Sequence Alignment Problems, 1999.

J. S. Sharp, J. M. Becker, and R. L. Hettich, Analysis of Protein Solvent Accessible Surfaces by Photochemical Oxidation and Mass Spectrometry, Analytical Chemistry, vol.76, issue.3, pp.672-683, 2004.
DOI : 10.1021/ac0302004

D. [. Stoye, F. Evers, and . Meyer, Rose: generating sequence families, Bioinformatics, vol.14, issue.2, pp.157-163, 1998.
DOI : 10.1093/bioinformatics/14.2.157

]. J. Thg94a, D. G. Thompson, T. J. Higgins, and . Gibson, CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice, Nucleic Acids Res, vol.22, issue.22, pp.4673-4680, 1994.

]. J. Thg94b, D. G. Thompson, T. J. Higgins, and . Gibson, CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice, Nucleic Acids Research, vol.22, pp.4673-4680, 1994.

F. [. Thompson, O. Plewniak, and . Poch, BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs, Bioinformatics, vol.15, issue.1, pp.87-88, 1999.
DOI : 10.1093/bioinformatics/15.1.87

T. Uno, A Fast Algorithm for Enumerating Bipartite Perfect Matchings, Proceedings of the 12th International Conference Algorithms and Computation, pp.367-379, 2001.
DOI : 10.1007/3-540-48686-0_35

T. [. Wang and . Jiang, On the Complexity of Multiple Sequence Alignment, Journal of Computational Biology, vol.1, issue.4, pp.337-348, 1994.
DOI : 10.1089/cmb.1994.1.337

[. Van-walle, I. Lasters, and L. Wyns, SABmark--a benchmark for sequence alignment that covers the entire known fold space, Bioinformatics, vol.20, issue.9, pp.1267-1268, 2005.
DOI : 10.1093/bioinformatics/bth116

A. Laurence and . Wolsey, Integer programming. Wiley-interscience series in discrete mathematics and optimization, 1998.

[. Wunderling, Paralleler und objektorientierter Simplex- Algorithmus, 1996.

S. [. Zhang, A. G. Guan, and . Marshall, Enhancement of the effective resolution of mass spectra of high-mass biomolecules by maximum entropy-based deconvolution to eliminate the isotopic natural abundance distribution, Journal of the American Society for Mass Spectrometry, vol.6, issue.138, pp.659-670, 1997.
DOI : 10.1016/1044-0305(95)00017-8

]. E. Zui02 and . Zuiderweg, Mapping protein-protein interactions in solution by nmr spectroscopy, Biochemistry, vol.41, issue.1, pp.1-7, 2002.