The design of a universal DNA array
Amir Ben-Dor
,
Department of Computer Science and Engineering, University of Washington
Custom designed DNA arrays offer the possibility of simultaneously
monitoring
thousands of hybridization reactions. These arrays show great potential
for many
medical and scientific applications such as DNA mutation genotyping.
However, the
relatively high manufacturing cost of these custom designed arrays limits
their use.
Recently, an alternative approach was suggested that utilizes fixed,
universal arrays.
These approach present an interesting design problem - the array should
contains as many
DNA tags as possible, while minimizing experimental errors caused by cross
hybridization.
We use a simple thermodynamic model to reduce this design problem to a
formal
mathematical problem: We consider strings over the alphabet {A,C,T,G}. The
{\em
melting temperature} of a string is twice the number of 'A's and 'T's,
plus 4 times the
number of 'C's and 'G's. For example, the melting temperature of 'ACCT' is
12. In
addition, we assign a melting temperature to string pairs - defined to be
the maximal
temperature of a common substring. For example, the melting temperature of
('AATATTATGCG','GCGAATATCC') is 12, because of the common substring 'GCG'.
The combinatorial problem can be now stated as follows: Given two positive
integers l and u, find the largest possible set of strings such that
1. The melting temperature of each string is at least u.
2. The melting temperature of each pair is below l.
employing combinatorial tools, we derive an efficient construction for the
design
problem, and prove that our construction is near optimal.
this is a joint work with Benno Schwikowski, Richard Karp, and Zohar
Yakhini.