1 Search Results for "D'Addario, Marianna"

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-dev.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}
}
  • Refine by Author
  • 1 D'Addario, Marianna
  • 1 Kriege, Nils
  • 1 Rahmann, Sven

  • Refine by Classification

  • Refine by Keyword
  • 1 DNA sequence design
  • 1 De Bruijn graph
  • 1 Euler graph
  • 1 Euler tour
  • 1 quotient graph
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact