{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T10:13:21Z","timestamp":1778667201675,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,13]],"date-time":"2014-09-13T00:00:00Z","timestamp":1410566400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9938-9","type":"journal-article","created":{"date-parts":[[2014,9,12]],"date-time":"2014-09-12T18:25:58Z","timestamp":1410546358000},"page":"91-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["A 1.5-Approximation Algorithm for Two-Sided Scaffold Filling"],"prefix":"10.1007","volume":"74","author":[{"given":"Nan","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haitao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,13]]},"reference":[{"issue":"1","key":"9938_CR1","doi-asserted-by":"crossref","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 Appl. 13(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"9938_CR2","doi-asserted-by":"crossref","unstructured":"Blin, G., Fertin, G., Sikora, F., Vialette, S.: The exemplar breakpoint distance for nontrivial genomes cannot be approximated. In: Proceedings of 3rd Workshop on Algorithm and Computation, LNCS 5431, pp. 357\u2013368 (2009)","DOI":"10.1007\/978-3-642-00202-1_31"},{"key":"9938_CR3","doi-asserted-by":"crossref","unstructured":"Chen, Z., Fu, B., Zhu, B.: The approximability of the exemplar breakpoint distance problem. In: Proceedings of 2nd International Conference on Algorithmic Aspects in Information and Management $$(AAIM^{\\prime }06)$$ ( A A I M \u2032 06 ) , LNCS 4041, pp. 291\u2013302 (2006)","DOI":"10.1007\/11775096_27"},{"issue":"2","key":"9938_CR4","doi-asserted-by":"crossref","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. Comb. Optim. 15(2), 201\u2013221 (2008)","journal-title":"J. Comb. Optim."},{"key":"9938_CR5","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proceedings of 13th ACM-SIAM Symposium on Discrete Algorithms $$(SODA^{\\prime }02)$$ ( S O D A \u2032 02 ) , pp. 667\u2013676 (2002)"},{"key":"9938_CR6","doi-asserted-by":"crossref","unstructured":"Goldstein, A., Kolman, P., Zheng, J.: Minimum common string partitioning problem: hardness and approximations. In: Proceedings of 15th International Symposium on Algorithms and Computation $$(ISAAC^{\\prime }04)$$ ( I S A A C \u2032 04 ) , LNCS 3341, pp. 473\u2013484 (2004)","DOI":"10.1007\/978-3-540-30551-4_43"},{"issue":"5","key":"9938_CR7","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/585265.585267","volume":"49","author":"DH Huson","year":"2002","unstructured":"Huson, D.H., Reinert, K., Myers, E.W.: The greedy path-merging algorithm for contig scaffolding. J. ACM 49(5), 603\u2013615 (2002)","journal-title":"J. ACM"},{"key":"9938_CR8","doi-asserted-by":"crossref","unstructured":"Jiang, H., Zhong, F., Zhu, B.: Filling scaffolds with gene repetitions: maximizing the number of adjacencies. In: Proceedings of 22nd Annual Symposium on Combinatorial Pattern Matching $$(CPM^{\\prime }11)$$ ( C P M \u2032 11 ) , LNCS 6661, pp. 55\u201364 (2011)","DOI":"10.1007\/978-3-642-21458-5_7"},{"key":"9938_CR9","doi-asserted-by":"crossref","unstructured":"Jiang, M.: The zero exemplar distance problem. In: Proceedings of the 2010 International RECOMB-CG Workshop (RECOMB-CG\u201910), LNBI 6398, pp. 74\u201382 (2010)","DOI":"10.1007\/978-3-642-16181-0_7"},{"issue":"4","key":"9938_CR10","doi-asserted-by":"crossref","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. Comput. Biol. Bioinform. 9(4), 1220\u20131229 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9938_CR11","doi-asserted-by":"crossref","unstructured":"Liu, N., Jiang, H., Zhu, D., Zhu, B.: An improved approximation algorithm for scaffold filling to maximize the common adjacencies. In: The 19th Annual International Computing and Combinatorics Conference $$(COCOON^{\\prime }13)$$ ( C O C O O N \u2032 13 ) , LNCS 7936, pp. 397\u2013408, (2013). IEEE\/ACM Trans. Comput. Biol. Bioinform., 10(4), 905\u2013913 (2013)","DOI":"10.1109\/TCBB.2013.100"},{"key":"9938_CR12","doi-asserted-by":"crossref","unstructured":"Liu, N., Zhu, D.: The algorithm for two-sided scaffold filling problem. In: The 10th Annual International Conference on Theory and Applications of Models of Computation $$(TAMC 2013)$$ ( T A M C 2013 ) , LNCS 7876, pp. 236\u2013247 (2013)","DOI":"10.1007\/978-3-642-38236-9_22"},{"key":"9938_CR13","doi-asserted-by":"crossref","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 Bioinform. 11, 304 (2010)","journal-title":"BMC Bioinform."},{"issue":"11","key":"9938_CR14","doi-asserted-by":"crossref","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9938-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9938-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9938-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T23:15:09Z","timestamp":1565824509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9938-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,13]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9938"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9938-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,13]]}}}