{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T18:15:22Z","timestamp":1725819322443},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319164823"},{"type":"electronic","value":"9783319164830"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-16483-0_48","type":"book-chapter","created":{"date-parts":[[2015,3,16]],"date-time":"2015-03-16T06:36:38Z","timestamp":1426487798000},"page":"491-502","source":"Crossref","is-referenced-by-count":3,"title":["A Unified Integer Programming Model for Genome Rearrangement Problems"],"prefix":"10.1007","author":[{"given":"Giuseppe","family":"Lancia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franca","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Serafini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1089\/cmb.2007.R006","volume":"14","author":"M. Bader","year":"2007","unstructured":"Bader, M., Ohlebusch, E.: Sorting by weighted reversals, transpositions, and inverted transpositions. J. Comput. Biol.\u00a014, 615\u2013636 (2007)","journal-title":"J. Comput. Biol."},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"Bafna, V., Pevzner, P.: Genome rearrangements and sorting by reversals. SIAM J. Comp.\u00a025, 272\u2013289 (1996)","journal-title":"SIAM J. Comp."},{"key":"48_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.: Sorting by transpositions. SIAM J. Discr. Math.\u00a011, 224\u2013240 (1998)","journal-title":"SIAM J. Discr. Math."},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C. Barnhart","year":"1998","unstructured":"Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H.: Branch-and-Price: Column Generation for Solving Huge Integer Programs. Op. Res.\u00a046, 316\u2013329 (1998)","journal-title":"Op. Res."},{"key":"48_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45749-6_21","volume-title":"Algorithms - ESA 2002","author":"P. Berman","year":"2002","unstructured":"Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-Approximation algorithm for sorting by reversals. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 200\u2013210. Springer, Heidelberg (2002)"},{"key":"48_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-32589-2_24","volume-title":"Mathematical Foundations of Computer Science 2012","author":"L. Bulteau","year":"2012","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Pancake Flipping is Hard. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 247\u2013258. Springer, Heidelberg (2012)"},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Sorting by Transpositions Is Difficult. SIAM J. Discr. Math. 26, 1148","DOI":"10.1137\/110851390"},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Sorting by reversals is difficult. In: 1st ACM\/IEEE International Conference on Computational Molecular Biology, pp. 75\u201383. ACM Press (1997)","DOI":"10.1145\/267521.267531"},{"key":"48_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"Caprara, A.: Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM J. on Disc. Math.\u00a012, 91\u2013110 (1999)","journal-title":"SIAM J. on Disc. Math."},{"key":"48_CR10","doi-asserted-by":"crossref","unstructured":"Caprara, A., Lancia, G., Ng, S.-K.: A Column-Generation Based Branch-and-Bound Algorithm for Sorting By Reversals. In: Mathematical Support For Molecular Biology. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 47, pp. 213\u2013226 (1999)","DOI":"10.1090\/dimacs\/047\/10"},{"key":"48_CR11","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1287\/ijoc.13.3.224.12631","volume":"13","author":"L.G. Caprara","year":"2001","unstructured":"Caprara, L.G., Ng, S.K.: Sorting Permutations by Reversals through Branch and Price. INFORMS J. on Comp.\u00a013, 224\u2013244 (2001)","journal-title":"INFORMS J. on Comp."},{"key":"48_CR12","doi-asserted-by":"publisher","first-page":"3372","DOI":"10.1016\/j.tcs.2008.04.045","volume":"410","author":"B. Chitturi","year":"2009","unstructured":"Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I.H., Voit, W.: An 18\/11 n upper bound for sorting by prefix reversals. Theor. Comp. Sc.\u00a0410, 3372\u20133390 (2009)","journal-title":"Theor. Comp. Sc."},{"key":"48_CR13","unstructured":"Christie, A.: A 3\/2-approximation algorithm for sorting by reversals. In: 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 244\u2013252. ACM Press (1998)"},{"key":"48_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/11561071_38","volume-title":"Algorithms \u2013 ESA 2005","author":"J. Fischer","year":"2005","unstructured":"Fischer, J., Ginzinger, S.W.: A 2-Approximation Algorithm for Sorting by Prefix Reversals. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 415\u2013425. Springer, Heidelberg (2005)"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W. Gates","year":"1979","unstructured":"Gates, W., Papadimitriou, C.: Bounds for sorting by prefix reversal. Discr. Math.\u00a027, 47\u201357 (1979)","journal-title":"Discr. Math."},{"key":"48_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0304-3975(98)00092-9","volume":"210","author":"Q.P. Gu","year":"1999","unstructured":"Gu, Q.P., Peng, S., Sudborough, H.: A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theoret. Comput. Sci.\u00a0210, 327\u2013339 (1999)","journal-title":"Theoret. Comput. Sci."},{"key":"48_CR17","doi-asserted-by":"crossref","unstructured":"Hartman, T., Sharan, R.: A 1.5-approximation algorithm for sorting by transpositions and transreversals. J. Comput. Syst. Sci. 70, 300\u2013320 (2005)","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"48_CR18","doi-asserted-by":"crossref","unstructured":"Kececioglu, J., Sankoff, D.: Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica 13, 180\u2013210 (1995)","DOI":"10.1007\/BF01188586"},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Lancia, G., Serafini, P.: Deriving compact extended formulations via LP-based separation techniques. 4OR 12, 201\u2013234 (2014)","DOI":"10.1007\/s10288-014-0262-7"},{"key":"48_CR20","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1089\/106652702761034163","volume":"9","author":"J. Meidanis","year":"2002","unstructured":"Meidanis, J., Walter, M.M.T., Dias, Z.: A Lower Bound on the Reversal and Transposition Diameter. J. Comput. Biol.\u00a09, 743\u2013745 (2002)","journal-title":"J. Comput. Biol."},{"key":"48_CR21","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization, 784 pages. Wiley (1999)"},{"key":"48_CR22","doi-asserted-by":"crossref","unstructured":"Sankoff, D., Cedergren, R., Abel, Y.: Genomic divergence through gene rearrangement. In: Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, pp. 428\u2013438. Academic Press, New York (1990)","DOI":"10.1016\/0076-6879(90)83028-8"}],"container-title":["Lecture Notes in Computer Science","Bioinformatics and Biomedical Engineering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-16483-0_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T12:40:07Z","timestamp":1559133607000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-16483-0_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319164823","9783319164830"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-16483-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}