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

A

*

1 23456 1 23456

C

G

1 23456 1 23456

Figure 14.3. Example of the memory space of the nodes.

N EIGHBOR R ECORDING . Next, we let each node store its right neighbor in its
second memory slot. This step still takes constant time since retrieving the
information is O(1) and also since all nodes are performing this task simulta-
neously on parallel processors. So once again, the first four nodes in rows and
columns one and two will be mapped into memory as shown here (Figure 14.4):

N ODE E LIMINATION . Now comes the grouping of the similar nodes in each
column.

A. We start by turning off (disconnect the channel) all the switches above
each node to force the signal sent by each node downwards.
B. Then we let all nodes simultaneously send out a signal downward in its
own frequency and turn on all switches (reconnecting the channel),
thereby lettings all signals pass through the bus. Then the nodes that
receive a signal in their own frequencies will be repeated nodes. We
disabled these nodes.

One node (the first or uppermost) of each type in that column that did not
receive a signal remains active and represents the rest of its type. To better
understand this procedure, we can take a look at the third column of our example.
Each of the A nodes will first send out a signal downward in Frequency A. Then,
there will be one—the first or uppermost—A node left that has not received any
signals in Frequency A. The rest of the A's will be obsolete, since the rest will now
be represented by that first A node. So for example, just for the A nucleotide in the
third column, this process will be as follows (Figure 14.5):

A

A

*

*

1 23456 1 23456

C G

G

*

1 23456 1 23456

Figure 14.4. Memory spaces of the nodes after the set-up stage.