License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.GCB.2012.82
URN: urn:nbn:de:0030-drops-37200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3720/
Go to the corresponding OASIcs Volume Portal

D'Addario, Marianna ; Kriege, Nils ; Rahmann, Sven

Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs

pdf-format:
9.pdf (0.6 MB)

Abstract

DNA nanoarchitechtures require carefully designed oligonucleotides with certain non-hybridization guarantees, which can be formalized as the q-uniqueness property on the sequence level. We study the optimization problem of finding a longest q-unique DNA sequence. We first present a convenient formulation as an integer linear program on the underlying De Bruijn graph that allows to flexibly incorporate a variety of constraints; solution times for practically relevant values of q are short. We then provide additional insights into the problem structure using the quotient graph of the De Bruijn graph with respect to the equivalence relation induced by reverse complementarity. Specifically, for odd q the quotient graph is Eulerian, so finding a longest q-unique sequence is equivalent to finding an Euler tour and solved in linear time with respect to the output string length. For even q, self-complementary edges complicate the problem, and the graph has to be Eulerized by deleting a minimum number of edges. Two sub-cases arise, for one of which we present a complete solution, while the other one remains open.

BibTeX - Entry

@InProceedings{daddario_et_al:OASIcs:2012:3720,
  author =	{Marianna D'Addario and Nils Kriege and Sven Rahmann},
  title =	{{Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs}},
  booktitle =	{German Conference on Bioinformatics 2012},
  pages =	{82--92},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-44-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{26},
  editor =	{Sebastian B{\"o}cker and Franziska Hufsky and Kerstin Scheubert and Jana Schleicher and Stefan Schuster},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3720},
  URN =		{urn:nbn:de:0030-drops-37200},
  doi =		{10.4230/OASIcs.GCB.2012.82},
  annote =	{Keywords: DNA sequence design, De Bruijn graph, quotient graph, reverse complement, Euler graph, Euler tour}
}

Keywords: DNA sequence design, De Bruijn graph, quotient graph, reverse complement, Euler graph, Euler tour
Collection: German Conference on Bioinformatics 2012
Issue Date: 2012
Date of publication: 13.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI