Skip to Main Content

 The ABC of DNA Computing


4. Encoding vertices and edges with DNA strands.

Adleman assigned to each vertex, and to each link, a single DNA strand 20 bases long. For example

Vertex 3    GCTATTCGAGCTTAAAGCTA                        
Link 2->3   GTATATCCGAGCTATTCGAG    Note that Link 2->3 is made of the last                                    
                                     half of 2 plus the first half of 3. 

(In fact, the Start and Finish vertices are treated slightly differently from the others, but this detail can safely be ignored in our schematic view of the procedure.) The length was chosen for technical reasons; in our illustration we will use 8-base strands, following Hapgood's schematization of the procedure; we will also continue with his airport-and-flight realization of the problem.

  • In the strand for each airport the first four bases represent the arrival area and the last four represent the departure area.
  • A flight from Dallas to Chicago links the Dallas departure area to the Chicago arrival area: the strand representing Dallas->Chicago is analogously made up of the Dallas departure code followed by the Chicago arrival code.
  • Note that Chicago->Dallas is a completely different strand.
Atlanta A    Atl->Dal A  
Dallas  A    Atl->Chi A  
Chicago     Dal->Chi A             
         etc.                Chi->Dal A