Randomized fast design of short DNA words

Ming-Yang Kao*, Manan Sanghi, Robert Schweller

*Corresponding author for this work

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

Original languageEnglish (US)
Article number43
JournalACM Transactions on Algorithms
Volume5
Issue number4
DOIs
StatePublished - Oct 1 2009

Fingerprint

Strings
DNA Computing
Coding Theory
Local Search Algorithm
Self-assembly
Heuristic Search
Randomized Algorithms
Polynomial time
Design
Genetic Algorithm
Optimization Problem
Optimization
Formulation
Output

Keywords

  • DNA code design
  • Randomized algorithms

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Cite this

Kao, Ming-Yang ; Sanghi, Manan ; Schweller, Robert. / Randomized fast design of short DNA words. In: ACM Transactions on Algorithms. 2009 ; Vol. 5, No. 4.
@article{f9ce9a13d76c4f4d9e6712c4364a6267,
title = "Randomized fast design of short DNA words",
abstract = "We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.",
keywords = "DNA code design, Randomized algorithms",
author = "Ming-Yang Kao and Manan Sanghi and Robert Schweller",
year = "2009",
month = "10",
day = "1",
doi = "10.1145/1597036.1597047",
language = "English (US)",
volume = "5",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

Randomized fast design of short DNA words. / Kao, Ming-Yang; Sanghi, Manan; Schweller, Robert.

In: ACM Transactions on Algorithms, Vol. 5, No. 4, 43, 01.10.2009.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Randomized fast design of short DNA words

AU - Kao, Ming-Yang

AU - Sanghi, Manan

AU - Schweller, Robert

PY - 2009/10/1

Y1 - 2009/10/1

N2 - We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

AB - We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

KW - DNA code design

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=76649131608&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=76649131608&partnerID=8YFLogxK

U2 - 10.1145/1597036.1597047

DO - 10.1145/1597036.1597047

M3 - Article

AN - SCOPUS:76649131608

VL - 5

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 4

M1 - 43

ER -