General Information
| Description | Concepts, constructs and comparisons |
| Homepage | http://www.bioinformatics.nyu.edu |
Publications
Scoring-and-unfolding trimmed tree assembler: concepts, constructs and comparisons
Motivation:
Mired by its connection to a well-known 𝒩𝒫-complete combinatorial optimization problem—namely, the Shortest Common Superstring Problem (SCSP)—historically, the whole-genome sequence assembly (WGSA) problem has been assumed to be amenable only to greedy and heuristic methods. By placing efficiency as their first priority, these methods opted to rely only on local searches, and are thus inherently approximate, ambiguous or error prone, especially, for genomes with complex structures. Furthermore, since choice of the best heuristics depended critically on the properties of (e.g. errors in) the input data and the available long range information, these approaches hindered designing an error free WGSA pipeline.
Results:
We dispense with the idea of limiting the solutions to just the approximated ones, and instead favor an approach that could potentially lead to an exhaustive (exponential-time) search of all possible layouts. Its computational complexity thus must be tamed through a constrained search (Branch-and-Bound) and quick identification and pruning of implausible overlays. For his purpose, such a method necessarily relies on a set of score functions (oracles) that can combine different structural properties (e.g. transitivity, coverage, physical maps, etc.). We give a detailed description of this novel assembly framework, referred to as Scoring-and-Unfolding Trimmed Tree Assembler (SUTTA), and present experimental results on several bacterial genomes using next-generation sequencing technology data. We also report experimental evidence that the assembly quality strongly depends on the choice of the minimum overlap parameter k.
Availability and Implementation:
SUTTA's binaries are freely available to non-profit institutions for research and educational purposes at http://www.bioinformatics.nyu.edu.
Contact:
narzisi@nyu.edu
Supplementary information:
Supplementary data are available at Bioinformatics online.
Related Tools
BLESS
Published January 2014
Bloom filter-based error correction solution for high-throughput sequencing reads
When less is more
Published May 2015
‘slicing’ sequencing data improves read decoding accuracy and de novo assembly quality
ScaffoldScaffolder
Published September 2015
Solving contig orientation via bidirected to directed graph reduction
LightAssembler
Published July 2016
Fast and memory-efficient assembly algorithm for high-throughput sequencing reads
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
