Format

Send to

Choose Destination
See comment in PubMed Commons below
Bioinformatics. 2013 Feb 15;29(4):428-34. doi: 10.1093/bioinformatics/bts716. Epub 2012 Dec 29.

SCARPA: scaffolding reads with practical algorithms.

Author information

1
Department of Computer Science, University of Toronto, Toronto, ON, Canada M5S 3E1. nild@cs.toronto.edu

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.

PMID:
23274213
DOI:
10.1093/bioinformatics/bts716
[Indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Silverchair Information Systems
    Loading ...
    Support Center