Algorithms for Testing That Sets of DNA Words Concatenate without Secondary Structure

摘要

We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S*, for some finite set S of equi-length words, are structure-free.