Title

Determining Longest Common Subsequences Of Two Sequences On A Linear Array Of Processors

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 architecture suitable for VLSI implementation. The algorithms are also suitable for implementation on parallel machines. We first develop a `greedy' algorithm to determine some of the LCS and then propose a generalization to determine all LCS of the given pair of sequences. Earlier hardware algorithms [Lipton and Lopresti, 85; Mukherjee, 89] were concerned with determining only the length of LCS or the edit distance of two sequences.

Publication Date

12-1-1992

Publication Title

Proceedings of the International Conference on Application

Number of Pages

526-537

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

Socpus ID

0026961395 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026961395

This document is currently not available here.

Share

COinS