title: MeDuSa: a multi-draft based scaffolder.
abstract: BACKGROUND
  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.
  
  
  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.
authors: Department of Biology, ComBo, Florence Computational Biology Group, Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy.
authors: Emanuele
authors: E
authors: Bosi
authors: INRIA Rhône-Alpes, Villeurbanne Cedex, France, Université de Lyon, F-69000 Lyon, France, Dipartimento di Ingegneria dell'Informazione, University of Florence, I-50139 Firenze, Italy.
authors: Beatrice
authors: B
authors: Donati
authors: EMBL-EBI - European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, CB10 1SD Cambridge, UK.
authors: Marco
authors: M
authors: Galardini
authors: Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, University of Siena, Siena I-53100, Italy.
authors: Sara
authors: S
authors: Brunetti
authors: INRIA Rhône-Alpes, Villeurbanne Cedex, France, Université de Lyon, F-69000 Lyon, France, Université Lyon 1, CNRS,UMR5558, 69622 Villeurbanne Cedex, France and.
authors: Marie-France
authors: MF
authors: Sagot
authors: Computer Laboratory, University of Cambridge, CB3 0FD Cambridge, UK.
authors: Pietro
authors: P
authors: Lió
authors: Dipartimento di Ingegneria dell'Informazione, University of Florence, I-50139 Firenze, Italy.
authors: Pierluigi
authors: P
authors: Crescenzi
authors: Department of Biology, ComBo, Florence Computational Biology Group, Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy.
authors: Renato
authors: R
authors: Fani
authors: Department of Biology, ComBo, Florence Computational Biology Group, Department of Biology, LEMM, Laboratory of Microbial and Molecular Evolution Florence, University of Florence, I-50019 Sesto F.no, Italy.
authors: Marco
authors: M
authors: Fondi
mesh_terms: D000465:Algorithms; D020451:Contig Mapping / Q000379:methods*; D023281:Genomics / Q000379:methods*; D012984:Software