Power-Efficient Pipelined Multiprocessor Architecture With Parallel Trace-Back Mechanism for Multiple Pair-Wise Sequence Alignment

Due to the exponential growth of sequence databases, the processing of genome sequencing in real-time is a fundamental problem. Though several schemes have been developed over the years, unfortunately, they suffer from time-consumption, power-consumption, and resource-bound trade-off issues. Another major issue concerns designing efficient architecture to perform the alignment of multiple sequences. A novel hierarchical multiprocessing architecture, designed around pipelined processing elements, is presented for multiple pair-wise sequence alignment at hardware-speed. In addition to parallel intra-sequence trace-back value generation, it can efficiently perform parallel inter-sequence computation to attain maximum utilization of processing elements. It can accomplish parallel trace-back operations to achieve massive parallelism. It consumes O(ni) or O(ji) clock-cycles to perform alignment operations for j-nucleotide query and i reference sequences of n-nucleotide, instead of O((n+j)i) or O(nji) clock-cycles used in state-of-the-art architectures. The entire architecture is evaluated for 16-to-512 multiple sequences of 16-to-512 nucleotides. It achieves ≈1.6 to ≈24 GCUPS (GCUPS: Giga Cell Updates Per Second) throughput and ≈5 to ≈12.5 GCUPS/W power-efficiency for 16-to-64 sequences and ≈1.6 to ≈5.6 GCUPS/W for 128-to-512 sequences. The peak throughput for 1024-nucleotide sequence is 128 GCUPS, and power-efficiency is 41 GCUPS/W. Finally, the presented architecture exhibits a gain of ≈2× in throughput and ≈6× in power-efficiency compared to state-of-the-art architectures.