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

TABLE 14 . 4 . Summarized Time Analysis of Standard and Multiscale Architectures
Arbitrary variation Constant variation

STANDARD VLSI O(AN) O(1)

Spin Wave O(1) O(1)

MULTISCALE VLSI max[O(N),O(L)] max[O(N),O(L)]

Spin Wave max[O(N),O(L)] max[O(N),O(L)]

to AN BL, a costly operation. Also, there can be an advantage in the case where
we use the VLSI reconfigurable for arbitrary variation. With an AN BL dataset,
we would expect the run-time to be O(AN) for this case. However, in the multiscale
architecture, this same case (VLSI with up to O(AN) variation) will still run at
max[O(N),O(L)].SoaslongaswemakeA W 1 (when N W L)orA W L/N (when

L W N), we will have gained a run-time advantage (Table 14.4).

14.5. CONCLUSIONS

This chapter, demonstrated several techniques for forming graphs representing
partial-order multiple-sequence alignment of a given set of N-aligned sequences,
using two types of reconfigurable mesh architectures (the spin-wave version [10] and
the VLSI version [11, 12]). It showed that for a constant number of variables, the
run-times of both architectures are the same, O(1). However for an arbitrary
number of variables, the spin-wave architecture will have an O(1) time complexity
as opposed to an O(N) time complexity using the other version. The algorithms
described in this chapter belong to one of the first sets of algorithms currently under
study in the area of bioinformatics. These results can be extended to large-scale
graph databases. Furthermore, other applications will also benefit from such
graphical representation of data, such as those in the areas of biological pathways
and sequence splicing. Such areas will continue to demand even more efficient
computing tools. The scale of our solution can be expanded by using clusters of
mainframes to aid in the sequence data processing. Mapping tools such as Cluster-
M, introduced in [13], can be used to handle the mapping and scheduling of graph
data bases. All of these will serve as preliminary steps towards coming up with
paradigms that could satisfy the computational needs of bioinformatics tasks.

REFERENCES

1. M. M. Eshaghian-Wilner. Integrated architectural solutions for protein sequence-
structure alignment. In: Proceedings of the Sixth World Multi-Conference on Sys-
temics, Cybernetics, and Informatics, SCI2002, July 2002.