{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:57:32Z","timestamp":1758268652523,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319319568"},{"type":"electronic","value":"9783319319575"}],"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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-31957-5_11","type":"book-chapter","created":{"date-parts":[[2016,4,7]],"date-time":"2016-04-07T13:26:45Z","timestamp":1460035605000},"page":"152-163","source":"Crossref","is-referenced-by-count":9,"title":["Safe and Complete Contig Assembly Via Omnitigs"],"prefix":"10.1007","author":[{"given":"Alexandru I.","family":"Tomescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,8]]},"reference":[{"issue":"5","key":"11_CR1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1089\/cmb.2012.0021","volume":"19","author":"A Bankevich","year":"2012","unstructured":"Bankevich, A., et al.: SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J. Comp. Biol. 19(5), 455\u2013477 (2012)","journal-title":"J. Comp. Biol."},{"issue":"4","key":"11_CR2","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","volume":"27","author":"M Boetzer","year":"2011","unstructured":"Boetzer, M., et al.: Scaffolding pre-assembled contigs using SSPACE. Bioinformatics 27(4), 578\u2013579 (2011)","journal-title":"Bioinformatics"},{"issue":"6","key":"11_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/gb-2012-13-6-r56","volume":"13","author":"M Boetzer","year":"2012","unstructured":"Boetzer, M., Pirovano, W.: Toward almost closed genomes with gapfiller. Genome Biol. 13(6), 1\u20139 (2012)","journal-title":"Genome Biol."},{"issue":"Suppl 5","key":"11_CR4","doi-asserted-by":"crossref","first-page":"S18","DOI":"10.1186\/1471-2105-14-S5-S18","volume":"14","author":"G Bresler","year":"2013","unstructured":"Bresler, G., et al.: Optimal assembly for high throughput shotgun sequencing. BMC Bioinform. 14(Suppl 5), S18 (2013)","journal-title":"BMC Bioinform."},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-319-05269-4_4","volume-title":"Research in Computational Molecular Biology","author":"R Chikhi","year":"2014","unstructured":"Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the representation of de Bruijn graphs. In: Sharan, R. (ed.) RECOMB 2014. LNCS, vol. 8394, pp. 35\u201355. Springer, Heidelberg (2014)"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"6","key":"11_CR7","first-page":"569","volume":"8","author":"A Gu\u00e9noche","year":"1992","unstructured":"Gu\u00e9noche, A.: Can we recover a sequence, just knowing all its subsequences of given length? Comput. Appl. Biosci. 8(6), 569\u2013574 (1992)","journal-title":"Comput. Appl. Biosci."},{"issue":"6","key":"11_CR8","first-page":"659","volume":"100","author":"D Haussler","year":"2008","unstructured":"Haussler, D., et al.: Genome 10\u00a0K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species. J. Hered. 100(6), 659\u2013674 (2008)","journal-title":"J. Hered."},{"issue":"2","key":"11_CR9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","volume":"2","author":"RM Idury","year":"1995","unstructured":"Idury, R.M., Waterman, M.S.: A new algorithm for DNA sequence assembly. J. Comp. Biol. 2(2), 291\u2013306 (1995)","journal-title":"J. Comp. Biol."},{"key":"11_CR10","unstructured":"Jackson, B.G.: Parallel methods for short read assembly. Ph.D. thesis, Iowa State University (2009)"},{"issue":"Suppl 5","key":"11_CR11","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1471-2105-14-S5-S7","volume":"14","author":"E Kapun","year":"2013","unstructured":"Kapun, E., Tsarev, F.: De Bruijn superwalk with multiplicities problem is NP-hard. BMC Bioinform. 14(Suppl 5), S7 (2013)","journal-title":"BMC Bioinform."},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-3-642-40453-5_6","volume-title":"Algorithms in Bioinformatics","author":"E Kapun","year":"2013","unstructured":"Kapun, E., Tsarev, F.: On NP-hardness of the paired de Bruijn sound cycle problem. In: Darling, A., Stoye, J. (eds.) WABI 2013. LNCS, vol. 8126, pp. 59\u201369. Springer, Heidelberg (2013)"},{"issue":"1\/2","key":"11_CR13","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu, J.D., Myers, E.W.: Combinatiorial algorithms for DNA sequence assembly. Algorithmica 13(1\/2), 7\u201351 (1995)","journal-title":"Algorithmica"},{"key":"11_CR14","unstructured":"Kececioglu, J.D.: Exact and approximation algorithms for DNA sequence reconstruction. Ph.D. thesis, University of Arizona, Tucson, AZ, USA (1992)"},{"issue":"1","key":"11_CR15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1471-2105-11-21","volume":"11","author":"C Kingsford","year":"2010","unstructured":"Kingsford, C., et al.: Assembly complexity of prokaryotic genomes using short reads. BMC Bioinform. 11(1), 21 (2010)","journal-title":"BMC Bioinform."},{"issue":"S\u20139","key":"11_CR16","doi-asserted-by":"crossref","first-page":"S4","DOI":"10.1186\/1471-2105-15-S9-S4","volume":"15","author":"K Lam","year":"2014","unstructured":"Lam, K., et al.: Near-optimal assembly for shotgun sequencing with noisy reads. BMC Bioinform. 15(S\u20139), S4 (2014)","journal-title":"BMC Bioinform."},{"issue":"3","key":"11_CR17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0888-7543(88)90007-9","volume":"2","author":"ES Lander","year":"1988","unstructured":"Lander, E.S., Waterman, M.S.: Genomic mapping by fingerprinting random clones: a mathematical analysis. Genomics 2(3), 231\u2013239 (1988)","journal-title":"Genomics"},{"issue":"1","key":"11_CR18","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/2047-217X-1-18","volume":"1","author":"R Luo","year":"2012","unstructured":"Luo, R., et al.: SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler. GigaScience 1(1), 18 (2012)","journal-title":"GigaScience"},{"issue":"6","key":"11_CR19","first-page":"1508","volume":"303","author":"I Lysov","year":"1988","unstructured":"Lysov, I., et al.: Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. a new method. Dokl Akad Nauk SSSR 303(6), 1508\u20131511 (1988)","journal-title":"Dokl Akad Nauk SSSR"},{"issue":"8","key":"11_CR20","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1089\/cmb.2009.0047","volume":"16","author":"P Medvedev","year":"2009","unstructured":"Medvedev, P., Brudno, M.: Maximum likelihood genome assembly. J. Comp. Biol. 16(8), 1101\u20131116 (2009)","journal-title":"J. Comp. Biol."},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science (Lecture Notes in Bioinformatics)","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-540-74126-8_27","volume-title":"Algorithms in Bioinformatics","author":"P Medvedev","year":"2007","unstructured":"Medvedev, P., Georgiou, K., Myers, G., Brudno, M.: Computability of models for sequence assembly. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS (LNBI), vol. 4645, pp. 289\u2013301. Springer, Heidelberg (2007)"},{"issue":"11","key":"11_CR22","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.1089\/cmb.2011.0151","volume":"18","author":"P Medvedev","year":"2011","unstructured":"Medvedev, P., et al.: Paired de Bruijn graphs: a novel approach for incorporating mate pair information into genome assemblers. J. Comp. Biol. 18(11), 1625\u20131634 (2011)","journal-title":"J. Comp. Biol."},{"issue":"6","key":"11_CR23","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","volume":"95","author":"JR Miller","year":"2010","unstructured":"Miller, J.R., et al.: Assembly algorithms for next-generation sequencing data. Genomics 95(6), 315\u2013327 (2010)","journal-title":"Genomics"},{"issue":"10","key":"11_CR24","doi-asserted-by":"crossref","first-page":"6273","DOI":"10.1109\/TIT.2013.2270273","volume":"59","author":"AS Motahari","year":"2013","unstructured":"Motahari, A.S., et al.: Information theory of DNA shotgun sequencing. IEEE Trans. Inf. Theory 59(10), 6273\u20136289 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Myers, E.W.: The fragment assembly string graph. In: ECCB\/JBI, p. 85 (2005)","DOI":"10.1093\/bioinformatics\/bti1114"},{"issue":"7","key":"11_CR26","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1089\/cmb.2009.0005","volume":"16","author":"N Nagarajan","year":"2009","unstructured":"Nagarajan, N., Pop, M.: Parametric complexity of sequence assembly: theory and applications to next generation sequencing. J. Comp. Biol. 16(7), 897\u2013908 (2009)","journal-title":"J. Comp. Biol."},{"issue":"3","key":"11_CR27","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1038\/nrg3367","volume":"14","author":"N Nagarajan","year":"2013","unstructured":"Nagarajan, N., Pop, M.: Sequence assembly demystified. Nat. Rev. Genet. 14(3), 157\u2013167 (2013)","journal-title":"Nat. Rev. Genet."},{"key":"11_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-319-07953-0_15","volume-title":"Algorithms for Computational Biology","author":"G Narzisi","year":"2014","unstructured":"Narzisi, G., Mishra, B., Schatz, M.C.: On algorithmic complexity of biomolecular sequence assembly problem. In: Dediu, A.-H., Mart\u00edn-Vide, C., Truthe, B. (eds.) AlCoB 2014. LNCS, vol. 8542, pp. 183\u2013195. Springer, Heidelberg (2014)"},{"key":"11_CR29","unstructured":"Peltola, H., et al.: Algorithms for some string matching problems arising in molecular genetics. In: IFIP Congress, 59\u201364 (1983)"},{"issue":"1","key":"11_CR30","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","volume":"7","author":"PA Pevzner","year":"1989","unstructured":"Pevzner, P.A.: L-Tuple DNA sequencing: computer analysis. J. Biomol. Struct. Dyn. 7(1), 63\u201373 (1989)","journal-title":"J. Biomol. Struct. Dyn."},{"issue":"17","key":"11_CR31","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner, P.A., et al.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. 98(17), 9748\u20139753 (2001)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"11_CR32","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1089\/cmb.1995.2.371","volume":"2","author":"AR Rubinov","year":"1995","unstructured":"Rubinov, A.R., Gelfand, M.S.: Reconstruction of a string from substring precedence data. J. Comp. Biol. 2(2), 371\u2013381 (1995)","journal-title":"J. Comp. Biol."},{"issue":"1","key":"11_CR33","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1186\/1471-2105-15-281","volume":"15","author":"K Sahlin","year":"2014","unstructured":"Sahlin, K., et al.: BESST-efficient scaffolding of large fragmented assemblies. BMC Bioinform. 15(1), 281 (2014)","journal-title":"BMC Bioinform."},{"key":"11_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-319-16706-0_29","volume-title":"Research in Computational Molecular Biology","author":"L Salmela","year":"2015","unstructured":"Salmela, L., Sahlin, K., M\u00e4kinen, V., Tomescu, A.I.: Gap filling as exact path length problem. In: Przytycka, T.M. (ed.) RECOMB 2015. LNCS, vol. 9029, pp. 281\u2013292. Springer, Heidelberg (2015)"},{"key":"11_CR35","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1101\/gr.131383.111","volume":"22","author":"SL Salzberg","year":"2012","unstructured":"Salzberg, S.L., et al.: GAGE: a critical evaluation of genome assemblies and assembly algorithms. Genome Res. 22, 557\u2013567 (2012)","journal-title":"Genome Res."},{"issue":"12","key":"11_CR36","doi-asserted-by":"crossref","first-page":"i367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"JT Simpson","year":"2010","unstructured":"Simpson, J.T., Durbin, R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics 26(12), i367\u2013i373 (2010)","journal-title":"Bioinformatics"},{"key":"11_CR37","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"JT Simpson","year":"2012","unstructured":"Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22, 549\u2013556 (2012)","journal-title":"Genome Res."},{"key":"11_CR38","unstructured":"Tomescu, A.I., Medvedev, P.: Safe and complete contig assembly via omnitigs (2016). http:\/\/arxiv.org\/abs\/1601.02932"},{"issue":"2","key":"11_CR39","doi-asserted-by":"crossref","first-page":"e11","DOI":"10.1093\/nar\/gku1187","volume":"43","author":"R Uricaru","year":"2015","unstructured":"Uricaru, R., et al.: Reference-free detection of isolated SNPs. Nucleic Acids Res. 43(2), e11 (2015)","journal-title":"Nucleic Acids Res."},{"key":"11_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-642-33122-0_20","volume-title":"Algorithms in Bioinformatics","author":"N Vyahhi","year":"2012","unstructured":"Vyahhi, N., Pyshkin, A., Pham, S., Pevzner, P.A.: From de Bruijn graphs to rectangle graphs for genome assembly. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol. 7534, pp. 249\u2013261. Springer, Heidelberg (2012)"},{"issue":"5","key":"11_CR41","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"DR Zerbino","year":"2008","unstructured":"Zerbino, D.R., Birney, E.: Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. 18(5), 821\u2013829 (2008)","journal-title":"Genome Res."}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-31957-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T06:11:17Z","timestamp":1567750277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-31957-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319319568","9783319319575"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-31957-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}