{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:53:36Z","timestamp":1742388816088},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540778905"},{"type":"electronic","value":"9783540778912"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77891-2_4","type":"book-chapter","created":{"date-parts":[[2008,1,12]],"date-time":"2008-01-12T03:19:36Z","timestamp":1200107976000},"page":"34-45","source":"Crossref","is-referenced-by-count":11,"title":["On the Approximability of Comparing Genomes with Duplicates"],"prefix":"10.1007","author":[{"given":"S\u00e9bastien","family":"Angibaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irena","family":"Rusu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoretical Computer Science\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"4_CR2","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1089\/cmb.2007.A001","volume":"14","author":"S. Angibaud","year":"2007","unstructured":"Angibaud, S., Fertin, G., Rusu, I., Vialette, S.: A general framework for computing rearrangement distances between genomes with duplicates. Journal of Computational Biology\u00a014(4), 379\u2013393 (2007)","journal-title":"Journal of Computational Biology"},{"key":"4_CR3","unstructured":"Bafna, V., Pevzner, P.: Sorting by reversals: genome rearrangements in plant organelles and evolutionary history of X chromosome. Molecular Biology and Evolution, 239\u2013246 (1995)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11533719_5","volume-title":"Computing and Combinatorics","author":"G. Blin","year":"2005","unstructured":"Blin, G., Rizzi, R.: Conserved interval distance computation between non-trivial genomes. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 22\u201331. Springer, Heidelberg (2005)"},{"key":"4_CR5","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-94-011-4309-7_19","volume-title":"Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignement, and the Evolution of Gene Families","author":"D. Bryant","year":"2000","unstructured":"Bryant, D.: The complexity of calculating exemplar distances. In: Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignement, and the Evolution of Gene Families, pp. 207\u2013212. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1007\/11758525_105","volume-title":"Computational Science \u2013 ICCS 2006","author":"C. Chauve","year":"2006","unstructured":"Chauve, C., Fertin, G., Rizzi, R., Vialette, S.: Genomes containing duplicates are hard to compare. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J.J. (eds.) ICCS 2006. LNCS, vol.\u00a03992, pp. 783\u2013790. Springer, Heidelberg (2006)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-73437-6_14","volume-title":"CPM 2007","author":"Z. Chen","year":"2007","unstructured":"Chen, Z., Fu, B., Xu, J., Yang, B., Zhao, Z., Zhu, B.: Non-breaking similarity of genomes with gene repetitions. In: CPM 2007. LNCS, vol.\u00a04580, pp. 119\u2013130. Springer, Heidelberg (2007)"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/11775096_27","volume-title":"Algorithmic Aspects in Information and Management","author":"Z. Chen","year":"2006","unstructured":"Chen, Z., Fu, B., Zhu, B.: The approximability of the exemplar breakpoint distance problem. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 291\u2013302. Springer, Heidelberg (2006)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/11561071_39","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Crochemore","year":"2005","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Vialette, S.: Approximating the 2-interval pattern problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 426\u2013437. Springer, Heidelberg (2005)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","first-page":"473","volume-title":"Algorithms and Computation","author":"A. Goldstein","year":"2004","unstructured":"Goldstein, A., Kolman, P., Zheng, Z.: Minimum common string partition problem: Hardness and approximations. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 473\u2013484. Springer, Heidelberg (2004)"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/11970125_22","volume-title":"Approximation and Online Algorithms","author":"P. Kolman","year":"2007","unstructured":"Kolman, P., Wale\u0144, T.: Reversal distance for strings with duplicates: Linear time approximation using hitting set. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 279\u2013289. Springer, Heidelberg (2007)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1038\/35057039","volume":"409","author":"W. Li","year":"2001","unstructured":"Li, W., Gu, Z., Wang, H., Nekrutenko, A.: Evolutionary analysis of the human genome. Nature\u00a0(409), 847\u2013849 (2001)","journal-title":"Nature"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.02.039","volume":"325","author":"M. Marron","year":"2004","unstructured":"Marron, M., Swenson, K.M., Moret, B.M.E.: Genomic distances under deletions and insertions. Theoretical Computer Science\u00a0325(3), 347\u2013360 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"11","key":"4_CR15","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D. Sankoff","year":"1999","unstructured":"Sankoff, D.: Genome rearrangement with gene families. Bioinformatics\u00a015(11), 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"key":"4_CR16","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11554714_11","volume-title":"Comparative Genomics","author":"D. Sankoff","year":"2005","unstructured":"Sankoff, D., Haque, L.: Power boosts for cluster tests. In: McLysaght, A., Huson, D.H. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03678, pp. 121\u2013130. Springer, Heidelberg (2005)"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-540-45078-8_4","volume-title":"Algorithms and Data Structures","author":"J. Tang","year":"2003","unstructured":"Tang, J., Moret, B.M.E.: Phylogenetic reconstruction from gene-rearrangement data with unequal gene content. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 37\u201346. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77891-2_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:55:09Z","timestamp":1619506509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77891-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540778905","9783540778912"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77891-2_4","relation":{},"subject":[]}}