{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T10:04:38Z","timestamp":1746007478439},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s10878-008-9139-z","type":"journal-article","created":{"date-parts":[[2008,3,4]],"date-time":"2008-03-04T17:40:46Z","timestamp":1204652446000},"page":"127-154","source":"Crossref","is-referenced-by-count":6,"title":["A Lagrangian relaxation approach for the multiple sequence alignment problem"],"prefix":"10.1007","volume":"16","author":[{"given":"Ernst","family":"Althaus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Canzar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,5]]},"reference":[{"key":"9139_CR1","series-title":"Bioinformatics","first-page":"S4","volume-title":"Proceedings of the European conference on computational biology, Saarbr\u00fccken, October 2002","author":"E Althaus","year":"2002","unstructured":"Althaus E, Caprara A, Lenhof H-P, Reinert K (2002) Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics. In: Lengauer T, Lenhof H-P (eds) Proceedings of the European conference on computational biology, Saarbr\u00fccken, October 2002. Bioinformatics, vol 18. Oxford University Press, London, pp S4\u2013S16"},{"key":"9139_CR2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s10107-005-0659-3","volume":"105","author":"E Althaus","year":"2006","unstructured":"Althaus E, Caprara A, Lenhof H-P, Reinert K (2006) A branch-and-cut algorithm for multiple sequence alignment. Math Program 105:387\u2013425","journal-title":"Math Program"},{"key":"9139_CR3","volume-title":"Modern heuristic techniques for combinatorial problems","author":"J Beasley","year":"1993","unstructured":"Beasley J (1993) Lagrangian relaxation. In: Modern heuristic techniques for combinatorial problems. Blackwell Scientific, Oxford"},{"key":"9139_CR4","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","volume":"47","author":"A Caprara","year":"1999","unstructured":"Caprara A, Fischetti M, Toth P (1999) A heuristic method for the set cover problem. Oper Res 47:730\u2013743","journal-title":"Oper Res"},{"issue":"5","key":"9139_CR5","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo H, Lipman DJ (1988) The multiple sequence alignment problem in biology. SIAM J Appl Math 48(5):1073\u20131082","journal-title":"SIAM J Appl Math"},{"key":"9139_CR6","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"A Delcher","year":"1999","unstructured":"Delcher A, Kasif S, Fleischmann R, Peterson J, White O, Salzberg S (1999) Alignment of whole genomes. Nucleic Acids Res 27:2369\u20132376","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"9139_CR7","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"RC Edgar","year":"2004","unstructured":"Edgar RC (2004) Muscle: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res 32(5):1792\u20131797","journal-title":"Nucleic Acids Res"},{"key":"9139_CR8","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-540-24587-2_37","volume-title":"Proc. of the 14th ann. int. symp. on algorithms and computation (ISAAC\u201903)","author":"I Elias","year":"2003","unstructured":"Elias I (2003) Settling the intractability of multiple alignment. In: Proc. of the 14th ann. int. symp. on algorithms and computation (ISAAC\u201903). Lecture notes in computer science, vol 2906. Springer, Berlin, pp 352\u2013363"},{"key":"9139_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","volume":"11","author":"D Eppstein","year":"1990","unstructured":"Eppstein D (1990) Sequence comparison with mixed convex and concave costs. J Algorithms 11:85\u2013101","journal-title":"J Algorithms"},{"key":"9139_CR10","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"M Fisher","year":"1994","unstructured":"Fisher M (1994) Optimal solutions of vehicle routing problems using minimum k-trees. Oper Res 42:626\u2013642","journal-title":"Oper Res"},{"key":"9139_CR11","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"9139_CR12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","volume":"2","author":"S Gupta","year":"1995","unstructured":"Gupta S, Kececioglu J, Schaeffer A (1995) 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","journal-title":"J Comput Biol"},{"key":"9139_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D (1997) Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge"},{"key":"9139_CR14","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M Held","year":"1971","unstructured":"Held M, Karp R (1971) The traveling salesman problem and minimum spanning trees: part II. Math Program 1:6\u201325","journal-title":"Math Program"},{"key":"9139_CR15","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1093\/nar\/gki198","volume":"33","author":"K Katoh","year":"2005","unstructured":"Katoh K, Kuma K, Toh H, Miyata T (2005) MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids 33:511","journal-title":"Nucleic Acids"},{"key":"9139_CR16","unstructured":"Larmore L, Schieber B (1990) Online dynamic programming with applications to the prediction of RNA secondary structure. In: Proceedings of the first symposium on discrete algorithms, pp\u00a0503\u2013512"},{"issue":"5","key":"9139_CR17","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1089\/106652701446134","volume":"7","author":"M Lermen","year":"2000","unstructured":"Lermen M, Reinert K (2000) The practical use of the $\\mathcal{A}^{*}$ algorithm for exact multiple sequence alignment. J Comput Biol 7(5):655\u2013673","journal-title":"J Comput Biol"},{"key":"9139_CR18","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"D Lipman","year":"1989","unstructured":"Lipman D, Altschul S, Kececioglu J (1989) A tool for multiple sequence alignment. Proc Nat Acad Sci US Am 86:4412\u20134415","journal-title":"Proc Nat Acad Sci US Am"},{"key":"9139_CR19","first-page":"2","volume":"21","author":"A Lucena","year":"1993","unstructured":"Lucena A (1993) Steiner problem in graphs: Lagrangean relaxation and cutting-planes. COAL Bull 21:2\u20137","journal-title":"COAL Bull"},{"key":"9139_CR20","volume-title":"The LEDA platform of combinatorial and geometric computing","author":"K Mehlhorn","year":"1999","unstructured":"Mehlhorn K, N\u00e4her S (1999) The LEDA platform of combinatorial and geometric computing. Cambridge University Press, Cambridge. See also http:\/\/www.mpi-sb.mpg.de\/LEDA\/"},{"issue":"1","key":"9139_CR21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins DG, Heringa J (2000) T-Coffee: a novel method for fast and accurate multiple sequence alignment. J Mol Biol 302(1):205\u2013217","journal-title":"J Mol Biol"},{"key":"9139_CR22","unstructured":"Reinert K (1999) A polyhedral approach to sequence alignment problems. PhD thesis, Universit\u00e4t des Saarlandes, 1999"},{"key":"9139_CR23","doi-asserted-by":"crossref","unstructured":"Reinert K, Lenhof H-P, Mutzel P, Mehlhorn K, Kececioglu J (1997) A branch-and-cut algorithm for multiple sequence alignment. In: Proceedings of the first annual international conference on computational molecular biology (RECOMB-97), pp 241\u2013249","DOI":"10.1145\/267521.267845"},{"issue":"9","key":"9139_CR24","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1093\/bioinformatics\/16.9.808","volume":"16","author":"K Reinert","year":"2000","unstructured":"Reinert K, Stoye J, Will T (2000) An iterative method for faster sum-of-pairs multiple sequence alignment. Bioinformatics 16(9):808\u2013814","journal-title":"Bioinformatics"},{"key":"9139_CR25","volume-title":"Time warps, string edits and macromolecules: the theory and practice of sequence comparison","author":"D Sankoff","year":"1983","unstructured":"Sankoff D, Kruskal JB (1983) Time warps, string edits and macromolecules: the theory and practice of sequence comparison. Addison\u2013Wesley, Reading"},{"key":"9139_CR26","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1186\/1471-2105-6-66","volume":"6","author":"AR Subramanian","year":"2005","unstructured":"Subramanian AR, Weyer-Menkhoff J, Kaufmann M, Morgenstern B (2005) DIALIGN-T: An improved algorithm for segment-based multiple sequence alignment. BMC Bioinformatics 6:66","journal-title":"BMC Bioinformatics"},{"issue":"22","key":"9139_CR27","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ (1994) CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res 22(22):4673\u20134680","journal-title":"Nucleic Acids Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-008-9139-z.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T08:03:09Z","timestamp":1555574589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-008-9139-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,5]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9139"],"URL":"https:\/\/doi.org\/10.1007\/s10878-008-9139-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,5]]}}}