{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:32:31Z","timestamp":1742916751524,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030271947"},{"type":"electronic","value":"9783030271954"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-27195-4_9","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T09:03:14Z","timestamp":1564650194000},"page":"95-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A 2.57-Approximation Algorithm for Contig-Based Genomic Scaffold Filling"],"prefix":"10.1007","author":[{"given":"Qilong","family":"Feng","sequence":"first","affiliation":[]},{"given":"Xiangzhong","family":"Meng","sequence":"additional","affiliation":[]},{"given":"Guanlan","family":"Tan","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2014.12.005","volume":"568","author":"L Bulteau","year":"2015","unstructured":"Bulteau, L., Carrieri, A.P., Dondi, R.: Fixed-parameter algorithms for scaffold filling. Theoret. Comput. Sci. 568, 72\u201383 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR2","unstructured":"Bulteau, L., Fertin, G., Komusiewicz, C.: Beyond adjacency maximization: Scaffold filling for new string distances. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 78. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"9_CR3","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). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_14"},{"key":"9_CR4","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). https:\/\/doi.org\/10.1007\/11775096_27"},{"key":"9_CR5","unstructured":"Jiang, H., Fan, C., Yang, B., Zhong, F., Zhu, D., Zhu, B.: Genomic scaffold filling revisited. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 54. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"4","key":"9_CR6","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. Comput. Biol. Bioinform. 9(4), 1220\u20131229 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR7","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). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_7"},{"issue":"4","key":"9_CR8","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. Biol. Bioinform. 10(4), 905\u2013913 (2013)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00453-014-9938-9","volume":"74","author":"N Liu","year":"2016","unstructured":"Liu, N., Zhu, D., Jiang, H., Zhu, B.: A 1.5-approximation algorithm for two-sided scaffold filling. Algorithmica 74(1), 91\u2013116 (2016)","journal-title":"Algorithmica"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1007\/978-3-319-48749-6_60","volume-title":"Combinatorial Optimization and Applications","author":"N Liu","year":"2016","unstructured":"Liu, N., Zou, P., Zhu, B.: A polynomial time solution for permutation scaffold filling. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 782\u2013789. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48749-6_60"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-319-39817-4_15","volume-title":"Frontiers in Algorithmics","author":"Jingjing Ma","year":"2016","unstructured":"Ma, J., Jiang, H.: Notes on the $$\\frac{6}{5}$$-approximation algorithm for one-sided scaffold filling. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, pp. 145\u2013157. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-319-39817-4_15"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-319-59605-1_18","volume-title":"Frontiers in Algorithmics","author":"J Ma","year":"2017","unstructured":"Ma, J., Jiang, H., Zhu, D., Zhang, S.: A 1.4-approximation algorithm for two-sided scaffold filling. In: Xiao, M., Rosamond, F. (eds.) FAW 2017. LNCS, vol. 10336, pp. 196\u2013208. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-59605-1_18"},{"issue":"1","key":"9_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.A., Rounsley, S., Sankoff, D.: Scaffold filling, contig fusion and comparative gene order inference. BMC Bioinform. 11(1), 304 (2010)","journal-title":"BMC Bioinform."},{"issue":"16","key":"9_CR14","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/978-3-319-39817-4_2","volume-title":"Frontiers in Algorithmics","author":"Binhai Zhu","year":"2016","unstructured":"Zhu, B.: Genomic scaffold filling: a progress report. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, vol. 9711, pp. 8\u201316. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-319-39817-4_2"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-27195-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:16:16Z","timestamp":1709824576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-27195-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030271947","9783030271954"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-27195-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/theory.ict.ac.cn\/aaim2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}