Efficient Algorithms for Finding a Longest Common Increasing Subsequence

摘要

We study the problem of finding a longest common increasing subsequence (LCIS) of multiple sequences of numbers. The LCIS problem is a fundamental issue in various application areas, including the whole genome alignment and pattern recognition. In this paper we give an efficient algorithm to find the LCIS of two sequences in O(min(r log l, nl + r) log log n + n log n) time where n is the length of each sequence and r is the total number of ordered pairs of positions at which the two sequences match and l is the length of the LCIS. For m sequences where m ≥ 3, we find the LCIS in O(min(mr~2, mr log l log~m r) + mn log n) time where r is the total number of m-tuples of positions at which the m sequences match. The previous results find the LCIS of two sequences in O(n~2) and O(nl log n) time. Our algorithm is faster when r is relatively small, e.g., for r < min(n~2/log log n,nl).