SCARPA: scaffolding reads with practical algorithms
Authors:
Open Access
- 29 December 2012
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 29 (4) , 428-434
Abstract
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. 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. Availability: SCARPA is open source and available from http://compbio.cs.toronto.edu/scarpa. Contact: nild@cs.toronto.edu Supplementary information: Supplementary data are available at Bioinformatics online.Keywords
This publication has 19 references indexed in Scilit:
- Fast scaffolding with small independent mixed integer programsBioinformatics, 2011
- Assemblathon 1: A competitive assessment of de novo short read assembly methodsGenome Research, 2011
- Scaffolding pre-assembled contigs using SSPACEBioinformatics, 2010
- SOPRA: Scaffolding algorithm for paired reads via statistical optimizationBMC Bioinformatics, 2010
- Pebble and Rock Band: Heuristic Resolution of Repeats and Scaffolding in the Velvet Short-Read de Novo AssemblerPLOS ONE, 2009
- De novo genome sequence assembly of a filamentous fungus using Sanger, 454 and Illumina sequence dataGenome Biology, 2009
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- ABySS: A parallel assembler for short read sequence dataGenome Research, 2009
- Hierarchical Scaffolding With BambusGenome Research, 2004
- The greedy path-merging algorithm for contig scaffoldingJournal of the ACM, 2002