Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-20036-6_40
Title: Opera: Reconstructing optimal genomic scaffolds with high-throughput paired-end sequences
Authors: Gao, S.
Nagarajan, N.
Sung, W.-K. 
Keywords: Fixed-parameter Tractable
Genome Assembly
Graph Algorithms
Scaffolding
Issue Date: 2011
Source: Gao, S.,Nagarajan, N.,Sung, W.-K. (2011). Opera: Reconstructing optimal genomic scaffolds with high-throughput paired-end sequences. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6577 LNBI : 437-451. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-20036-6_40
Abstract: Scaffolding, the problem of ordering and orienting contigs, typically using paired-end reads, is a crucial step in the assembly of high-quality draft genomes. Even as sequencing technologies and mate-pair protocols have improved significantly, scaffolding programs still rely on heuristics, with no gaurantees on the quality of the solution. In this work we explored the feasibility of an exact solution for scaffolding and present a first fixed-parameter tractable solution for assembly (Opera). We also describe a graph contraction procedure that allows the solution to scale to large scaffolding problems and demonstrate this by scaffolding several large real and synthetic datasets. In comparisons with existing scaffolders, Opera simultaneously produced longer and more accurate scaffolds demonstrating the utility of an exact approach. Opera also incorporates an exact quadratic programming formulation to precisely compute gap sizes. © 2011 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/42138
ISBN: 9783642200359
ISSN: 03029743
DOI: 10.1007/978-3-642-20036-6_40
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

11
checked on Jan 16, 2018

Page view(s)

77
checked on Jan 14, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.