{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:01:36Z","timestamp":1773270096596,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T00:00:00Z","timestamp":1131580800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,2]]},"DOI":"10.1007\/s10107-005-0659-3","type":"journal-article","created":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T19:57:22Z","timestamp":1131652642000},"page":"387-425","source":"Crossref","is-referenced-by-count":14,"title":["A branch-and-cut algorithm for multiple sequence alignment"],"prefix":"10.1007","volume":"105","author":[{"given":"Ernst","family":"Althaus","sequence":"first","affiliation":[]},{"given":"Alberto","family":"Caprara","sequence":"additional","affiliation":[]},{"given":"Hans-Peter","family":"Lenhof","sequence":"additional","affiliation":[]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,11,10]]},"reference":[{"key":"659_CR1","unstructured":"Achterberg, T.: SCIP - a framework to integrate constraint and mixed integer programming. Technical Report 04-19, Zuse Institute Berlin, 2004. http:\/\/www.zib.de\/bib\/pub\/pw"},{"key":"659_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215, 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"659_CR3","unstructured":"Bienstock, D.: Potential function methods for approximately solving linear programming problems, Theory and Practice. Kluwer Academic Publishers, Boston, 2002"},{"key":"659_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0167-6377(01)00106-7","volume":"30","author":"Carr","year":"2002","unstructured":"Carr, R.D., Lancia, G.: Compact vs exponential-size lp relaxations. Operations Research Letters 30, 57\u201365 (2002)","journal-title":"Operations Research Letters"},{"key":"659_CR5","doi-asserted-by":"crossref","unstructured":"Carr, R.D., Lancia, G.: Compact optimization can outperform separation: A case study in structural proteomics. 4OR 2, 221\u2013233 (2004)","DOI":"10.1007\/s10288-004-0036-8"},{"key":"659_CR6","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"Carrillo","year":"5","unstructured":"Carrillo, H., Lipman, D.J.: The multiple sequence alignment problem in biology. SIAM J. Appl. Math. 48 (5), 1073\u20131082 (1988)","journal-title":"SIAM J. Appl. Math."},{"key":"659_CR7","unstructured":"Dayhoff, M., Schwartz, R., Orcut, B.: A model of evolutionary change in proteins. In: M. Dayhoff (ed.) Atlas of Protein Sequence and Structure, vol 5, National Biomedical Research Foundation, Washington, D.C., 1979, pp 345\u2013352"},{"key":"659_CR8","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"Delcher","year":"1999","unstructured":"Delcher, A., Kasif, S., Fleischmann, R., J. Peterson, W. O., Salzberg, S.: Alignment of whole genomes. Nucleic Acids Res 27, 2369\u20132376 (1999)","journal-title":"Nucleic Acids Res"},{"key":"659_CR9","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Sequence comparison with mixed convex and concave costs. J Algorithms (11), 85\u2013101 (1990)","DOI":"10.1016\/0196-6774(90)90031-9"},{"key":"659_CR10","doi-asserted-by":"crossref","first-page":"1520","DOI":"10.1287\/mnsc.43.11.1520","volume":"43","author":"Fischetti","year":"11","unstructured":"Fischetti, M., Toth, P.: A polyhedral approach to the asymmetric traveling salesman problem. Management Sci 43 (11), 1520\u20131536 (1997)","journal-title":"Management Sci"},{"key":"659_CR11","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979"},{"key":"659_CR12","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, New York, 1980","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"659_CR13","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"Gotoh","year":"1982","unstructured":"Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol. 162, 705\u2013708 (1982)","journal-title":"J. Mol. Biol."},{"key":"659_CR14","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","volume":"2","author":"Gupta","year":"1995","unstructured":"Gupta, S., Kececioglu, J., Schaeffer, A.: Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment. J. Comput. Biol. 2, 459\u2013472 (1995)","journal-title":"J. Comput. Biol."},{"key":"659_CR15","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge, 1997","DOI":"10.1017\/CBO9780511574931"},{"key":"659_CR16","doi-asserted-by":"crossref","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","volume":"89","author":"Henikoff","year":"1992","unstructured":"Henikoff, S., Henikoff, J.: Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Science 89, 10915\u201310919 (1992)","journal-title":"Proceedings of the National Academy of Science"},{"key":"659_CR17","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"Martin","year":"1991","unstructured":"Kipp Martin, R.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10, 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"key":"659_CR18","unstructured":"Larmore, L., Schieber, B.: Online dynamic programming with applications to the prediction of rna secondary structure. In: Proceedings of the First Symposium on Discrete Algorithms 1990, pp 503\u2013512"},{"key":"659_CR19","unstructured":"LEDA (Library of Efficient Data Types and Algorithms), 2004. http:\/\/www.algorithmic-solutions.com"},{"key":"659_CR20","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1093\/bioinformatics\/15.3.203","volume":"15","author":"Lenhof","year":"3","unstructured":"Lenhof, H.-P., Morgenstern, B., Reinert, K.: An exact solution for the segment-to-segment multiple sequence alignment problem. Bioinformatics 15 (3), 203\u2013210 (1999)","journal-title":"Bioinformatics"},{"key":"659_CR21","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1089\/106652701446134","volume":"7","author":"Lermen","year":"5","unstructured":"Lermen, M., Reinert, K.: The practical use of the algorithm for exact multiple sequence alignment. J. Comput. Biol. 7(5), 655\u2013673 (2000)","journal-title":"J. Comput. Biol."},{"key":"659_CR22","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"Notredame","year":"2000","unstructured":"Notredame, C., Higgins, D.G., Heringa, J.: T-coffee : A novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302, 205\u2013217 (2000)","journal-title":"J. Mol. Biol."},{"key":"659_CR23","unstructured":"Reinert, K.: A Polyhedral Approach to Sequence Alignment Problems. PhD thesis, Universit\u00e4t des Saarlandes, 1999"},{"key":"659_CR24","doi-asserted-by":"crossref","unstructured":"Reinert, K., Lenhof, H.-P., Mutzel, P., Mehlhorn, K., Kececioglu, J.: A branch-and-cut algorithm for multiple sequence alignment. In: Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB-97), 1997, pp 241\u2013249","DOI":"10.1145\/267521.267845"},{"key":"659_CR25","doi-asserted-by":"crossref","unstructured":"K. Reinert, J. Stoye, and T. Will. An iterative methods for faster sum-of-pairs multiple sequence alignment. BIOINFORMATICS 16(9):808\u2013814, 2000.","DOI":"10.1093\/bioinformatics\/16.9.808"},{"key":"659_CR26","unstructured":"SCIL\u2013Symbolic Constraints for Integer Linear programming, 2002. http:\/\/www.mpi-sb.mpg.de\/SCIL"},{"key":"659_CR27","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","volume":"15","author":"Thompson","year":"1","unstructured":"Thompson, J.D., Plewniak, F., Poch, O.: BAliBASE: A benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15 (1), 87\u201388 (1999) http:\/\/www-igbmc.u-strasbg.fr\/BioInfo\/BAliBASE\/prog_scores.html","journal-title":"Bioinformatics"},{"key":"659_CR28","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"Wang","year":"1994","unstructured":"Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol. 1, 337\u2013348 (1994)","journal-title":"J. Comput. Biol."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0659-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0659-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0659-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T19:54:28Z","timestamp":1586548468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0659-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,10]]},"references-count":28,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["659"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0659-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11,10]]}}}