{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:29Z","timestamp":1746331409487,"version":"3.40.4"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079523"},{"type":"electronic","value":"9783319079530"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07953-0_15","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:58:08Z","timestamp":1402419488000},"page":"183-195","source":"Crossref","is-referenced-by-count":2,"title":["On Algorithmic Complexity of Biomolecular Sequence Assembly Problem"],"prefix":"10.1007","author":[{"given":"Giuseppe","family":"Narzisi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bud","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael C.","family":"Schatz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/3-540-61258-0_8","volume-title":"Combinatorial Pattern Matching","author":"C. Armen","year":"1996","unstructured":"Armen, C., Stein, C.: A 2 2\/3-approximation algorithm for the shortest superstring problem. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 87\u2013101. Springer, Heidelberg (1996)"},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/2047-217X-2-10","volume":"2","author":"K. Bradnam","year":"2013","unstructured":"Bradnam, K., et al.: Assemblathon 2: evaluating de novo methods of genome assembly in three vertebrate species. GigaScience\u00a02(1), 10 (2013)","journal-title":"GigaScience"},{"issue":"3","key":"15_CR3","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1090\/S0002-9947-1936-1501858-0","volume":"39","author":"A. Church","year":"1936","unstructured":"Church, A., Rosser, J.B.: Some properties of conversion. Transactions of the American Mathematical Society\u00a039(3), 472\u2013482 (1936)","journal-title":"Transactions of the American Mathematical Society"},{"key":"15_CR4","unstructured":"Earl, D.A., et al.: Assemblathon 1: A competitive assessment of de novo short read assembly methods. Genome Research (2011)"},{"issue":"1","key":"15_CR5","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"Gallant, J., Maier, D., Astorer, J.: On finding minimal length superstrings. Journal of Computer and System Sciences\u00a020(1), 50\u201358 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1073\/pnas.1017351108","volume":"108","author":"S. Gnerre","year":"2011","unstructured":"Gnerre, S., et al.: High-quality draft assemblies of mammalian genomes from massively parallel sequence data. Proceedings of the National Academy of Sciences\u00a0108(4), 1513\u20131518 (2011)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Hierholzer, C., Wiener, C.: Ueber die mglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Mathematische Annalen\u00a06(1), 30\u201332 (1873)","DOI":"10.1007\/BF01442866"},{"issue":"2","key":"15_CR8","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z. Iqbal","year":"2012","unstructured":"Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., McVean, G.: De novo assembly and genotyping of variants using colored de bruijn graphs. Nature Genetics\u00a044(2), 226\u2013232 (2012)","journal-title":"Nature Genetics"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: The role of algorithmic research in computational genomics. In: Computational Systems Bioinformatics Conf, p. 10. IEEE Computer Society (2003)","DOI":"10.1109\/CSB.2003.1227288"},{"issue":"1","key":"15_CR10","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1471-2105-11-21","volume":"11","author":"C. Kingsford","year":"2010","unstructured":"Kingsford, C., Schatz, M., Pop, M.: Assembly complexity of prokaryotic genomes using short reads. BMC Bioinformatics\u00a011(1), 21 (2010)","journal-title":"BMC Bioinformatics"},{"issue":"7","key":"15_CR11","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1038\/nbt.2280","volume":"30","author":"S. Koren","year":"2012","unstructured":"Koren, S., et al.: Hybrid error correction and de novo assembly of single-molecule sequencing reads. Nature Biotechnology\u00a030(7), 693\u2013700 (2012)","journal-title":"Nature Biotechnology"},{"issue":"2","key":"15_CR12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1101\/gr.097261.109","volume":"20","author":"R. Li","year":"2010","unstructured":"Li, R., et al.: De novo assembly of human genomes with massively parallel short read sequencing. Genome Research\u00a020(2), 265\u2013272 (2010)","journal-title":"Genome Research"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Li, S., Li, R., Li, H., Lu, J., Li, Y., Bolund, L., Schierup, M., Wang, J.: Soapindel: Efficient identification of indels from short paired reads. Genome Research (2012)","DOI":"10.1101\/gr.132480.111"},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tig.2007.12.007","volume":"24","author":"E.R. Mardis","year":"2008","unstructured":"Mardis, E.R.: The impact of next-generation sequencing technology on genetics. Trends in Genetics\u00a024(3), 133\u2013141 (2008)","journal-title":"Trends in Genetics"},{"key":"15_CR15","series-title":"LNBI","doi-asserted-by":"publisher","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.\u00a04645, pp. 289\u2013301. Springer, Heidelberg (2007)"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1089\/cmb.1995.2.275","volume":"2","author":"E.W. Myers","year":"1995","unstructured":"Myers, E.W.: Toward simplifying and accurately formulating fragment assembly. Journal of Computational Biology\u00a02, 275\u2013290 (1995)","journal-title":"Journal of Computational Biology"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Myers, E.W.: The fragment assembly string graph. Bioinformatics\u00a021(suppl. 2), ii79\u2013ii85 (2005)","DOI":"10.1093\/bioinformatics\/bti1114"},{"issue":"7","key":"15_CR18","doi-asserted-by":"publisher","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. Journal of Computational Biology\u00a016(7), 897\u2013908 (2009)","journal-title":"Journal of Computational Biology"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Narzisi, G., Mishra, B.: Comparing de novo genome assembly: The long and short of it. PLoS ONE\u00a06(4), e19175 (2011)","DOI":"10.1371\/journal.pone.0019175"},{"issue":"2","key":"15_CR20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1093\/bioinformatics\/btq646","volume":"27","author":"G. Narzisi","year":"2011","unstructured":"Narzisi, G., Mishra, B.: Scoring-and-unfolding trimmed tree assembler: concepts, constructs and comparisons. Bioinformatics\u00a027(2), 153\u2013160 (2011)","journal-title":"Bioinformatics"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Narzisi, G., O\u2019Rawe, J.A., Iossifov, I.: ha\u00a0Lee, Y., Wang, Z., Wu, Y., Lyon, G.J., Wigler, M., Schatz, M.C.: Accurate detection of de novo and transmitted indels within exome-capture data using micro-assembly. bioRxiv (2013)","DOI":"10.1101\/001370"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01405730","volume":"4","author":"H.W.J. Rittel","year":"1973","unstructured":"Rittel, H.W.J., Webber, M.M.: Dilemmas in a general theory of planning. Policy Sciences\u00a04, 155\u2013169 (1973)","journal-title":"Policy Sciences"},{"issue":"7","key":"15_CR23","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1186\/gb-2013-14-6-405","volume":"14","author":"R. Roberts","year":"2013","unstructured":"Roberts, R., Carneiro, M., Schatz, M.: The advantages of smrt sequencing. Genome Biology\u00a014(7), 405 (2013)","journal-title":"Genome Biology"},{"issue":"1","key":"15_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. Journal of Molecular Biology\u00a0147(1), 195\u2013197 (1981)","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"15_CR25","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"Tarhio, J., Ukkonen, E.: A greedy approximation algorithm for constructing shortest common superstrings. Theor. Comput. Sci.\u00a057(1), 131\u2013145 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"15_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J.S. Turner","year":"1989","unstructured":"Turner, J.S.: Approximation algorithms for the shortest common superstring problem. Inf. Comput.\u00a083(1), 1\u201320 (1989)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms for Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07953-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:06:24Z","timestamp":1746263184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07953-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079523","9783319079530"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07953-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}