Deterministic polynomial-time algorithms for designing short DNA words

DOI10.1007/978-3-642-13562-0_28zbMATH Open1284.92074arXiv1201.6358OpenAlexW2108251045MaRDI QIDQ3569085FDOQ3569085

Authors: Henry Leung, He Sun, Yong Zhang, Ming-Yang Kao 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 (2009) 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{log n, 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.1 log n + 6.28 k) and 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.

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

Recommendations

• Deterministic polynomial-time algorithms for designing short DNA words
• On codeword design in metric DNA spaces
• Randomized fast design of short DNA words
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1568800

zbMATH Keywords

derandomizationcoding theoryRamanujan graphsexpander codesDNA computatingDNA words design

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32) Other types of codes (94B60)

Cited In (8)

• Deterministic polynomial-time algorithms for designing short DNA words
• Flexible Word Design and Graph Labeling
• A method for constructing artificial DNA libraries based on generalized de Bruijn sequences
• Algorithms for testing that sets of DNA words concatenate without secondary structure
• Title not available (Why is that?)
• Automata, Languages and Programming
• Randomized fast design of short DNA words
• Computational and Information Science

This page was built for publication: Deterministic polynomial-time algorithms for designing short DNA words

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