Deterministic polynomial-time algorithms for designing short DNA words (Q391100)

The paper focuses on deterministic algorithms for designing DNA words, under biologically motivated constraints, in polynomial time. It commences with a comparative study of the effect of constraints on word length and of randomized and deterministic algorithms. This is followed by a detailed description of the constraints and an overview of the approaches for designing words for the basic and the shifting Hamming constraints. Next, a polynomial algorithm based on derandomization techniques is presented in detail. The fourth section introduces deterministic polynomial-time algorithms for subsets of the nine constraints introduced earlier. Throughout the paper, the authors present full proofs of their theorems that support the approaches leading to the proposed polynomial-time algorithms.