Computational Biology CB_W0004

Title : Generalized LCS
Author : Amihood Amir, Tzvika Hartman, Oren Kapah, B. Riva Shalom and Dekel Tsur
Year : 2007
Place of publish :
Abstract :

The Longest Common Subsequence (LCS) is a well studied problem, having a wide range of implementations. Its motivation is in comparing strings. It has long been of interest to devise a similar measure for comparing higher dimensional objects, and more complex structures. In this paper we give, what is to our knowledge, the first inherently multi-dimensional definition of LCS. We discuss the Longest Common Substructure of two matrices and the Longest Common Subtree problem for multiple trees including a constrained version. Both problems cannot be solved by a natural extension of the original LCS solution. We investigate the tractability of the above problems. For the first we prove NP -Completeness. For the latter NP -hardness holds for two general unordered trees and for k trees in the constrained LCS.