Abstract: The longest common subsequences can represent the common information of a sequence set,and it has many important applications in many fields,such as computational genomics,information retrieval and so on.Computing longest common subsequences is a famous NP-hard problem with multiple solutions.Some approximate algorithms have a low time complexity,but the result set only has one subsequence.For the sequence set with many longest common subsequences,the information loss is overmuch.In this paper,we presented a new approximate algorithm for this problem.Our algorithm employs a specific mathematical structure called lattice.Firstly,the common lattice of two sequences is computed through dynamic programming and then the common lattice of the current lattice and the current sequence recursively combined with the greedy algorithm are also computed.As the paths in a common lattice contain many common subsequences,the result set contains many longest common subsequences of the original sequence set.And the validity of our algorithm is proved through theory and experiment.

Key words: Longest common subsequences (LCS),Lattice,Approximate algorithm,Greedy algorithm