title: Graph formations of partial-order multiple-sequence alignments using nanoscale, microscale, and multiscale reconfigurable meshes.
abstract: In this paper, 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 that uses electrical interconnects, while the second type of reconfigurable mesh 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 very large scale integration version.
authors.affiliation: Electrical Engineering Department, University of California, Los Angeles, CA 90095, USA. maryew@ee.ucla.edu
authors.forename: Mary Mehrnoosh
authors.initials: MM
authors.lastname: Eshaghian-Wilner
authors.forename: Ling Jonathan
authors.initials: LJ
authors.lastname: Lau
authors.forename: Shiva
authors.initials: S
authors.lastname: Navab
authors.forename: David
authors.initials: D
authors.lastname: Shen
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000235:genetics*; D008969:Molecular Sequence Data; D036103:Nanotechnology / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D004247:DNA