{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:05:54Z","timestamp":1761620754433},"reference-count":41,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4733,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1016\/s0166-218x(00)00194-3","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T17:13:06Z","timestamp":1027617186000},"page":"143-186","source":"Crossref","is-referenced-by-count":35,"title":["A polyhedral approach to sequence alignment problems"],"prefix":"10.1016","volume":"104","author":[{"given":"John D.","family":"Kececioglu","sequence":"first","affiliation":[]},{"given":"Hans-Peter","family":"Lenhof","sequence":"additional","affiliation":[]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Vingron","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00194-3_BIB1","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/BF02462328","article-title":"Locally optimal subalignments using nonlinear similarity functions","volume":"48","author":"Altschul","year":"1986","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB2","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal, B. Cook, Finding cuts in the TSP, DIMACS Technical Report 95-05, DIMACS, April 1995."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB3","series-title":"Proceedings of the Sixth Annual Symposium on Combinatorial Pattern Matching (CPM-95)","first-page":"1","article-title":"Computing similarity between RNA strings","volume":"Vol. 937","author":"Bafna","year":"1995"},{"issue":"4","key":"10.1016\/S0166-218X(00)00194-3_BIB4","first-page":"389","article-title":"RNAlign program: alignment of RNA sequences using both primary and secondary structures","volume":"10","author":"Corpet","year":"1994","journal-title":"CABIOS"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB5","series-title":"Atlas of Proteins Sequence and Structure, Vol. 5","first-page":"345","article-title":"A model of evolutionary change in proteins","author":"Dayhoff","year":"1979"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB6","first-page":"3495","article-title":"Database on the structure of the small ribosomal subunit RNA","volume":"1994","author":"de Rijk","year":"1922","journal-title":"Nucleic Acids Res."},{"issue":"11","key":"10.1016\/S0166-218X(00)00194-3_BIB7","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","article-title":"RNA sequence analysis using covariance models","volume":"22","author":"Eddy","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB8","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","article-title":"Finding the most significant common sequence and structure motifs in a set of RNA sequences","volume":"25","author":"Gorodkin","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB9","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","article-title":"A cutting plane algorithm for the linear ordering problem","volume":"32","author":"Gr\u00f6tschel","year":"1984","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB11","series-title":"Polyhedral theory, Wiley-Interscience Series in Discrete Mathematics and Optimization.","author":"Gr\u00f6tschel","year":"1985"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","article-title":"Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment","volume":"2","author":"Gupta","year":"1995","journal-title":"J. Comput. Biol."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB13","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF01580442","article-title":"Facets of Regular 0-1-Polytopes","volume":"8","author":"Hammer","year":"1975","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB14","doi-asserted-by":"crossref","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","article-title":"Amino acid substitution matrices from protein blocks","volume":"89","author":"Henikoff","year":"1992","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB15","series-title":"Handbook on Operations Research and Management Science","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0927-0507(05)80121-5","article-title":"The traveling salesman problem","author":"J\u00fcnger","year":"1995"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB16","series-title":"Combinatorial optimization: papers from the DIMACS special year, Vol. 20, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"111","article-title":"Practical problem solving with cutting plane algorithms in combinatorial optimization","author":"J\u00fcnger","year":"1995"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB17","unstructured":"M. J\u00fcnger, S. Thienel, The design of the branch and cut system ABACUS, Technical Report 97.260, Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln, 1997."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB18","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1137\/0211053","article-title":"On linear characterizations of combinatorial optimization problems","volume":"11","author":"Karp","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB19","unstructured":"J.D. Kececioglu, Exact and approximation algorithms for DNA sequence reconstruction, Ph.D. Thesis, University of Arizona, 1991."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB20","unstructured":"J.D. Kececioglu, PRIMAL: Practical rigorous multiple alignment, Computer software, 1996."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB21","doi-asserted-by":"crossref","unstructured":"H.-P. Lenhof, K. Reinert, M. Vingron, A polyhedral approach to RNA sequence structure alignment, Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB-98) ACM Press, New York, USA, 1998, pp. 153\u2013162.","DOI":"10.1145\/279069.279109"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB22","unstructured":"M. Lermen, K. Reinert, The practical use of the A* algorithm for exact multiple sequence alignment, Research report MPI-I-97-1-028, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, 1997."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB23","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/224759a0","article-title":"Detailed molecular model for transfer ribonucleic acid","volume":"224","author":"Levitt","year":"1969","journal-title":"Nature"},{"issue":"4","key":"10.1016\/S0166-218X(00)00194-3_BIB24","first-page":"571","article-title":"Comparative analysis of multiple protein-sequence alignment methods","volume":"11","author":"McClure","year":"1994","journal-title":"Mol. Biol. Evol."},{"issue":"1","key":"10.1016\/S0166-218X(00)00194-3_BIB25","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/204865.204889","article-title":"LEDA, a platform for combinatorial and geometric computing","volume":"38","author":"Mehlhorn","year":"1995","journal-title":"Commun. ACM"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB26","unstructured":"B. Morgenstern, W.R. Atchley, K. Hahn, A. Dress, Segment-based scores for pairwise and multiple sequence alignments, Proceedings of the Sixth International Conference on Intelligent Systems for Molecular Biology (ISMB-98), 1998, in press."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB27","doi-asserted-by":"crossref","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","article-title":"Multiple DNA and protein sequence alignment based on segment-to-segment comparison","volume":"93","author":"Morgenstern","year":"1996","journal-title":"Proc. Nat. Acad. Sci."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB28","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino-acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB29","series-title":"Optimization, Vol. 1, Handbooks in Operations Research and Management Science","author":"Nemhauser","year":"1989"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB30","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/BF01580222","article-title":"Properties of vertex packing and independence system polyhedra","volume":"6","author":"Nemhauser","year":"1973","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB31","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1093\/nar\/25.22.4570","article-title":"RAGA: RNA sequence alignment by genetic algorithm","volume":"25","author":"Notredame","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","article-title":"Optimization of a 532 city symmetric traveling salesman problem by branch and cut","volume":"6","author":"Padberg","year":"1987","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB33","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1006\/aama.1993.1008","article-title":"Generalized sequence alignment and duality","volume":"14","author":"Pevzner","year":"1993","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB34","unstructured":"K. Reinert, A polyhedral approach to sequence alignment problems, Ph.D. Thesis Universit\u00e4t des Saarlandes, Im Stadtwald, 66123 Saarbr\u00fccken, Germany, 1999."},{"issue":"5","key":"10.1016\/S0166-218X(00)00194-3_BIB35","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB36","series-title":"Time Warps, String Edits and Macromolecules: the Theory and Practice of Sequence Comparison","author":"Sankoff","year":"1983"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB37","series-title":"Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"Schrijver","year":"1986"},{"key":"10.1016\/S0166-218X(00)00194-3_BIB38","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A new algorithm for generating all the maximal independent sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/aama.1995.1001","article-title":"Multiple sequence comparison and consistency on multipartite graphs","volume":"16","author":"Vingron","year":"1995","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0166-218X(00)00194-3_BIB40","unstructured":"M.S. Waterman, Consensus methods for folding single-stranded nucleic acids, Mathematical Methods for DNA Sequences, CRC Press, Boca Raton, FL, 1989, pp. 185\u2013224."},{"issue":"3","key":"10.1016\/S0166-218X(00)00194-3_BIB41","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/0144038","article-title":"The context dependent comparison of biological sequences","volume":"44","author":"Wilbur","year":"1984","journal-title":"SIAM J. Appl. Math."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00001943?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00001943?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T04:56:44Z","timestamp":1556168204000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00001943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":41,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0166218X00001943"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00194-3","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}