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: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Designing short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these 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)
Title of host publicationTheory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings
Pages308-319
Number of pages12
DOIs
StatePublished - Jul 15 2010
Event7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 - Prague, Czech Republic
Duration: Jun 7 2010Jun 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6108 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010
CountryCzech Republic
CityPrague
Period6/7/106/11/10

Fingerprint

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

Keywords

  • DNA computating
  • DNA words design
  • Ramanujan graphs
  • coding theory
  • derandomization
  • expander codes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M-Y., Leung, H. C. M., Sun, H., & Zhang, Y. (2010). Deterministic polynomial-time algorithms for designing short DNA words. In Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings (pp. 308-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6108 LNCS). https://doi.org/10.1007/978-3-642-13562-0_28
Kao, Ming-Yang ; Leung, Henry C.M. ; Sun, He ; Zhang, Yong. / Deterministic polynomial-time algorithms for designing short DNA words. Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings. 2010. pp. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{79a2c2982b5a4af7a6c6ece44a6cc24b,
title = "Deterministic polynomial-time algorithms for designing short DNA words",
abstract = "Designing short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.",
keywords = "DNA computating, DNA words design, Ramanujan graphs, coding theory, derandomization, expander codes",
author = "Ming-Yang Kao and Leung, {Henry C.M.} and He Sun and Yong Zhang",
year = "2010",
month = "7",
day = "15",
doi = "10.1007/978-3-642-13562-0_28",
language = "English (US)",
isbn = "3642135617",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "308--319",
booktitle = "Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings",

}

Kao, M-Y, Leung, HCM, Sun, H & Zhang, Y 2010, Deterministic polynomial-time algorithms for designing short DNA words. in Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6108 LNCS, pp. 308-319, 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010, Prague, Czech Republic, 6/7/10. https://doi.org/10.1007/978-3-642-13562-0_28

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

Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings. 2010. p. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6108 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

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 - 2010/7/15

Y1 - 2010/7/15

N2 - Designing short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these 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 n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

KW - DNA computating

KW - DNA words design

KW - Ramanujan graphs

KW - coding theory

KW - derandomization

KW - expander codes

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

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

U2 - 10.1007/978-3-642-13562-0_28

DO - 10.1007/978-3-642-13562-0_28

M3 - Conference contribution

AN - SCOPUS:77954437447

SN - 3642135617

SN - 9783642135613

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 308

EP - 319

BT - Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings

ER -

Kao M-Y, Leung HCM, Sun H, Zhang Y. Deterministic polynomial-time algorithms for designing short DNA words. In Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings. 2010. p. 308-319. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-13562-0_28