Deterministic polynomial-time algorithms for designing short DNA words

Ming-Yang Kao*, Henry C.M. Leung, He Sun, Yong Zhang

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

Original languageEnglish (US)
Pages (from-to)144-160
Number of pages17
JournalTheoretical Computer Science
Volume494
DOIs
StatePublished - Jul 8 2013

Fingerprint

Deterministic Algorithm
Polynomial-time Algorithm
DNA
Polynomials
Randomized Algorithms
Derandomization
Coding Theory
Hamming Distance
Self-assembly
Heuristic Search
Large Set
Local Search
Hamming distance
Multiplicative
Strings
Genetic Algorithm
Self assembly
Genetic algorithms

Keywords

  • DNA word design
  • Derandomization
  • Deterministic algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, Ming-Yang ; Leung, Henry C.M. ; Sun, He ; Zhang, Yong. / Deterministic polynomial-time algorithms for designing short DNA words. In: Theoretical Computer Science. 2013 ; Vol. 494. pp. 144-160.
@article{f0453d165d024f08a3703aa89fc006af,
title = "Deterministic polynomial-time algorithms for designing short DNA words",
abstract = "Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.",
keywords = "DNA word design, Derandomization, Deterministic algorithms",
author = "Ming-Yang Kao and Leung, {Henry C.M.} and He Sun and Yong Zhang",
year = "2013",
month = "7",
day = "8",
doi = "10.1016/j.tcs.2012.12.030",
language = "English (US)",
volume = "494",
pages = "144--160",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Deterministic polynomial-time algorithms for designing short DNA words. / Kao, Ming-Yang; Leung, Henry C.M.; Sun, He; Zhang, Yong.

In: Theoretical Computer Science, Vol. 494, 08.07.2013, p. 144-160.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Deterministic polynomial-time algorithms for designing short DNA words

AU - Kao, Ming-Yang

AU - Leung, Henry C.M.

AU - Sun, He

AU - Zhang, Yong

PY - 2013/7/8

Y1 - 2013/7/8

N2 - Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

AB - Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

KW - DNA word design

KW - Derandomization

KW - Deterministic algorithms

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

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

U2 - 10.1016/j.tcs.2012.12.030

DO - 10.1016/j.tcs.2012.12.030

M3 - Article

AN - SCOPUS:84879080194

VL - 494

SP - 144

EP - 160

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -