{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T09:20:19Z","timestamp":1780651219505,"version":"3.54.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"15","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Completing the genome sequence of an organism is an important task in comparative, functional and structural genomics. However, this remains a challenging issue from both a computational and an experimental viewpoint. Genome scaffolding (i.e. the process of ordering and orientating contigs) of de novo assemblies usually represents the first step in most genome finishing pipelines.<\/jats:p>\n               <jats:p>Results: In this article we present MeDuSa (Multi-Draft based Scaffolder), an algorithm for genome scaffolding. MeDuSa exploits information obtained from a set of (draft or closed) genomes from related organisms to determine the correct order and orientation of the contigs. MeDuSa formalizes the scaffolding problem by means of a combinatorial optimization formulation on graphs and implements an efficient constant factor approximation algorithm to solve it. In contrast to currently used scaffolders, it does not require either prior knowledge on the microrganisms dataset under analysis (e.g. their phylogenetic relationships) or the availability of paired end read libraries. This makes usability and running time two additional important features of our method. Moreover, benchmarks and tests on real bacterial datasets showed that MeDuSa is highly accurate and, in most cases, outperforms traditional scaffolders. The possibility to use MeDuSa on eukaryotic datasets has also been evaluated, leading to interesting results.<\/jats:p>\n               <jats:p>Availability and implementation: MeDuSa web server: http:\/\/combo.dbe.unifi.it\/medusa. A stand-alone version of the software can be downloaded from https:\/\/github.com\/combogenomics\/medusa\/releases. All results presented in this work have been obtained with MeDuSa v. 1.3.<\/jats:p>\n               <jats:p>Contact: \u00a0marco.fondi@unifi.it<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv171","type":"journal-article","created":{"date-parts":[[2015,3,26]],"date-time":"2015-03-26T04:39:55Z","timestamp":1427344795000},"page":"2443-2451","source":"Crossref","is-referenced-by-count":393,"title":["M<scp>e<\/scp>D<scp>u<\/scp>S<scp>a<\/scp>: a multi-draft based scaffolder"],"prefix":"10.1093","volume":"31","author":[{"given":"Emanuele","family":"Bosi","sequence":"first","affiliation":[{"name":"1 Department of Biology, ComBo, Florence Computational Biology Group,"},{"name":"2 Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Beatrice","family":"Donati","sequence":"additional","affiliation":[{"name":"3 INRIA Rh\u00f4ne-Alpes, Villeurbanne Cedex, France,"},{"name":"4 Universit\u00e9 de Lyon, F-69000 Lyon, France,"},{"name":"5 Dipartimento di Ingegneria dell\u2019Informazione, University of Florence, I-50139 Firenze, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Galardini","sequence":"additional","affiliation":[{"name":"6 EMBL-EBI - European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, CB10 1SD Cambridge, UK,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sara","family":"Brunetti","sequence":"additional","affiliation":[{"name":"7 Dipartimento di Ingegneria dell\u2019Informazione e Scienze Matematiche, University of Siena, Siena I-53100, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marie-France","family":"Sagot","sequence":"additional","affiliation":[{"name":"3 INRIA Rh\u00f4ne-Alpes, Villeurbanne Cedex, France,"},{"name":"4 Universit\u00e9 de Lyon, F-69000 Lyon, France,"},{"name":"8 Universit\u00e9 Lyon 1, CNRS,UMR5558, 69622 Villeurbanne Cedex, France and"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pietro","family":"Li\u00f3","sequence":"additional","affiliation":[{"name":"9 Computer Laboratory, University of Cambridge, CB3 0FD Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[{"name":"5 Dipartimento di Ingegneria dell\u2019Informazione, University of Florence, I-50139 Firenze, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renato","family":"Fani","sequence":"additional","affiliation":[{"name":"1 Department of Biology, ComBo, Florence Computational Biology Group,"},{"name":"2 Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Fondi","sequence":"additional","affiliation":[{"name":"1 Department of Biology, ComBo, Florence Computational Biology Group,"},{"name":"2 Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"2023051308493478700_btv171-B1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1186\/1751-0473-7-4","article-title":"Scaffolder - software for manual genome scaffolding","volume":"7","author":"Barton","year":"2012","journal-title":"Source Code Biol. Med."},{"key":"2023051308493478700_btv171-B2","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":"2023051308493478700_btv171-B3","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1186\/1471-2105-11-485","article-title":"Solexaqa: at-a-glance quality assessment of illumina second-generation sequencing data","volume":"11","author":"Cox","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023051308493478700_btv171-B4","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1371\/journal.pone.0011147","article-title":"Progressivemauve: multiple genome alignment with gene gain, loss and rearrangement","volume":"5","author":"Darling","year":"2010","journal-title":"PLoS One"},{"key":"2023051308493478700_btv171-B5","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":"2023051308493478700_btv171-B6","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","article-title":"Scarpa: scaffolding reads with practical algorithms","volume":"29","author":"Donmez","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051308493478700_btv171-B7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.margen.2013.12.009","article-title":"Draft genomes of three antarctic psychrobacter strains producing antimicrobial compounds against burkholderia cepacia complex, opportunistic human pathogens","volume":"13","author":"Fondi","year":"2014","journal-title":"Mar. Genomics"},{"key":"2023051308493478700_btv171-B8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1751-0473-6-11","article-title":"Contiguator: a bacterial genomes finishing tool for structural insights on draft genomes","volume":"6","author":"Galardini","year":"2011","journal-title":"Source Code Biol. Med."},{"key":"2023051308493478700_btv171-B9","doi-asserted-by":"crossref","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","article-title":"Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences","volume":"18","author":"Gao","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023051308493478700_btv171-B10","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1093\/bioinformatics\/bts175","article-title":"Grass: a generic algorithm for scaffolding next-generation sequencing assemblies","volume":"28","author":"Gritsenko","year":"2012","journal-title":"Bioinformatics"},{"key":"2023051308493478700_btv171-B11","doi-asserted-by":"crossref","first-page":"R42","DOI":"10.1186\/gb-2014-15-3-r42","article-title":"A comprehensive evaluation of assembly scaffolding tools","volume":"15","author":"Hunt","year":"2014","journal-title":"Genome Biol."},{"key":"2023051308493478700_btv171-B12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-5-3","article-title":"Phylogenetic comparative assembly","volume":"5","author":"Husemann","year":"2010","journal-title":"Algorithms Mol. Biol."},{"key":"2023051308493478700_btv171-B13","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.1073\/pnas.1220349110","article-title":"Reference-assisted chromosome assembly","volume":"110","author":"Kim","year":"2013","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051308493478700_btv171-B14","doi-asserted-by":"crossref","first-page":"i302","DOI":"10.1093\/bioinformatics\/btu280","article-title":"Ragout-a reference-assisted assembly tool for bacterial genomes","volume":"30","author":"Kolmogorov","year":"2014","journal-title":"Bioinformatics"},{"key":"2023051308493478700_btv171-B15","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":"2023051308493478700_btv171-B16","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":"2023051308493478700_btv171-B17","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with burrows-wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023051308493478700_btv171-B18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230200106","article-title":"Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight","volume":"20","author":"Moran","year":"1990","journal-title":"Networks"},{"key":"2023051308493478700_btv171-B19","doi-asserted-by":"crossref","first-page":"2987","DOI":"10.1093\/bioinformatics\/btt527","article-title":"Fpsac: fast phylogenetic scaffolding of ancient contigs","volume":"29","author":"Rajaraman","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051308493478700_btv171-B20","doi-asserted-by":"crossref","first-page":"D1099","DOI":"10.1093\/nar\/gku950","article-title":"The genomes online database (gold) v.5: a metadata management system based on a four level (meta) genome project classification","volume":"43","author":"Reddy","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023051308493478700_btv171-B21","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1186\/1471-2105-9-518","article-title":"Algorithm of OMA for large-scale orthology inference","volume":"9","author":"Roth","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023051308493478700_btv171-B22","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":"2023051308493478700_btv171-B23","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1101\/gr.131383.111","article-title":"Gage: a critical evaluation of genome assemblies and assembly algorithms","volume":"22","author":"Salzberg","year":"2012","journal-title":"Genome Res."},{"key":"2023051308493478700_btv171-B24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1186\/1751-0473-8-23","article-title":"Combining de novo and reference-guided assembly with scaffold_builder","volume":"8","author":"Silva","year":"2013","journal-title":"Source Code Biol. Med."},{"key":"2023051308493478700_btv171-B25","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."},{"issue":"Web Server issue","key":"2023051308493478700_btv171-B26","doi-asserted-by":"crossref","first-page":"W560","DOI":"10.1093\/nar\/gki356","article-title":"Projector 2: contig mapping for efficient gap-closure of prokaryotic genome sequence assemblies","volume":"33","author":"van Hijum","year":"2005","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/15\/2443\/50306988\/bioinformatics_31_15_2443.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/15\/2443\/50306988\/bioinformatics_31_15_2443.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T08:50:46Z","timestamp":1683967846000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/15\/2443\/188083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":26,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2015,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv171","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,8,1]]},"published":{"date-parts":[[2015,3,25]]}}}