  In this paper we propose new solution methods for designing tag sets for use
in universal DNA arrays. First, we give integer linear programming formulations
for two previous formalizations of the tag set design problem, and show that
these formulations can be solved to optimality for instance sizes of practical
interest by using general purpose optimization packages. Second, we note the
benefits of periodic tags, and establish an interesting connection between the
tag design problem and the problem of packing the maximum number of
vertex-disjoint directed cycles in a given graph. We show that combining a
simple greedy cycle packing algorithm with a previously proposed alphabetic
tree search strategy yields an increase of over 40% in the number of tags
compared to previous methods.
