DNA SEQUENCE MATCHING AT NANOSCALE LEVEL - Bio-Inspired and Nanoscale Integrated Computing - page 385

C. Indexing disabled nodes' right neighbors. Now, we find the row index in the
graph column for each disabled node. We begin by turning on all switches and
having each representative node sent a signal with an amplitude equal to its row
index in the graph column plus two in its own frequency. Since all switches are on,
the transmitted signals will travel in two opposite directions up and down the bus.
Then each disabled node that receives a signal in its own frequency will take the
amplitude of the received signal as its row index in the graph column, sends a
signal with amplitude of 1, and then finally disables its receiver (by changing its
receiving frequency to a dummy frequency), so that the node will not receive any
signals from below. Similar to the previous procedure, this procedure is also done
in constant time. We show how this works using the third column of our example.
The representative nodes A and * send signals of 0+2=2 and 4+2=6,
respectively. Then the first disabled A node that receives the 2 sends a 1 making
the total signal 3. Then last disabled A node that receives the 3 sends a 1 making
the total signal 4. If there were another disabled A node, it would receive that 4. If
there were a disabled * node, it would receive 6. The signals received by the
disabled nodes are their respective row indices in the graph column. The first and
last disabled A nodes will have row indices in the graph column of 2 and 3,
respectively. Since each disabled node has its row index in the graph column now,
it can retrieve its own right neighbor and copy it to the appropriate slot in the
graph column based its row index in constant time.
D. Eliminating repeated right connections. Finally, we eliminate the repeated
right neighbors under each representative node in each graph column. We first
turn off the switch above each representative node and then perform the Node
Elimination procedure under each representative node. This is done in constant
time. Our graph is now formed and store in the graph columns (Figure 14.10).
Table 14.1 lists the time complexities of each stage of the process. The total
time complexity of the process will be O(1).

T

K E C

G

K G

A C B

B

G F

D

A D F

C

S

E H

Figure 14.10. Result of the example sequence.