{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:29:52Z","timestamp":1742912992848,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319559100"},{"type":"electronic","value":"9783319559117"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_8","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T10:23:37Z","timestamp":1490005417000},"page":"97-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Shortest Common Superstring of NGS Reads"],"prefix":"10.1007","author":[{"given":"Tristan","family":"Braquelaire","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie","family":"Gasparoux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Raffinot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raluca","family":"Uricaru","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Armen, C., Stein, C.: A \n            $${2}{\\frac{2}{3}}$$\n           superstring approximation algorithm. Discrete Appl. Math. 88(1\u20133), 29\u201357 (1998). \nhttp:\/\/dx.doi.org\/10.1016\/S0166-218X(98)00065-1\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X98000651\n\n, Computational Molecular Biology DAM - CMB Series","DOI":"10.1016\/S0166-218X(98)00065-1"},{"key":"8_CR2","doi-asserted-by":"publisher","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear approximation of shortest superstrings. J. ACM 41(4), 630\u2013647 (1994). doi:\n10.1145\/179812.179818\n\n, \nhttp:\/\/doi.acm.org\/10.1145\/179812.179818","DOI":"10.1145\/179812.179818"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Breslauer, D., Jiang, T., Jiang, Z.: Rotations of periodic strings and short superstrings. J. Algorithms 24(2), 340\u2013353 (1997). \nhttp:\/\/dx.doi.org\/10.1006\/jagm.1997.0861\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677497908610","DOI":"10.1006\/jagm.1997.0861"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/3-540-60220-8_88","volume-title":"Algorithms and Data Structures","author":"C Armen","year":"1995","unstructured":"Armen, C., Stein, C.: Improved length bounds for the shortest superstring problem. In: Akl, S.G., Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 494\u2013505. Springer, Heidelberg (1995). doi:\n10.1007\/3-540-60220-8_88"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-13509-5_27","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Cygan, M., Iliopoulos, C., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Algorithms for three versions of the shortest common superstring problem. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 299\u2013309. Springer, Heidelberg (2010). doi:\n10.1007\/978-3-642-13509-5_27"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/3-540-45123-4_34","volume-title":"Combinatorial Pattern Matching","author":"A Czumaj","year":"2000","unstructured":"Czumaj, A., G\u00e7asieniec, L.: On the complexity of determining the period of a string. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 412\u2013422. Springer, Heidelberg (2000). doi:\n10.1007\/3-540-45123-4_34"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Gasieniec, L., Piotr\u00f3w, M., Rytter, W.: Sequential and parallel approximation of shortest superstrings. J. Algorithms 23(1), 74\u2013100 (1997). \nhttp:\/\/dx.doi.org\/10.1006\/jagm.1996.0823\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677496908238","DOI":"10.1006\/jagm.1996.0823"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Landau, G., Ma, B.: Combinatorial pattern matching why greed works for shortest common superstring problem. Theor. Comput. Sci. 410(51), 5374\u20135381 (2009). \nhttp:\/\/dx.doi.org\/10.1016\/j.tcs.2009.09.014\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397509006410","DOI":"10.1016\/j.tcs.2009.09.014"},{"key":"8_CR9","doi-asserted-by":"publisher","unstructured":"Fici, G., Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: On the greedy algorithm for the shortest common superstring problem with reversals. Inf. Process. Lett. 116(3), 245\u2013251 (2016). doi:\n10.1016\/j.ipl.2015.11.015","DOI":"10.1016\/j.ipl.2015.11.015"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Gallant, J., Maier, D., Astorer, J.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50\u201358 (1980). \nhttp:\/\/dx.doi.org\/10.1016\/0022-0000(80)90004-5\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000080900045","DOI":"10.1016\/0022-0000(80)90004-5"},{"key":"8_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1990)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-642-38905-4_13","volume-title":"Combinatorial Pattern Matching","author":"A Golovnev","year":"2013","unstructured":"Golovnev, A., Kulikov, A.S., Mihajlin, I.: Approximating shortest superstring problem using de Bruijn graphs. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 120\u2013129. Springer, Heidelberg (2013). doi:\n10.1007\/978-3-642-38905-4_13"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Odlyzko, A.M.: Periods in strings. J. Comb. Theor. Ser. A 30(1), 19\u201342 (1981). \nhttp:\/\/dx.doi.org\/10.1016\/0097-3165(81)90038-8\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/0097316581900388","DOI":"10.1016\/0097-3165(81)90038-8"},{"key":"8_CR14","unstructured":"Holub, S., Shallit, J.: Periods and borders of random words. In: STACS, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 47, pp. 44:1\u201344:10 (2016)"},{"key":"8_CR15","doi-asserted-by":"publisher","unstructured":"Kaplan, H., Shafrir, N.: The greedy algorithm for shortest superstrings. Inf. Process. Lett. 93(1), 13\u201317 (2005). doi:\n10.1016\/j.ipl.2004.09.012","DOI":"10.1016\/j.ipl.2004.09.012"},{"key":"8_CR16","unstructured":"Karpinski, M., Schmied, R.: Improved inapproximability results for the shortest superstring and related problems. In: CATS, Australian Computer Society, CRPIT 2013, vol. 141, pp. 27\u201336 (2013)"},{"key":"8_CR17","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings. In: 1994 Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp 166\u2013177 (1994). doi:\n10.1109\/SFCS.1994.365696","DOI":"10.1109\/SFCS.1994.365696"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Li, M.: Towards a DNA sequencing theory (learning a string). In: Proceedings of the 31st Symposium on the Foundations of Computer Science, pp. 125\u2013134. IEEE Computer Society Press, Los Alamitos (1990)","DOI":"10.1109\/FSCS.1990.89531"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Mucha, M.: Lyndon words and short superstrings. In: SODA, pp. 958\u2013972. SIAM (2013)","DOI":"10.1137\/1.9781611973105.69"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-46784-X_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Ott","year":"1999","unstructured":"Ott, S.: Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 55\u201364. Springer, Heidelberg (1999). doi:\n10.1007\/3-540-46784-X_7"},{"key":"8_CR21","unstructured":"Paluch, K.E.: Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. CoRR abs\/1401.3670 (2014). \nhttp:\/\/arxiv.org\/abs\/1401.3670"},{"key":"8_CR22","unstructured":"Paluch, K.E., Elbassioni, K.M., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In: STACS, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 14, pp. 501\u2013506 (2012)"},{"key":"8_CR23","doi-asserted-by":"publisher","unstructured":"Sweedyk, Z.: A \n            $$\\mathbf{{2}{\\frac{1}{2}}}$$\n          -approximation algorithm for shortest superstring. SIAM J. Comput. 29(3), 954\u2013986 (1999). doi:\n10.1137\/S0097539796324661","DOI":"10.1137\/S0097539796324661"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Tarhio, J., Ukkonen, E.: A greedy approximation algorithm for constructing shortest common superstrings. Theor. Comput. Sci. 57(1), 131\u2013145 (1988). doi:\n10.1016\/0304-3975(88)90167-3\n\n, \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397588901673","DOI":"10.1016\/0304-3975(88)90167-3"},{"key":"8_CR25","doi-asserted-by":"publisher","unstructured":"Teng, S.H., Yao, F.F.: Approximating shortest superstrings. SIAM J. Comput. 26(2), 410\u2013417 (1997). doi:\n10.1137\/S0097539794286125","DOI":"10.1137\/S0097539794286125"},{"key":"8_CR26","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag New York Inc., New York (2001)"},{"key":"8_CR27","unstructured":"Yu, Y.W.: Approximation hardness of shortest common superstring variants. CoRR abs\/1602.08648 (2016). \nhttp:\/\/arxiv.org\/abs\/1602.08648"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,11,22]],"date-time":"2017-11-22T03:59:07Z","timestamp":1511323147000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}