Randomized fast design of short DNA words

DOI10.1145/1597036.1597047MaRDI QIDQ2930269zbMATH OpenOpenAlexFDO

Authors Manan Sanghi, Robert T. Schweller, Ming-Yang Kao

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0601084

Combinatorics on words (68R15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Protein sequences, DNA sequences (92D20)

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 computing and DNA self-assembly. 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 paper 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 high-probability 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. 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.

Recommendations

Cited in

(12)

This page was built for publication: Randomized fast design of short DNA words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930269)