{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T16:49:18Z","timestamp":1772729358022,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T00:00:00Z","timestamp":1702166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["851093"],"award-info":[{"award-number":["851093"]}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["322595, 328877"],"award-info":[{"award-number":["322595, 328877"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (\n            <jats:italic>unitigs<\/jats:italic>\n            ) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a\n            <jats:italic>closed arc-covering walk<\/jats:italic>\n            of the graph, then unitigs appear in all solutions, being thus\n            <jats:italic>safe<\/jats:italic>\n            partial solutions. Until recently, it was open what are\n            <jats:italic>all<\/jats:italic>\n            the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (\n            <jats:italic>omnitigs<\/jats:italic>\n            ), thus giving the first safe and\n            <jats:italic>complete<\/jats:italic>\n            genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et\u00a0al.\u00a0(ACM Trans.\u00a0Algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs.\n          <\/jats:p>\n          <jats:p>\n            We answer this question affirmatively, by describing a surprising\n            <jats:italic>O(m)<\/jats:italic>\n            -time algorithm to\n            <jats:italic>identify<\/jats:italic>\n            all maximal omnitigs of a graph with\n            <jats:italic>n<\/jats:italic>\n            nodes and\n            <jats:italic>m<\/jats:italic>\n            arcs, notwithstanding the existence of families of graphs with\n            <jats:italic>\u0398 (mn)<\/jats:italic>\n            total maximal omnitig size. This is based on the discovery of a family of walks (\n            <jats:italic>macrotigs<\/jats:italic>\n            ) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A\n            <jats:italic>linear-time output-sensitive<\/jats:italic>\n            algorithm enumerating all maximal omnitigs. (2) A\n            <jats:italic>\n              compact\n              <jats:italic>O(m)<\/jats:italic>\n              representation\n            <\/jats:italic>\n            of all maximal omnitigs, which allows, e.g., for\n            <jats:italic>O(m)<\/jats:italic>\n            -time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and\n            <jats:italic>complete<\/jats:italic>\n            genome assembly programs, as has been the case for other key Bioinformatics problems.\n          <\/jats:p>","DOI":"10.1145\/3632176","type":"journal-article","created":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T11:56:01Z","timestamp":1699444561000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Genome Assembly, from Practice to Theory: Safe, Complete and\n            <i>Linear-Time<\/i>"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-756X","authenticated-orcid":false,"given":"Massimo","family":"Cairo","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2387-0952","authenticated-orcid":false,"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5302-0580","authenticated-orcid":false,"given":"Elia C.","family":"Zirondelli","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Trento, Italy and Department of Computer Science, University of Verona, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,10]]},"reference":[{"key":"e_1_3_5_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_5_3_2","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-018-0122-7"},{"issue":"3","key":"e_1_3_5_4_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul Stephen F.","year":"1990","unstructured":"Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman. 1990. Basic local alignment search tool. Journal of Molecular Biology 215, 3 (1990), 403\u2013410.","journal-title":"Journal of Molecular Biology"},{"key":"e_1_3_5_5_2","first-page":"51","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015","author":"Backurs Arturs","year":"2015","unstructured":"Arturs Backurs and Piotr Indyk. 2015. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, Portland, OR, USA, 51\u201358. DOI:10.1145\/2746539.2746612"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591885"},{"key":"e_1_3_5_8_2","first-page":"2053","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016","author":"Belazzougui Djamal","year":"2016","unstructured":"Djamal Belazzougui and Simon J. Puglisi. 2016. Range predecessor and Lempel-Ziv parsing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, Robert Krauthgamer (Ed.). SIAM, Arlington, VA, USA, 2053\u20132071. DOI:10.1137\/1.9781611974331.ch143"},{"issue":"11","key":"e_1_3_5_9_2","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1089\/cmb.2009.0238","article-title":"Ray: Simultaneous assembly of reads from a mix of high-throughput sequencing technologies","volume":"17","author":"Boisvert S\u00e9bastien","year":"2010","unstructured":"S\u00e9bastien Boisvert, Fran\u00e7ois Laviolette, and Jacques Corbeil. 2010. Ray: Simultaneous assembly of reads from a mix of high-throughput sequencing technologies. Journal of Computational Biology 17, 11 (2010), 1519\u20131533.","journal-title":"Journal of Computational Biology"},{"issue":"5","key":"e_1_3_5_10_2","doi-asserted-by":"crossref","first-page":"S18","DOI":"10.1186\/1471-2105-14-S5-S18","article-title":"Optimal assembly for high throughput shotgun sequencing","volume":"14","author":"Bresler G.","year":"2013","unstructured":"G. Bresler, M. Bresler, and D. Tse. 2013. Optimal assembly for high throughput shotgun sequencing. BMC Bioinformatics 14, Suppl. 5 (2013), S18.","journal-title":"BMC Bioinformatics"},{"key":"e_1_3_5_11_2","first-page":"1","article-title":"The hydrostructure: A universal framework for safe and complete algorithms for genome assembly","volume":"2011","author":"Cairo Massimo","year":"2021","unstructured":"Massimo Cairo, Shahbaz Khan, Romeo Rizzi, Sebastian S. Schmidt, Alexandru I. Tomescu, and Elia C. Zirondelli. 2021. The hydrostructure: A universal framework for safe and complete algorithms for genome assembly. arXiv abs\/2011.12635 (2021), 1\u201338. https:\/\/arxiv.org\/abs\/2011.12635","journal-title":"arXiv"},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341731"},{"key":"e_1_3_5_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01194399"},{"key":"e_1_3_5_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/9.4.387"},{"key":"e_1_3_5_15_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt310"},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90049-3"},{"key":"e_1_3_5_17_2","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/3313276.3316390","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)","author":"Dudek Bart\u0142omiej","year":"2019","unstructured":"Bart\u0142omiej Dudek and Pawe\u0142 Gawrychowski. 2019. Computing quartet distance is equivalent to counting 4-cycles. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). Association for Computing Machinery, New York, NY, USA, 733\u2013743. DOI:10.1145\/3313276.3316390"},{"key":"e_1_3_5_18_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin Richard","year":"1998","unstructured":"Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge, United Kingdom."},{"key":"e_1_3_5_19_2","first-page":"1","article-title":"K-best enumeration","volume":"115","author":"Eppstein David","year":"2015","unstructured":"David Eppstein. 2015. K-best enumeration. Bulletin of the EATCS 115 (2015), 1\u201325. http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/322","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_733"},{"key":"e_1_3_5_21_2","series-title":"LIPIcs","first-page":"55:1\u201355:15","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece","author":"Equi Massimo","year":"2019","unstructured":"Massimo Equi, Roberto Grossi, Veli M\u00e4kinen, and Alexandru I. Tomescu. 2019. On the complexity of string matching for graphs. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece(LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Patras, Greece, 55:1\u201355:15. DOI:10.4230\/LIPIcs.ICALP.2019.55"},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892127"},{"key":"e_1_3_5_23_2","first-page":"768","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009","author":"Ferragina Paolo","year":"2009","unstructured":"Paolo Ferragina, Igor Nitto, and Rossano Venturini. 2009. On the bit-complexity of Lempel-Ziv compression. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, Claire Mathieu (Ed.). SIAM, New York, NY, USA, 768\u2013777. DOI:10.1137\/1.9781611973068"},{"issue":"3","key":"e_1_3_5_24_2","first-page":"261","article-title":"A new approach for displaying identities and differences among aligned amino acid sequences.","volume":"8","author":"Friemann A.","year":"1992","unstructured":"A. Friemann and S. Schmitz. 1992. A new approach for displaying identities and differences among aligned amino acid sequences. Comput. Appl. Biosci. 8, 3 (June 1992), 261\u2013265.","journal-title":"Comput. Appl. Biosci."},{"key":"e_1_3_5_25_2","first-page":"1880","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19","author":"Georgiadis Loukas","year":"2017","unstructured":"Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. 2017. Strong connectivity in directed graphs under failures, with applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, Philip N. Klein (Ed.). SIAM, Barcelona, Spain, 1880\u20131899. DOI:10.1137\/1.9781611974782.123"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_728"},{"key":"e_1_3_5_27_2","first-page":"237","article-title":"Graphic programming using odd and even points","volume":"1","author":"Guan Meigu","year":"1962","unstructured":"Meigu Guan. 1962. Graphic programming using odd and even points. Chinese Math. 1 (1962), 237\u2013277.","journal-title":"Chinese Math."},{"issue":"6","key":"e_1_3_5_28_2","first-page":"569","article-title":"Can we recover a sequence, just knowing all its subsequences of given length?","volume":"8","author":"Gu\u00e9noche A.","year":"1992","unstructured":"A. Gu\u00e9noche. 1992. Can we recover a sequence, just knowing all its subsequences of given length? Computer Applications in the Biosciences 8, 6 (1992), 569\u2013574. http:\/\/dblp.uni-trier.de\/db\/journals\/bioinformatics\/bioinformatics8.html#Guenoche92","journal-title":"Computer Applications in the Biosciences"},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603052"},{"issue":"6","key":"e_1_3_5_30_2","first-page":"1508","article-title":"Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method","volume":"303","author":"Lysov Iu P.","year":"1988","unstructured":"Iu P. Lysov, V. L. Florent\u2019ev, A. A. Khorlin, K. R. Khrapko, and V. V. Shik. 1988. Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method. Doklady Akademii nauk SSSR 303, 6 (1988), 1508\u20131511. http:\/\/view.ncbi.nlm.nih.gov\/pubmed\/3250844","journal-title":"Doklady Akademii nauk SSSR"},{"key":"e_1_3_5_31_2","volume-title":"Parallel Methods for Short Read Assembly","author":"Jackson Benjamin Grant","year":"2009","unstructured":"Benjamin Grant Jackson. 2009. Parallel Methods for Short Read Assembly. Ph.D. Dissertation. Iowa State University."},{"issue":"5","key":"e_1_3_5_32_2","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1471-2105-14-S5-S7","article-title":"De Bruijn Superwalk with multiplicities problem is NP-hard","volume":"14","author":"Kapun Evgeny","year":"2013","unstructured":"Evgeny Kapun and Fedor Tsarev. 2013. De Bruijn Superwalk with multiplicities problem is NP-hard. BMC Bioinformatics 14, Suppl. 5 (2013), S7.","journal-title":"BMC Bioinformatics"},{"key":"e_1_3_5_33_2","volume-title":"Exact and Approximation Algorithms for DNA Sequence Reconstruction","author":"Kececioglu John Dimitri","year":"1992","unstructured":"John Dimitri Kececioglu. 1992. Exact and Approximation Algorithms for DNA Sequence Reconstruction. Ph.D. Dissertation. University of Arizona, Tucson, AZ, USA."},{"issue":"1","key":"e_1_3_5_34_2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","article-title":"Combinatorial algorithms for DNA sequence assembly.","volume":"13","author":"Kececioglu John D.","year":"1995","unstructured":"John D. Kececioglu and Eugene W. Myers. 1995. Combinatorial algorithms for DNA sequence assembly. Algorithmica 13, 1\/2 (1995), 7\u201351.","journal-title":"Algorithmica"},{"key":"e_1_3_5_35_2","first-page":"756","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019","author":"Kempa Dominik","year":"2019","unstructured":"Dominik Kempa and Tomasz Kociumaka. 2019. String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, Moses Charikar and Edith Cohen (Eds.). ACM, Phoenix, AZ, USA, 756\u2013767. DOI:10.1145\/3313276.3316368"},{"key":"e_1_3_5_36_2","first-page":"827","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018","author":"Kempa Dominik","year":"2018","unstructured":"Dominik Kempa and Nicola Prezza. 2018. At the roots of dictionary compression: String attractors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.). ACM, Los Angeles, CA, USA, 827\u2013840. DOI:10.1145\/3188745.3188814"},{"issue":"1","key":"e_1_3_5_37_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1471-2105-11-21","article-title":"Assembly complexity of prokaryotic genomes using short reads","volume":"11","author":"Kingsford Carl","year":"2010","unstructured":"Carl Kingsford, Michael C. Schatz, and Mihai Pop. 2010. Assembly complexity of prokaryotic genomes using short reads. BMC Bioinformatics 11, 1 (2010), 21.","journal-title":"BMC Bioinformatics"},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_731"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-S9-S4"},{"issue":"4","key":"e_1_3_5_40_2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead Ben","year":"2012","unstructured":"Ben Langmead and Steven L. Salzberg. 2012. Fast gapped-read alignment with Bowtie 2. Nature Methods 9, 4 (2012), 357.","journal-title":"Nature Methods"},{"issue":"10","key":"e_1_3_5_41_2","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1093\/bioinformatics\/btv033","article-title":"MEGAHIT: An ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph","volume":"31","author":"Li Dinghua","year":"2015","unstructured":"Dinghua Li, Chi-Man Liu, Ruibang Luo, Kunihiko Sadakane, and Tak-Wah Lam. 2015. MEGAHIT: An ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph. Bioinformatics 31, 10 (2015), 1674\u20131676.","journal-title":"Bioinformatics"},{"issue":"14","key":"e_1_3_5_42_2","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows\u2013Wheeler transform","volume":"25","author":"Li Heng","year":"2009","unstructured":"Heng Li and Richard Durbin. 2009. Fast and accurate short read alignment with Burrows\u2013Wheeler transform. Bioinformatics 25, 14 (2009), 1754\u20131760.","journal-title":"Bioinformatics"},{"key":"e_1_3_5_43_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023"},{"issue":"4","key":"e_1_3_5_44_2","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1093\/bib\/bby003","article-title":"Modeling biological problems in computer science: A case study in genome assembly","volume":"20","author":"Medvedev Paul","year":"2019","unstructured":"Paul Medvedev. 2019. Modeling biological problems in computer science: A case study in genome assembly. Briefings in Bioinformatics 20, 4 (2019), 1376\u20131383.","journal-title":"Briefings in Bioinformatics"},{"issue":"8","key":"e_1_3_5_45_2","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1089\/cmb.2009.0047","article-title":"Maximum likelihood genome assembly.","volume":"16","author":"Medvedev Paul","year":"2009","unstructured":"Paul Medvedev and Michael Brudno. 2009. Maximum likelihood genome assembly. Journal of Computational Biology 16, 8 (2009), 1101\u20131116.","journal-title":"Journal of Computational Biology"},{"key":"e_1_3_5_46_2","series-title":"Algorithms in Bioinformatics, 7th International Workshop, WABI 2007, Philadelphia, PA, USA, September 8-9, 2007, Proceedings","first-page":"289","volume":"4645","author":"Medvedev Paul","year":"2007","unstructured":"Paul Medvedev, Konstantinos Georgiou, Gene Myers, and Michael Brudno. 2007. Computability of models for sequence assembly. In Algorithms in Bioinformatics, 7th International Workshop, WABI 2007, Philadelphia, PA, USA, September 8-9, 2007, Proceedings(Lecture Notes in Computer Science, Vol. 4645), Raffaele Giancarlo and Sridhar Hannenhalli (Eds.). Springer, Philadelphia, PA, USA, 289\u2013301. DOI:10.1007\/978-3-540-74126-8_27"},{"issue":"2","key":"e_1_3_5_47_2","first-page":"ii79\u2013ii85","article-title":"The fragment assembly string graph","volume":"21","author":"Myers Eugene W.","year":"2005","unstructured":"Eugene W. Myers. 2005. The fragment assembly string graph. Bioinformatics 21, suppl_2 (2005), ii79\u2013ii85.","journal-title":"Bioinformatics"},{"issue":"7","key":"e_1_3_5_48_2","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1089\/cmb.2009.0005","article-title":"Parametric complexity of sequence assembly: Theory and applications to next generation sequencing","volume":"16","author":"Nagarajan Niranjan","year":"2009","unstructured":"Niranjan Nagarajan and Mihai Pop. 2009. Parametric complexity of sequence assembly: Theory and applications to next generation sequencing. Journal of Computational Biology 16, 7 (2009), 897\u2013908.","journal-title":"Journal of Computational Biology"},{"issue":"3","key":"e_1_3_5_49_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1038\/nrg3367","article-title":"Sequence assembly demystified","volume":"14","author":"Nagarajan Niranjan","year":"2013","unstructured":"Niranjan Nagarajan and Mihai Pop. 2013. Sequence assembly demystified. Nature Reviews Genetics 14, 3 (2013), 157\u2013167.","journal-title":"Nature Reviews Genetics"},{"key":"e_1_3_5_50_2","series-title":"Algorithms for Computational Biology - First International Conference, AlCoB 2014, Tarragona, Spain, July 1-3, 2014, Proceedings","first-page":"183","volume":"8542","author":"Narzisi Giuseppe","year":"2014","unstructured":"Giuseppe Narzisi, Bud Mishra, and Michael C. Schatz. 2014. On algorithmic complexity of biomolecular sequence assembly problem. In Algorithms for Computational Biology - First International Conference, AlCoB 2014, Tarragona, Spain, July 1-3, 2014, Proceedings(Lecture Notes in Computer Science, Vol. 8542), Adrian-Horia Dediu, Carlos Mart\u00edn-Vide, and Bianca Truthe (Eds.). Springer, Tarragona, Spain, 183\u2013195. DOI:10.1007\/978-3-319-07953-0_15"},{"key":"e_1_3_5_51_2","first-page":"59","volume-title":"Information Processing 83, Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19-23, 1983","author":"Peltola Hannu","year":"1983","unstructured":"Hannu Peltola, Hans S\u00f6derlund, Jorma Tarhio, and Esko Ukkonen. 1983. Algorithms for some string matching problems arising in molecular genetics. In Information Processing 83, Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19-23, 1983, R. E. A. Mason (Ed.). North-Holland\/IFIP, Paris, France, 59\u201364."},{"issue":"1","key":"e_1_3_5_52_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","article-title":"l-tuple DNA sequencing: Computer analysis","volume":"7","author":"Pevzner P. A.","year":"1989","unstructured":"P. A. Pevzner. 1989. l-tuple DNA sequencing: Computer analysis. Journal of Biomolecular Structure & Dynamics 7, 1 (Aug. 1989), 63\u201373.","journal-title":"Journal of Biomolecular Structure & Dynamics"},{"issue":"17","key":"e_1_3_5_53_2","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An Eulerian path approach to DNA fragment assembly.","volume":"98","author":"Pevzner Pavel A.","year":"2001","unstructured":"Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman. 2001. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences 98, 17 (2001), 9748\u20139753.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"9","key":"e_1_3_5_54_2","doi-asserted-by":"crossref","first-page":"1746","DOI":"10.1101\/gr.276601.122","article-title":"Assembler artifacts include misassembly because of unsafe unitigs and underassembly because of bidirected graphs","volume":"32","author":"Rahman Amatur","year":"2022","unstructured":"Amatur Rahman and Paul Medvedev. 2022. Assembler artifacts include misassembly because of unsafe unitigs and underassembly because of bidirected graphs. Genome Research 32, 9 (2022), 1746\u20131753.","journal-title":"Genome Research"},{"key":"e_1_3_5_55_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0669-3"},{"key":"e_1_3_5_56_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw450"},{"key":"e_1_3_5_57_2","series-title":"Research in Computational Molecular Biology - 20th Annual Conference, RECOMB 2016, Santa Monica, CA, USA, April 17-21, 2016, Proceedings","first-page":"152","volume":"9649","author":"Tomescu Alexandru I.","year":"2016","unstructured":"Alexandru I. Tomescu and Paul Medvedev. 2016. Safe and complete contig assembly via omnitigs. In Research in Computational Molecular Biology - 20th Annual Conference, RECOMB 2016, Santa Monica, CA, USA, April 17-21, 2016, Proceedings(Lecture Notes in Computer Science, Vol. 9649), Mona Singh (Ed.). Springer, Santa Monica, CA, USA, 152\u2013163. DOI:10.1007\/978-3-319-31957-5_11"},{"issue":"6","key":"e_1_3_5_58_2","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1089\/cmb.2016.0141","article-title":"Safe and complete contig assembly through omnitigs","volume":"24","author":"Tomescu Alexandru I.","year":"2017","unstructured":"Alexandru I. Tomescu and Paul Medvedev. 2017. Safe and complete contig assembly through omnitigs. Journal of Computational Biology 24, 6 (2017), 590\u2013602.","journal-title":"Journal of Computational Biology"},{"key":"e_1_3_5_59_2","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/3.7.565"},{"key":"e_1_3_5_60_2","first-page":"1671","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, January 4-6, 2015","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. 2015. Finding four-node subgraphs in triangle time. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, January 4-6, 2015, Piotr Indyk (Ed.). SIAM, San Diego, CA, USA, 1671\u20131680. DOI:10.1137\/1.9781611973730.111"},{"key":"e_1_3_5_61_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2008-3"},{"issue":"2","key":"e_1_3_5_62_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0022-2836(91)80062-Y","article-title":"Suboptimal sequence alignment in molecular biology. Alignment with error analysis.","volume":"221","author":"Zuker M.","year":"1991","unstructured":"M. Zuker. 1991. Suboptimal sequence alignment in molecular biology. Alignment with error analysis. J. Mol. Biol. 221, 2 (Sep. 1991), 403\u2013420.","journal-title":"J. Mol. Biol."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:55Z","timestamp":1750286995000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,10]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3632176"],"URL":"https:\/\/doi.org\/10.1145\/3632176","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,10]]},"assertion":[{"value":"2022-02-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}