A reconfigurable embedded system for sequence alignment problem

Sequence alignment is a basic and important tool for the research of biological information. It can compare and analyze the degree of similarity between two or more sequences to speculate whether they are derived from the common ancestor or not. Usually, lengths of both input sequences are fairly long, resulting in long processing time. Many previous algorithms have been proposed to reduce the processing time. Previous systolic algorithms can achieve linear time complexity with linear number of processing elements. However, each processing element needs linear memory-space to store intermediate results and then the system needs too large memory-space in total, resulting in being not suitable for being implemented on VLSI. Hence, to design an efficient and hardware-implementable algorithm is an important issue. This paper proposes a reconfigurable systolic architecture for the sequence alignment problem. At first, we use Needleman-Wunsch recursive function to derive the rules of forward and backward processes. By employing “divide and conquer” technique, we can find a sequence alignment with the best score. It needs a little more time complexity with only linear memory-space in total. Furthermore, the number of physical processing elements can be fixed by employing the concept of virtual processing elements. Therefore, our proposed reconfigurable systolic architecture is not only hardware-implementable on VLSI but also efficient.