Advanced

Facilitated sequence assembly using densely labeled optical DNA barcodes : A combinatorial auction approach

Dvirnas, Albertas LU ; Pichler, Christoffer LU ; Stewart, Callum L.; Quaderi, Saair; Nyberg, Lena K.; Müller, Vilhelm; Bikkarolla, Santosh Kumar; Kristiansson, Erik; Sandegren, Linus and Westerlund, Fredrik, et al. (2018) In PLoS ONE 13(3).
Abstract

The output from whole genome sequencing is a set of contigs, i.e. short non-overlapping DNA sequences (sizes 1-100 kilobasepairs). Piecing the contigs together is an especially difficult task for previously unsequenced DNA, and may not be feasible due to factors such as the lack of sufficient coverage or larger repetitive regions which generate gaps in the final sequence. Here we propose a new method for scaffolding such contigs. The proposed method uses densely labeled optical DNA barcodes from competitive binding experiments as scaffolds. On these scaffolds we position theoretical barcodes which are calculated from the contig sequences. This allows us to construct longer DNA sequences from the contig sequences. This proof-of-principle... (More)

The output from whole genome sequencing is a set of contigs, i.e. short non-overlapping DNA sequences (sizes 1-100 kilobasepairs). Piecing the contigs together is an especially difficult task for previously unsequenced DNA, and may not be feasible due to factors such as the lack of sufficient coverage or larger repetitive regions which generate gaps in the final sequence. Here we propose a new method for scaffolding such contigs. The proposed method uses densely labeled optical DNA barcodes from competitive binding experiments as scaffolds. On these scaffolds we position theoretical barcodes which are calculated from the contig sequences. This allows us to construct longer DNA sequences from the contig sequences. This proof-of-principle study extends previous studies which use sparsely labeled DNA barcodes for scaffolding purposes. Our method applies a probabilistic approach that allows us to discard “foreign” contigs from mixed samples with contigs from different types of DNA. We satisfy the contig non-overlap constraint by formulating the contig placement challenge as a combinatorial auction problem. Our exact algorithm for solving this problem reduces computational costs compared to previous methods in the combinatorial auction field. We demonstrate the usefulness of the proposed scaffolding method both for synthetic contigs and for contigs obtained using Illumina sequencing for a mixed sample with plasmid and chromosomal DNA.

(Less)
Please use this url to cite or link to this publication:
author
, et al. (More)
(Less)
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
PLoS ONE
volume
13
issue
3
publisher
Public Library of Science
external identifiers
  • scopus:85043765928
ISSN
1932-6203
DOI
10.1371/journal.pone.0193900
language
English
LU publication?
yes
id
26f7890f-3e6b-470c-abcc-a3c6c942caae
date added to LUP
2018-03-27 14:03:53
date last changed
2019-07-16 03:46:30
@article{26f7890f-3e6b-470c-abcc-a3c6c942caae,
  abstract     = {<p>The output from whole genome sequencing is a set of contigs, i.e. short non-overlapping DNA sequences (sizes 1-100 kilobasepairs). Piecing the contigs together is an especially difficult task for previously unsequenced DNA, and may not be feasible due to factors such as the lack of sufficient coverage or larger repetitive regions which generate gaps in the final sequence. Here we propose a new method for scaffolding such contigs. The proposed method uses densely labeled optical DNA barcodes from competitive binding experiments as scaffolds. On these scaffolds we position theoretical barcodes which are calculated from the contig sequences. This allows us to construct longer DNA sequences from the contig sequences. This proof-of-principle study extends previous studies which use sparsely labeled DNA barcodes for scaffolding purposes. Our method applies a probabilistic approach that allows us to discard “foreign” contigs from mixed samples with contigs from different types of DNA. We satisfy the contig non-overlap constraint by formulating the contig placement challenge as a combinatorial auction problem. Our exact algorithm for solving this problem reduces computational costs compared to previous methods in the combinatorial auction field. We demonstrate the usefulness of the proposed scaffolding method both for synthetic contigs and for contigs obtained using Illumina sequencing for a mixed sample with plasmid and chromosomal DNA.</p>},
  articleno    = {e0193900},
  author       = {Dvirnas, Albertas and Pichler, Christoffer and Stewart, Callum L. and Quaderi, Saair and Nyberg, Lena K. and Müller, Vilhelm and Bikkarolla, Santosh Kumar and Kristiansson, Erik and Sandegren, Linus and Westerlund, Fredrik and Ambjörnsson, Tobias},
  issn         = {1932-6203},
  language     = {eng},
  month        = {03},
  number       = {3},
  publisher    = {Public Library of Science},
  series       = {PLoS ONE},
  title        = {Facilitated sequence assembly using densely labeled optical DNA barcodes : A combinatorial auction approach},
  url          = {http://dx.doi.org/10.1371/journal.pone.0193900},
  volume       = {13},
  year         = {2018},
}