{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:24:51Z","timestamp":1773228291114,"version":"3.50.1"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Mired by its connection to a well-known \ud835\udca9\ud835\udcab-complete combinatorial optimization problem\u2014namely, the Shortest Common Superstring Problem (SCSP)\u2014historically, the whole-genome sequence assembly (WGSA) problem has been assumed to be amenable only to greedy and heuristic methods. By placing efficiency as their first priority, these methods opted to rely only on local searches, and are thus inherently approximate, ambiguous or error prone, especially, for genomes with complex structures. Furthermore, since choice of the best heuristics depended critically on the properties of (e.g. errors in) the input data and the available long range information, these approaches hindered designing an error free WGSA pipeline.<\/jats:p>\n               <jats:p>Results: We dispense with the idea of limiting the solutions to just the approximated ones, and instead favor an approach that could potentially lead to an exhaustive (exponential-time) search of all possible layouts. Its computational complexity thus must be tamed through a constrained search (Branch-and-Bound) and quick identification and pruning of implausible overlays. For his purpose, such a method necessarily relies on a set of score functions (oracles) that can combine different structural properties (e.g. transitivity, coverage, physical maps, etc.). We give a detailed description of this novel assembly framework, referred to as Scoring-and-Unfolding Trimmed Tree Assembler (SUTTA), and present experimental results on several bacterial genomes using next-generation sequencing technology data. We also report experimental evidence that the assembly quality strongly depends on the choice of the minimum overlap parameter k.<\/jats:p>\n               <jats:p>Availability and Implementation: SUTTA's binaries are freely available to non-profit institutions for research and educational purposes at http:\/\/www.bioinformatics.nyu.edu.<\/jats:p>\n               <jats:p>Contact: \u00a0narzisi@nyu.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq646","type":"journal-article","created":{"date-parts":[[2010,11,19]],"date-time":"2010-11-19T03:58:31Z","timestamp":1290139111000},"page":"153-160","source":"Crossref","is-referenced-by-count":24,"title":["Scoring-and-unfolding trimmed tree assembler: concepts, constructs and comparisons"],"prefix":"10.1093","volume":"27","author":[{"given":"Giuseppe","family":"Narzisi","sequence":"first","affiliation":[{"name":"1 Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012 and 2NYU School of Medicine, 550 First Avenue, New York, NY 10016, USA"}]},{"given":"Bud","family":"Mishra","sequence":"additional","affiliation":[{"name":"1 Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012 and 2NYU School of Medicine, 550 First Avenue, New York, NY 10016, USA"},{"name":"1 Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012 and 2NYU School of Medicine, 550 First Avenue, New York, NY 10016, USA"}]}],"member":"286","published-online":{"date-parts":[[2010,11,18]]},"reference":[{"key":"2023012512181264600_B1","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-45586-8_7","article-title":"Tsp cuts which do not conform to the template paradigm","volume-title":"Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School].","author":"Applegate","year":"2001"},{"key":"2023012512181264600_B2","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1101\/gr.7088808","article-title":"Short read fragment assembly of bacterial genomes","volume":"18","author":"Chaisson","year":"2008","journal-title":"Genome Res."},{"key":"2023012512181264600_B3","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theorem-proving","volume":"5","author":"Davis","year":"1962","journal-title":"Commun. ACM"},{"key":"2023012512181264600_B4","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1101\/gr.072033.107","article-title":"De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer","volume":"18","author":"Hernandez","year":"2008","journal-title":"Genome Res."},{"key":"2023012512181264600_B5","first-page":"10","article-title":"The role of algorithmic research in computational genomics","volume":"0","author":"Karp","year":"2003","journal-title":"Comput. Syst. Bioinformatics Conf. Int. IEEE Comput. Soc."},{"key":"2023012512181264600_B6","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","article-title":"Combinatorial algorithms for dna sequence assembly","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"2023012512181264600_B7","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1101\/gr.183201","article-title":"Assembly of the working draft of the human genome with GigAssembler","volume":"11","author":"Kent","year":"2001","journal-title":"Genome Res."},{"key":"2023012512181264600_B8","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometrica"},{"key":"2023012512181264600_B9","doi-asserted-by":"crossref","first-page":"5374","DOI":"10.1016\/j.tcs.2009.09.014","article-title":"Why greed works for shortest common superstring problem","volume":"410","author":"Ma","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"2023012512181264600_B10","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1089\/cmb.1995.2.275","article-title":"Toward simplifying and accurately formulating fragment assembly","volume":"2","author":"Myers","year":"1995","journal-title":"J. Comput. Biol."},{"key":"2023012512181264600_B11","doi-asserted-by":"crossref","first-page":"R55","DOI":"10.1186\/gb-2008-9-3-r55","article-title":"Genome assembly forensics: finding the elusive mis-assembly","volume":"9","author":"Phillippy","year":"2008","journal-title":"Genome Biol."},{"key":"2023012512181264600_B12","doi-asserted-by":"crossref","first-page":"5463","DOI":"10.1073\/pnas.74.12.5463","article-title":"DNA sequencing with chain-terminating inhibitors","volume":"74","author":"Sanger","year":"1977","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012512181264600_B13","doi-asserted-by":"crossref","first-page":"2279","DOI":"10.1093\/bioinformatics\/btp374","article-title":"A fast hybrid short read fragment assembly algorithm","volume":"25","author":"Schmidt","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512181264600_B14","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1002\/0470867302.ch5","article-title":"Assembling a view of the human genome","volume-title":"Bioinformatics for Geneticists","author":"Semple","year":"2003"},{"key":"2023012512181264600_B15","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res."},{"key":"2023012512181264600_B16","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012512181264600_B17","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","article-title":"A greedy approximation algorithm for constructing shortest common superstrings","volume":"57","author":"Tarhio","year":"1988","journal-title":"Theor. Comput. Sci."},{"key":"2023012512181264600_B18","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btl629","article-title":"Assembling millions of short DNA sequences using SSAKE","volume":"23","author":"Warren","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012512181264600_B19","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: Algorithms for de novo short read assembly using de Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/2\/153\/48870177\/bioinformatics_27_2_153.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/2\/153\/48870177\/bioinformatics_27_2_153.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T14:57:24Z","timestamp":1674658644000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/2\/153\/286078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,18]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq646","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,1,15]]},"published":{"date-parts":[[2010,11,18]]}}}