D'Addario, Marianna ;
Kriege, Nils ;
Rahmann, Sven
Designing qUnique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs
Abstract
DNA nanoarchitechtures require carefully designed oligonucleotides with certain nonhybridization guarantees, which can be formalized as the quniqueness property on the sequence level. We study the optimization problem of finding a longest qunique 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 qunique sequence is equivalent to finding an Euler tour and solved in linear time with respect to the output string length. For even q, selfcomplementary edges complicate the problem, and the graph has to be Eulerized by deleting a minimum number of edges. Two subcases 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 qUnique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs}},
booktitle = {German Conference on Bioinformatics 2012},
pages = {8292},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897446},
ISSN = {21906807},
year = {2012},
volume = {26},
editor = {Sebastian B{\"o}cker and Franziska Hufsky and Kerstin Scheubert and Jana Schleicher and Stefan Schuster},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3720},
URN = {urn:nbn:de:0030drops37200},
doi = {http://dx.doi.org/10.4230/OASIcs.GCB.2012.82},
annote = {Keywords: DNA sequence design, De Bruijn graph, quotient graph, reverse complement, Euler graph, Euler tour}
}
2012
Keywords: 

DNA sequence design, De Bruijn graph, quotient graph, reverse complement, Euler graph, Euler tour 
Seminar: 

German Conference on Bioinformatics 2012

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 