Graph Formations of Partial-Order Multiple-Sequence Alignments Using Nanoscale, Microscale, and Multiscale Reconfigurable Meshes

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.