{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:49:44Z","timestamp":1742917784970,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","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":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_22","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"294-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding"],"prefix":"10.1007","author":[{"given":"Cl\u00e9ment","family":"Dallard","sequence":"first","affiliation":[]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"22_CR1","series-title":"Combinatorial Optimization","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/0-306-48213-4_12","volume-title":"The Traveling Salesman Problem and Its Variations","author":"A Barvinok","year":"2007","unstructured":"Barvinok, A., Gimadi, E.K., Serdyukov, A.I.: The maximum TSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, pp. 585\u2013607. Springer, Heidelberg (2007)"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2015.06.023","volume":"595","author":"A Chateau","year":"2015","unstructured":"Chateau, A., Giroudeau, R.: A complexity and approximation framework for the maximization scaffolding problem. Theor. Comput. Sci. 595, 92\u2013106 (2015). \n                      http:\/\/dx.doi.org\/10.1016\/j.tcs.2015.06.023","journal-title":"Theor. Comput. Sci."},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-319-39817-4_3","volume-title":"Frontiers in Algorithmics","author":"Z-Z Chen","year":"2016","unstructured":"Chen, Z.-Z., Harada, Y., Machida, E., Guo, F., Wang, L.: Better approximation algorithms for scaffolding problems. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, vol. 9711, pp. 17\u201328. Springer, Heidelberg (2016). \n                      http:\/\/dx.doi.org\/10.1007\/978-3-319-39817-4_3"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-33122-0_19","volume-title":"Algorithms in Bioinformatics","author":"R Chikhi","year":"2012","unstructured":"Chikhi, R., Rizk, G.: Space-efficient and exact de bruijn graph representation based on a bloom filter. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol. 7534, pp. 236\u2013248. Springer, Heidelberg (2012)"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-11-345","volume":"11","author":"A Dayarian","year":"2010","unstructured":"Dayarian, A., Michael, T.P., Sengupta, A.M.: SOPRA: scaffolding algorithm for paired reads via statistical optimization. BMC Bioinform. 11(1), 1\u201321 (2010)","journal-title":"BMC Bioinform."},{"issue":"4","key":"22_CR6","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","volume":"29","author":"N Donmez","year":"2013","unstructured":"Donmez, N., Brudno, M.: SCARPA: scaffolding reads with practical algorithms. Bioinformatics 29(4), 428\u2013434 (2013)","journal-title":"Bioinformatics"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Ferdjoukh, A., Bourreau, E., Chateau, A., Nebut, C.: A model-driven approach to generate relevant and realistic datasets. In: SEKE, pp. 105\u2013109. KSI Research Inc. and Knowledge Systems Institute Graduate School (2016)","DOI":"10.18293\/SEKE2016-029"},{"issue":"11","key":"22_CR8","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","volume":"18","author":"S Gao","year":"2011","unstructured":"Gao, S., Sung, W.-K., Nagarajan, N.: Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences. J. Comput. Biol. 18(11), 1681\u20131691 (2011)","journal-title":"J. Comput. Biol."},{"issue":"11","key":"22_CR9","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1093\/bioinformatics\/bts175","volume":"28","author":"AA Gritsenko","year":"2012","unstructured":"Gritsenko, A.A., Nijkamp, J.F., Reinders, M.J., de Ridder, D.: GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies. Bioinformatics 28(11), 1429\u20131437 (2012)","journal-title":"Bioinformatics"},{"issue":"3","key":"22_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/gb-2014-15-3-r42","volume":"15","author":"M Hunt","year":"2014","unstructured":"Hunt, M., Newbold, C., Berriman, M., Otto, T.: A comprehensive evaluation of assembly scaffolding tools. Genome Biol. 15(3), 1\u201315 (2014). doi:\n                      10.1186\/gb-2014-15-3-r42\n                      \n                    . \n                      http:\/\/dx.doi.org\/10.1186\/gb-2014-15-3-r42","journal-title":"Genome Biol."},{"issue":"5","key":"22_CR11","doi-asserted-by":"publisher","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 (JACM) 49(5), 603\u2013615 (2002)","journal-title":"J. ACM (JACM)"},{"issue":"21","key":"22_CR12","doi-asserted-by":"publisher","first-page":"2964","DOI":"10.1093\/bioinformatics\/btr520","volume":"27","author":"S Koren","year":"2011","unstructured":"Koren, S., Treangen, T.J., Pop, M.: Bambus 2: scaffolding metagenomes. Bioinformatics 27(21), 2964\u20132971 (2011)","journal-title":"Bioinformatics"},{"issue":"5","key":"22_CR13","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics 26(5), 589\u2013595 (2010). doi:\n                      10.1093\/bioinformatics\/btp698\n                      \n                    . \n                      http:\/\/dx.doi.org\/10.1093\/bioinformatics\/btp698","journal-title":"Bioinformatics"},{"issue":"16","key":"22_CR14","doi-asserted-by":"publisher","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Handsaker, B., Wysoker, A., Fennell, T., Ruan, J., Homer, N., Marth, G.T., Abecasis, G.R., Durbin, R.: The sequence alignment\/map format and SAMtools. Bioinformatics 25(16), 2078\u20132079 (2009)","journal-title":"Bioinformatics"},{"issue":"1","key":"22_CR15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1186\/1471-2105-15-281","volume":"15","author":"K Sahlin","year":"2014","unstructured":"Sahlin, K., Vezzi, F., Nystedt, B., Lundeberg, J., Arvestad, L.: BESST - efficient scaffolding of large fragmented assemblies. BMC Bioinform. 15(1), 281 (2014). ISSN 1471\u20132105","journal-title":"BMC Bioinform."},{"issue":"23","key":"22_CR16","doi-asserted-by":"publisher","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","volume":"27","author":"L Salmela","year":"2011","unstructured":"Salmela, L., M\u00e4kinen, V., V\u00e4lim\u00e4ki, N., Ylinen, J., Ukkonen, E.: Fast scaffolding with small independent mixed integer programs. Bioinformatics 27(23), 3259\u20133265 (2011)","journal-title":"Bioinformatics"},{"key":"22_CR17","unstructured":"Weller, M., Chateau, A., Dallard, C., Giroudeau, R.: Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases. In: (2016, revision)"},{"issue":"14","key":"22_CR18","doi-asserted-by":"publisher","first-page":"S2","DOI":"10.1186\/1471-2105-16-S14-S2","volume":"16","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(14), S2 (2015). ISSN 1471\u20132105","journal-title":"BMC Bioinform."},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-26626-8_30","volume-title":"Combinatorial Optimization and Applications","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: On the complexity of scaffolding problems: from cliques to sparse graphs. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 409\u2013423. Springer, Heidelberg (2015)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:19:09Z","timestamp":1558477149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","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":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}