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

The rest of this chapter will be organized as follows: Section 14.2 gives some
background information on reconfigurable meshes; Section 14.3 shows how the
two architectures as well as the multiscale architecture can solve the MSA problem
with a fixed amount of data variables; Section 14.4 shows how to solve the
problem with up to O(N) data variables; and the final sections will discuss our
concluding remarks and list our references.

14.2. PRELIMINARIES

For some basic information about reconfigurable meshes and our reasons
for choosing this architecture to implement graph formations of partial-order
multiple-sequence alignments algorithm, please refer to Chapter 7.

14.3. PO-MSAG FORMATION FOR CONSTANT VARIATION

The sequence output in this section is limited to at most a finite (constant) number
of variables. To make the problem more concrete, we focus on DNA sequences,
which have four variables (nucleotides) and possibly a special character, ''*'',
representing a blank space, as our example (Figure 14.2).

14.3.1. Mapping on the Spin-Wave Architecture

I NITIAL M APPING . In our first step, we map the given data sequences (length:
L; number of sequences: N) onto N L processors (we shall address these
processors as nodes) each with its own memory capable of storing any six of
the five possible data variables (in this case, the nucleotides A, T, G, C, and the
blank *) by placing each data variable of all sequences into the first memory slot of
each respective processor. This takes constant time O(1). So, for example, the first
four nodes in rows and columns one and two will be mapped into memory as
follows (Figure 14.3):

A A T G

*

C G T G

*

A T A G

*

C A T C

*

Figure 14.2. Example of a PO-MSA output of DNA.