{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:32:22Z","timestamp":1742913142523,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_20","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"251-263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem"],"prefix":"10.1007","author":[{"given":"Haitao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjing","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junfeng","family":"Luan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S Angibaud","year":"2009","unstructured":"Angibaud, S., Fertin, G., Rusu, I., Thevenin, A., Vialette, S.: On the approximability of comparing genomes with duplicates. J. Graph Algorithms and Applications 13(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms and Applications"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-00202-1_31","volume-title":"WALCOM: Algorithms and Computation","author":"G Blin","year":"2009","unstructured":"Blin, G., Fertin, G., Sikora, F., Vialette, S.: The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 357\u2013368. Springer, Heidelberg (2009)"},{"key":"20_CR3","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 667\u2013676 (2002)"},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10878-007-9077-1","volume":"15","author":"Z Chen","year":"2008","unstructured":"Chen, Z., Fowler, R., Fu, B., Zhu, B.: On the inapproximability of the exemplar conserved interval distance problem of genomes. J. Combinatorial Optimization 15(2), 201\u2013221 (2008)","journal-title":"J. Combinatorial Optimization"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Madhu, S., Umesh, V.: On syntactic versus computational views of approximability. SIAM Journal on Computing 28(1), 164\u2013191 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-540-73437-6_14","volume-title":"Combinatorial Pattern Matching","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: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 119\u2013130. Springer, Heidelberg (2007)"},{"key":"20_CR7","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. 4041, pp. 291\u2013302. Springer, Heidelberg (2006)"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/978-3-540-30551-4_43","volume-title":"Algorithms and Computation","author":"A Goldstein","year":"2004","unstructured":"Goldstein, A., Kolman, P., Zheng, J.: Minimum common string partitioning problem: hardness and approximations. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 484\u2013495. Springer, Heidelberg (2004). also in: The Electronic Journal of Combinatorics 12 (2005), paper R50"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-16181-0_7","volume-title":"Comparative Genomics","author":"M Jiang","year":"2010","unstructured":"Jiang, M.: The zero exemplar distance problem. In: Tannier, E. (ed.) RECOMB-CG 2010. LNCS, vol. 6398, pp. 74\u201382. Springer, Heidelberg (2010)"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-16181-0_8","volume-title":"Comparative Genomics","author":"H Jiang","year":"2010","unstructured":"Jiang, H., Zheng, C., Sankoff, D., Zhu, B.: Scaffold filling under the breakpoint distance. In: Tannier, E. (ed.) RECOMB-CG 2010. LNCS, vol. 6398, pp. 83\u201392. Springer, Heidelberg (2010)"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-21458-5_7","volume-title":"Combinatorial Pattern Matching","author":"H Jiang","year":"2011","unstructured":"Jiang, H., Zhong, F., Zhu, B.: Filling scaffolds with gene repetitions: maximizing the number of adjacencies. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 55\u201364. Springer, Heidelberg (2011)"},{"issue":"4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1109\/TCBB.2012.57","volume":"9","author":"H Jiang","year":"2012","unstructured":"Jiang, H., Zheng, C., Sankoff, D., Zhu, B.: Scaffold filling under the breakpoint and related distances. IEEE\/ACM Trans. Bioinformatics and Comput. Biology 9(4), 1220\u20131229 (2012)","journal-title":"IEEE\/ACM Trans. Bioinformatics and Comput. Biology"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1186\/1471-2105-11-304","volume":"11","author":"A Mu\u00f1oz","year":"2010","unstructured":"Mu\u00f1oz, A., Zheng, C., Zhu, Q., Albert, V., Rounsley, S., Sankoff, D.: Scaffold filling, contig fusion and gene order comparison. BMC Bioinformatics 11, 304 (2010)","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"20_CR14","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 15(11), 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"issue":"4","key":"20_CR15","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1109\/TCBB.2013.100","volume":"10","author":"N Liu","year":"2013","unstructured":"Liu, N., Jiang, H., Zhu, D., Zhu, B.: An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies. IEEE\/ACM Trans. Comput. Biology Bioinform. 10(4), 905\u2013913 (2013)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-38236-9_22","volume-title":"Theory and Applications of Models of Computation","author":"N Liu","year":"2013","unstructured":"Liu, N., Zhu, D.: The algorithm for the two-sided scaffold filling problem. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 236\u2013247. Springer, Heidelberg (2013)"},{"key":"20_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inform. Process. Lett. 37, 27\u201335 (1991)","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:31:10Z","timestamp":1675272670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}