Scoring-and-unfolding trimmed tree assembler: concepts, constructs and comparisons
Open Access
- 18 November 2010
- journal article
- research article
- Published byĀ Oxford University Press (OUP)Ā inĀ Bioinformatics
- Vol.Ā 27 Ā (2) , 153-160
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Why greed works for shortest common superstring problemTheoretical Computer Science, 2009
- Genome assembly forensics: finding the elusive mis-assemblyGenome Biology, 2008
- De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computerGenome Research, 2008
- Short read fragment assembly of bacterial genomesGenome Research, 2007
- TSP Cuts Which Do Not Conform to the Template Paradigm2001
- Assembly of the Working Draft of the Human Genome with GigAssemblerGenome Research, 2001
- Combinatorial algorithms for DNA sequence assemblyAlgorithmica, 1995
- Toward Simplifying and Accurately Formulating Fragment AssemblyJournal of Computational Biology, 1995
- A machine program for theorem-provingCommunications of the ACM, 1962
- An Automatic Method of Solving Discrete Programming ProblemsEconometrica, 1960