Efficient algorithms for finding a longest common increasing subsequence

Wun-Tat Chan, Yong Zhang, Stanley P. Y. Fung, Deshi Ye, Hong Zhu

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

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(min(r log l, n l + r) log log n + Sort(n)) time where n is the length of each sequence and r is the number of ordered pairs of positions at which the two sequences match, l is the length of the LCIS, and Sort(n) is the time to sort n numbers. Form sequences wherem >= 3, we find the LCIS in O(min(m r^2, r log l log^m r ) + m 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(n l log log n + Sort(n)) time. Our algorithm is faster when r is relatively small, e.g., for r <min(n^2 / (log l log log n), n l / log l).
Original languageEnglish
Pages (from-to)277 - 288
Number of pages12
JournalJOURNAL OF COMBINATORIAL OPTIMIZATION
Volume13
Issue number3
DOIs
Publication statusPublished - Apr 2007

Fingerprint

Dive into the research topics of 'Efficient algorithms for finding a longest common increasing subsequence'. Together they form a unique fingerprint.

Cite this