Computer Science – Data Structures and Algorithms
Scientific paper
2006-01-19
Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), Lisboa, Portugal, July 1
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Kao Ming-Yang
Sanghi Manan
Schweller Robert
No associations
LandOfFree
Randomized Fast Design of Short DNA Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Randomized Fast Design of Short DNA Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Fast Design of Short DNA Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-449322