Combinatorial problems of universal DNA tag sets

Abstract

A universal DNA tag system is a set of short single-stranded pieces of DNA(oligonucleotides) where each oligonucleotide has a much greater tendency to hybridize with its own Watson-Crick complement than the complement of the other oligonucleotides in the set. The oligonucleotides are referred to as tags and their Watson-Crick complements are referred to as antitags. It has a variety of uses especially labeling distinct chemicals. We implement an algorithm to design these oligonucleotides, apply the algorithm to generate a DNA tag system of other ratios of ω(C or G) / ω(A or T), and to find the largest string that uses each token at most once for a given collection of c-tokens.