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

14
DNA SEQUENCE MATCHING AT
NANOSCALE LEVEL
Mary Mehrnoosh Eshaghian-Wilner, Ling Lau, Shiva Navab,
and David D. Shen
In this chapter, we show how to form partial-order multiple-sequence alignment
graphs on two types of reconfigurable mesh architectures. The first reconfigurable
mesh is a standard microscale one that uses electrical interconnects, while the
second one can be implemented at a nanoscale level and employs spin waves for
interconnectivity. We consider graph formations for two cases. In one case, the
number of distinct variables in the data sequences is constant. In the other case, it
can be as much as O(N ). We show that given O(N ) aligned sequences of length L,
we can combine the sequences to form a graph in O(1) time, using either
architecture if there is a constant number of distinct variables in the sequence.
Otherwise, it will take O(1) time if we use the spin-wave model and O(N) time if we
use the standard VLSI version.
14.1. INTRODUCTION
Research in molecular biology has been moving at an astonishing pace in recent
years. The rapid accumulation of biological data has necessitated more robust
databases and data processing algorithms. Consequently, new areas of computa-
tional biology are being created rapidly, combining the biological and informa-
tional sciences. To illustrate the complexities of some of the problems in
computational biology, let us consider the genetic material in all living organisms,
DNA. DNA is a polymer of nucleotides, where each nucleotide contains one of
four bases: A, G, T, or C. An average gene in a human genome has 30,000
The authors of this chapter are listed alphabetically.