# DNA Computing: Concepts for Medical Applications
## 3 New Concept of Designing Diagnostic Biochips
At the molecular level, the mechanism of action of the diagnostic biochips consists of a sequential (alternate) reading of characteristic genetic features by the programmable biomolecular nanodevices built of a double-stranded DNA and the restriction enzymes. The devices complete their action as soon as they detect the presence of the desired DNA fragments and output signal, e.g., by means of fluorescence. It is worth noting that the so-designed diagnostic biochips can be manufactured commercially as laboratory kits or diagnostic devices. One of the requirements for the correct and accurate designing of biochips based on biomolecular computers is to develop theoretical fundamentals of the implementation of practical biomolecular computers. In the case of diagnostic biochips, we propose the use of a formal system called queue automata [29] which have a memory that works according to the first in, first out (FIFO) principle--queue memory [30] (Figure 3). The queue automata consist of a head (finite control), a type with cells containing an input word created from symbols of a certain finite alphabet and a queue (Figure 3). A finite control reading of the symbols of the input word runs one after another and changes its state according to the transition rules followed. At every step of the queue automaton operation, the first symbol in the queue may be removed or retained, and another symbol may be added at the end of the queue. The transition depends on the current state of the queue automaton and on the symbol read out from the input word. A variant of queue automata is the deterministic input-driven queue automata [31]. In these automata, \"input-driven\" means that the automata are controlled by the input, i.e., that the input word controls the queue. The deterministic input-driven queue automata are a formal system \(M=(Q,\Sigma,\Gamma,q_{0},F,\bot,\delta_{\ell},\delta_{\tau},\delta_{i})\), where \(Q\) is the finite set of internal states; \(\Sigma\) is the finite set of input symbols consisting of the disjoint union of sets \(\Sigma_{e},\ \ \Sigma_{\tau},\ \Sigma_{i}\); \(\Gamma\) is the finite set of queue symbols; \(q_{0}\in Q\) is the initial state; \(F\subseteq Q\) is the set of accepting states; \(\bot\
ot\in\Gamma\) is the empty queue symbol; \(\delta_{e}\) is the partial transition function mapping \(Q\times\ \Sigma_{e}\times(\Gamma\cup\{\bot\})\) to \(Q\times\Gamma\); \(\delta_{\tau}\) is the partial transition function mapping \(Q\times\ \Sigma_{\tau}\times(\Gamma\cup\{\bot\})\) to \(Q\); and \(\delta_{i}\) is the partial transition function mapping \(Q\times\ \Sigma_{i}\times(\Gamma\cup\{\bot\})\) to \(Q\). The choice of that theoretical model (exactly queue automata) was dictated by the possibility of task scheduling with the use of queue automata, which is required for the controlled genome reading at the molecular level with the use of type IIB restriction  
Figure 3: Schematic diagram of the queue memory operation (FIFO principle). A new element added to the queue is placed at the end of the queue, and the first element is removed from the front of the queue. The operation of adding a new element to the queue is called ENQUEUE, while the operation of removing an element from the queue is called DEQUEUE. Abbreviations: 1, 2, 3, 4, 5 denote the positions of the elements that are in the queue. endonucleases. The biomolecular implementation of the queue automata (biomolecular queue automata) requires specific encoding of the respective components of the queue automata (Figure 4). We propose that the symbols in the queue automaton should be separated by spacers, that is, the DNA fragments which do not encode the input symbols of a biomolecular computer--similarly to a computing machine made of biomolecules and presented by [PERSON]'s group in 2003 [4]. In addition, our proposal is that the spacers between the symbols should be of different length as this provides an opportunity to perceive a genome as a system of different symbols separated by spacers (Figure 5A).