{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:18:25Z","timestamp":1752985105121,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T00:00:00Z","timestamp":1687392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000057","name":"National Institute of General Medical Sciences","doi-asserted-by":"publisher","award":["R01GM146462"],"award-info":[{"award-number":["R01GM146462"]}],"id":[{"id":"10.13039\/100000057","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2138585, 1453527, and 1931531"],"award-info":[{"award-number":["2138585, 1453527, and 1931531"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>A case study reveals the theoretical analysis of algorithms is not always as helpful as standard dogma might suggest.<\/jats:p>","DOI":"10.1145\/3571723","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T22:47:22Z","timestamp":1687474042000},"page":"118-125","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Theoretical Analysis of Sequencing Bioinformatics Algorithms and Beyond"],"prefix":"10.1145","volume":"66","author":[{"given":"Paul","family":"Medvedev","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Rainbowfish: A succinct colored de Bruijn graph representation","volume":"88","author":"Almodaresi F.","year":"2017","unstructured":"Almodaresi, F., Pandey, P., and Patro, R. Rainbowfish: A succinct colored de Bruijn graph representation. In Proceedings in Informatics Algorithms in Bioinformatics 88, 2017, 18:1--18:15. R. Schwartz and K. Reinert, eds. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","journal-title":"Proceedings in Informatics Algorithms in Bioinformatics"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1093\/bioinformatics\/bty292"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1089\/cmb.2012.0021"},{"key":"e_1_2_1_4_1","volume-title":"Succinct de Bruijn graphs. WABI 7534 LNCS","author":"Bowe A.","year":"2012","unstructured":"Bowe, A., Onodera, T., Sadakane, K., and Shibuya, T. Succinct de Bruijn graphs. WABI 7534 LNCS. Springer, 2012, 225--235."},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1186\/s13015-015-0052-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1186\/2047-217X-2-10"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1186\/1471-2105-14-S5-S18"},{"key":"e_1_2_1_8_1","volume-title":"et al. The hydrostructure: A universal framework for safe and complete algorithms for genome assembly. 2020","author":"Cairo M.","year":"2011","unstructured":"Cairo, M. et al. The hydrostructure: A universal framework for safe and complete algorithms for genome assembly. 2020; arXiv:2011.12635."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1038\/s41467-019-11146-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/3445967"},{"key":"e_1_2_1_11_1","volume-title":"Springer","author":"Chikhi R.","year":"2012","unstructured":"Chikhi, R. and Rizk, G. Space-efficient and exact de Bruijn graph representation based on a Bloom filter. WABI 7534 LNCS. B. Raphael and J. Tang, eds. Springer, 2012, 236--248."},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1093\/bioinformatics\/bts723"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1089\/cmb.2011.0170"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1186\/1756-0500-6-334"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1186\/s12915-014-0069-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1371\/journal.pone.0099497"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1186\/gb-2013-14-5-r47"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1016\/j.cell.2018.03.042"},{"key":"e_1_2_1_19_1","first-page":"039230","article-title":"Shannon: An information-optimal de novo RNA-Seq assembler","author":"Kannan S.","year":"2016","unstructured":"Kannan, S., Hui, J., Mazooji, K., Pachter, L., and Tse, D. Shannon: An information-optimal de novo RNA-Seq assembler. BioRxiv, 2016, 039230.","journal-title":"BioRxiv"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1093\/nar\/gkab1053"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1186\/1471-2105-11-21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1186\/s13059-019-1720-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1038\/nmeth.1923"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1186\/s13059-014-0553-5"},{"key":"e_1_2_1_25_1","volume-title":"et al. Megahit v1.0: A fast and scalable metagenome assembler driven by advanced methodologies and community practices. Methods 102","author":"Li D.","year":"2016","unstructured":"Li, D. et al. Megahit v1.0: A fast and scalable metagenome assembler driven by advanced methodologies and community practices. Methods 102 (2016), 3--11."},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1186\/s13059-019-1828-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1101\/gr.260604.119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1038\/nprot.2016.182"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1093\/bioinformatics\/bts566"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1089\/cmb.2009.0047"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1038\/nmeth.1374"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1089\/cmb.1995.2.275"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1089\/cmb.2009.0005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1371\/journal.pone.0019175"},{"volume-title":"Proceedings of the 2014 Intern. Conf. Algorithms for Computational Biology. Springer, 183--195","author":"Narzisi G.","unstructured":"Narzisi, G., Mishra, B., and Schatz, M.C. On algorithmic complexity of biomolecular sequence assembly problem. In Proceedings of the 2014 Intern. Conf. Algorithms for Computational Biology. Springer, 183--195.","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1017\/CBO9781316588284"},{"volume-title":"Proceedings of the 2017 ACM Intern. Conf. Management of Data. ACM","author":"Pandey P.","unstructured":"Pandey, P., Bender, M.A., Johnson, R., and Patro, R. A general-purpose counting filter: Making every bit count. In Proceedings of the 2017 ACM Intern. Conf. Management of Data. ACM, New York, NY, 775--787.","key":"e_1_2_1_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1038\/nmeth.4197"},{"key":"e_1_2_1_39_1","first-page":"168","article-title":"Representation of k-mer sets using spectrum-preserving string sets. In Proceedings of 24th Inter. Conf. Computational Molecular Biology 12074 LNCS","volume":"152","author":"Rahman A.","year":"2020","unstructured":"Rahman, A. and Medvedev, P. Representation of k-mer sets using spectrum-preserving string sets. In Proceedings of 24th Inter. Conf. Computational Molecular Biology 12074 LNCS. Springer, 2020, 152--168.","journal-title":"Springer"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1186\/gb-2013-14-1-r8"},{"key":"e_1_2_1_41_1","volume-title":"et al. Chasing perfection: validation and polishing strategies for telomere-to-telomere genome assemblies. bioRxiv","author":"Rhie A.","year":"2021","unstructured":"Rhie, A. et al. Chasing perfection: validation and polishing strategies for telomere-to-telomere genome assemblies. bioRxiv, 2021."},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1038\/s41586-021-03451-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1186\/s13059-020-02134-9"},{"key":"e_1_2_1_44_1","first-page":"3","article-title":"Beyond worst-case analysis","volume":"62","author":"Roughgarden T","year":"2019","unstructured":"Roughgarden, T. Beyond worst-case analysis. Commun. 62, 3 (Mar. 2019), 88--96.","journal-title":"Commun."},{"key":"e_1_2_1_45_1","volume-title":"Pearson Education India","author":"Sedgewick R.","year":"2013","unstructured":"Sedgewick, R. and Flajolet, P. An Introduction to the Analysis of Algorithms. Pearson Education India, 2013."},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1093\/bioinformatics\/btq217"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1146\/annurev-genom-090314-050032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1137\/1.9781611974768.2"},{"unstructured":"Titus Brown C. Thoughts on the Assemblathon 2 paper; http:\/\/ivory.idyll.org\/blog\/thoughts-on-Assemblathon-2.html.","key":"e_1_2_1_49_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1089\/cmb.2016.0141"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1109\/ICCABS.2011.5729873"},{"key":"e_1_2_1_52_1","first-page":"12","article-title":"Reevaluating assembly evaluations with feature response curves","volume":"7","author":"Vezzi F.","year":"2012","unstructured":"Vezzi, F., Narzisi, G., and Mishra, B. Reevaluating assembly evaluations with feature response curves: Gage and Assemblathons. PloS One 7, 12 (2012), e52210.","journal-title":"Gage and Assemblathons. PloS One"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1038\/nrg3373"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571723","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571723","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:33Z","timestamp":1750182573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571723"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,22]]},"references-count":53,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1145\/3571723"],"URL":"https:\/\/doi.org\/10.1145\/3571723","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2023,6,22]]},"assertion":[{"value":"2023-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}