Your browser has javascript turned off or blocked. This will lead to some parts of our website to not work properly or at all. Turn on javascript for best performance.

The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Face of Tobias Ambjörnsson. Photo.

Tobias Ambjörnsson

Senior lecturer

Face of Tobias Ambjörnsson. Photo.

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

Author

  • Albertas Dvirnas
  • Christoffer Pichler
  • Callum L. Stewart
  • Saair Quaderi
  • Lena K. Nyberg
  • Vilhelm Müller
  • Santosh Kumar Bikkarolla
  • Erik Kristiansson
  • Linus Sandegren
  • Fredrik Westerlund
  • Tobias Ambjörnsson

Summary, in English

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.

Department/s

  • Department of Astronomy and Theoretical Physics

Publishing year

2018-03-01

Language

English

Publication/Series

PLoS ONE

Volume

13

Issue

3

Document type

Journal article

Publisher

Public Library of Science

Topic

  • Genetics
  • Biophysics

Status

Published

ISBN/ISSN/Other

  • ISSN: 1932-6203