Title :
Determining longest common subsequences of two sequences on a linear array of processors
Author_Institution :
Dept. of Comput. Sci., Univ. of Central Florida, Orlando, FL, USA
Abstract :
This paper presents special-purpose linear array processor architecture for determining longest common subsequences (LCS) of two sequences. The algorithm uses systolic and pipelined architectures suitable for VLSI implementation. The algorithms are also suitable for implementation on parallel machines. The author first develops a `greedy´ algorithm to determine some of the LCS and then proposes a generalization to determine all LCS of the given pair of sequences. Earlier hardware algorithms were concerned with determining only the length of LCS or the edit distance of two sequences
Keywords :
VLSI; systolic arrays; VLSI implementation; greedy algorithm; linear array of processors; longest common subsequences; pipelined architectures; systolic architecture; Algorithm design and analysis; Biology computing; Computer architecture; Computer science; DNA; Genetics; Hardware; Parallel machines; Sequences; Very large scale integration;
Conference_Titel :
Application Specific Array Processors, 1992. Proceedings of the International Conference on
Conference_Location :
Berkeley, CA
Print_ISBN :
0-8186-2967-3
DOI :
10.1109/ASAP.1992.218547