Deterministic polynomial-time algorithms for designing short DNA words

DOI10.1007/978-3-642-13562-0_28MaRDI QIDQ3569085zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• scientific article; zbMATH DE number 1568800 (Why is no real title available?)
• 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)