Fig. 1. Two schematic views of separating round-trip itineraries. LEFT: Itinaraties encoded as circular DNA moleculew in testubes. RIGHT: Corresponding DNA chip readout.
Joint Penn-UDel Colloquium on the Nature of Computing
DNA Chip Readout for DNA Computing
David Harlan Wood
Fig. 1. Two schematic views of separating round-trip itineraries.
LEFT:
Itinaraties encoded as circular DNA moleculew in testubes.
RIGHT:
Corresponding DNA chip readout.
(General Interest: First 25 minutes)
We wish to read out round-trip itineraries when they are encoded in circular molecules of DNA. See the upper left part of Fig 1. Each such itinerary consists of some particular circular ordering of A, B, C, D, E, F, and G. DNA chips (right part of Fig 1) are designed so that any round-trip itinerary DNA molecule will light up 7 spots. One spot is lit in each row (each city has exactly one departure); such that there is one spot lit in each column (each city has exactly one arrival).
We will show how, with the guidance of the chips on the right, the circular DNA molecules are progressively separated. For example, the ultimate chip readouts on the bottom disclose one circular itinerary (A->B->C->D->E->F->G->A). and one error (an itinerary that omits city D).
(Break: Second 10 minutes)
(Researcher's Interest: Last 25 minutes)
A more general problem is to use DNA chips to read out variable length DNA strings. These strings might contain any number of, say, As, Bs, Cs, Ds, Es, Fs, and Gs in any order. Approaches to this problem will be presented.
1. David Harlan Wood, "A DNA computing algorithm for directed Hamiltonian paths." In Genetic Programming 1998, Morgan Kaufman, San Francisco, 731-734, 1988.2. Bertrand Lemieux, A. Aharoni and M. Schena, "Overview of DNA chip technology." Molecular Breeding 4: 277-289, 1988.