{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:34:02Z","timestamp":1773275642387,"version":"3.50.1"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Scaffolding is the process of ordering and orienting contigs produced during genome assembly. Accurate scaffolding is essential for finishing draft assemblies, as it facilitates the costly and laborious procedures needed to fill in the gaps between contigs. Conventional formulations of the scaffolding problem are intractable, and most scaffolding programs rely on heuristic or approximate solutions, with potentially exponential running time.<\/jats:p>\n               <jats:p>Results: We present SCARPA, a novel scaffolder, which combines fixed-parameter tractable and bounded algorithms with Linear Programming to produce near-optimal scaffolds. We test SCARPA on real datasets in addition to a simulated diploid genome and compare its performance with several state-of-the-art scaffolders. We show that SCARPA produces longer or similar length scaffolds that are highly accurate compared with other scaffolders. SCARPA is also capable of detecting misassembled contigs and reports them during scaffolding.<\/jats:p>\n               <jats:p>Availability: SCARPA is open source and available from http:\/\/compbio.cs.toronto.edu\/scarpa.<\/jats:p>\n               <jats:p>Contact: nild@cs.toronto.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts716","type":"journal-article","created":{"date-parts":[[2012,12,30]],"date-time":"2012-12-30T01:14:02Z","timestamp":1356830042000},"page":"428-434","source":"Crossref","is-referenced-by-count":58,"title":["SCARPA: scaffolding reads with practical algorithms"],"prefix":"10.1093","volume":"29","author":[{"given":"Nilgun","family":"Donmez","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, 2Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, Toronto, ON, Canada M5S 3E1 and 3Centre for Computational Medicine, Hospital for Sick Children, Toronto, ON, Canada M5G 1L7"}]},{"given":"Michael","family":"Brudno","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, 2Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, Toronto, ON, Canada M5S 3E1 and 3Centre for Computational Medicine, Hospital for Sick Children, Toronto, ON, Canada M5G 1L7"},{"name":"1 Department of Computer Science, 2Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, Toronto, ON, Canada M5S 3E1 and 3Centre for Computational Medicine, Hospital for Sick Children, Toronto, ON, Canada M5G 1L7"},{"name":"1 Department of Computer Science, 2Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, Toronto, ON, Canada M5S 3E1 and 3Centre for Computational Medicine, Hospital for Sick Children, Toronto, ON, Canada M5G 1L7"}]}],"member":"286","published-online":{"date-parts":[[2012,12,29]]},"reference":[{"key":"2023012810260570600_bts716-B1","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","article-title":"Scaffolding pre-assembled contigs using SSPACE","volume":"27","author":"Boetzer","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012810260570600_bts716-B2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1186\/1471-2105-11-345","article-title":"SOPRA: scaffolding algorithm for paired reads via statistical optimization","volume":"11","author":"Dayarian","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012810260570600_bts716-B3","doi-asserted-by":"crossref","first-page":"2224","DOI":"10.1101\/gr.126599.111","article-title":"Assemblathon 1: a competitive assessment of de novo short read assembly methods","volume":"21","author":"Dent","year":"2011","journal-title":"Genome Res."},{"key":"2023012810260570600_bts716-B4","doi-asserted-by":"crossref","first-page":"R94","DOI":"10.1186\/gb-2009-10-9-r94","article-title":"De novo genome sequence assembly of a filamentous fungus using sanger, 454 and illumina sequence data","volume":"10","author":"DiGuistini","year":"2009","journal-title":"Genome Biol."},{"key":"2023012810260570600_bts716-B5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20036-6_5","article-title":"Hapsembler: an assembler for highly polymorphic genomes","volume-title":"Research in Computational Molecular Biology. Vol. 6577 of Lecture Notes in Computer Science","author":"Donmez","year":"2011"},{"key":"2023012810260570600_bts716-B6","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0020-0190(93)90079-O","article-title":"A fast effective heuristic for the feedback arc set problem","volume":"47","author":"Eades","year":"1993","journal-title":"Inf. Process. Lett."},{"key":"2023012810260570600_bts716-B7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20036-6_40","article-title":"Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences","volume-title":"Research in Computational Molecular Biology. Vol. 6577 of Lecture Notes in Computer Science","author":"Gao","year":"2011"},{"key":"2023012810260570600_bts716-B8","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","article-title":"Algorithm 447: efficient algorithms for graph manipulation","volume":"16","author":"Hopcroft","year":"1973","journal-title":"Commun. ACM"},{"key":"2023012810260570600_bts716-B9","doi-asserted-by":"crossref","first-page":"6003","DOI":"10.1145\/585265.585267","article-title":"The greedy path merging algorithm for contig scaffolding","volume":"49","author":"Huson","year":"2002","journal-title":"J. ACM"},{"key":"2023012810260570600_bts716-B10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume-title":"Complexity of computer computations","author":"Karp","year":"1972"},{"key":"2023012810260570600_bts716-B11","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012810260570600_bts716-B12","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023012810260570600_bts716-B13","first-page":"265","article-title":"De novo assembly of human genomes with massively parallel short read sequencing","volume":"20","author":"Li","year":"2009","journal-title":"Gemome Res."},{"key":"2023012810260570600_bts716-B14","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/978-3-642-10217-2_37","article-title":"Simpler parameterized algorithm for OCT","volume-title":"Combinatorial Algorithms","author":"Lokshtanov","year":"2009"},{"key":"2023012810260570600_bts716-B15","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1101\/gr.1536204","article-title":"Hierarchical scaffolding with bambus","volume":"14","author":"Pop","year":"2004","journal-title":"Genome Res."},{"key":"2023012810260570600_bts716-B16","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","article-title":"Finding odd cycle transversals","volume":"32","author":"Reed","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"2023012810260570600_bts716-B17","doi-asserted-by":"crossref","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","article-title":"Fast scaffolding with small independent mixed integer programs","volume":"27","author":"Salmela","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012810260570600_bts716-B18","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":"2023012810260570600_bts716-B19","doi-asserted-by":"crossref","first-page":"e8407","DOI":"10.1371\/journal.pone.0008407","article-title":"Pebble and rock band: heuristic resolution of repeats and scaffolding in the velvet short-read de novo assembler","volume":"4","author":"Zerbino","year":"2009","journal-title":"PLoS One"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/4\/428\/48899621\/bioinformatics_29_4_428.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/4\/428\/48899621\/bioinformatics_29_4_428.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:03:34Z","timestamp":1674907414000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/4\/428\/198425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,29]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts716","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,2,15]]},"published":{"date-parts":[[2012,12,29]]}}}