### 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 language | English (US) |
---|---|

Title of host publication | Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings |

Publisher | Springer Verlag |

Pages | 308-319 |

Number of pages | 12 |

ISBN (Print) | 3642135617, 9783642135613 |

DOIs | |

State | Published - Jan 1 2010 |

Event | 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 - Prague, Czech Republic Duration: Jun 7 2010 → Jun 11 2010 |

### Publication series

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

Volume | 6108 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 6/7/10 → 6/11/10 |

### Fingerprint

### 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

*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). Springer Verlag. https://doi.org/10.1007/978-3-642-13562-0_28