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. In this paper we give an efficient algorithm to find the LCIS of two sequences in $O({rm min}(r {rm log} ell, n ell +r) {rm log} {rm log} n + Sort(n))$ time where n is the length of each sequence andr is the number of ordered pairs of positions at which the two sequences match, ℓ is the length of the LCIS, and Sort(n) is the time to sort n numbers. For m sequences wherem ≥ 3, we find the LCIS in $O({rm min}(mr^2, r {rm log}ell {rm log}^m r)+mcdot $ Sort(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(nell {rm log} {rm log} n+$ Sort(n)) time. Our algorithm is faster when r is relatively small, e.g., for $r < {rm min}(n^2/({rm log} ell {rm log}{rm log} n), nell/{rm log}ell)$ .