DROPS

Document

DOI: 10.4230/OASIcs.GCB.2012.82

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

Authors: Marianna D'Addario, Nils Kriege, and Sven Rahmann

Published in: OASIcs, Volume 26, German Conference on Bioinformatics 2012

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.

Cite as

Marianna D'Addario, Nils Kriege, and Sven Rahmann. Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs. In German Conference on Bioinformatics 2012. Open Access Series in Informatics (OASIcs), Volume 26, pp. 82-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{daddario_et_al:OASIcs.GCB.2012.82,
  author =	{D'Addario, Marianna and Kriege, Nils and Rahmann, Sven},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-44-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{26},
  editor =	{B\"{o}cker, Sebastian and Hufsky, Franziska and Scheubert, Kerstin and Schleicher, Jana and Schuster, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2012.82},
  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}
}

Search Results

Documents authored by D'Addario, Marianna

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

Abstract

Cite as

Thanks for your feedback!

Could not send message