Efficient algorithms for finding a longest common increasing subsequence

Wun-Tat Chan (), Yong Zhang (), Stanley P. Y. Fung (), Deshi Ye () and Hong Zhu ()
Additional contact information
Wun-Tat Chan: University of Hong Kong
Yong Zhang: University of Hong Kong
Stanley P. Y. Fung: University of Leicester
Deshi Ye: University of Hong Kong
Hong Zhu: Fudan University

Journal of Combinatorial Optimization, 2007, vol. 13, issue 3, No 7, 277-288

Abstract: 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({\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)+m\cdot $$ 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\ell {\rm log} {\rm log} n+$$ Sort(n)) time. Our algorithm is faster when r is relatively small, e.g., for $$r

Keywords: Design and analysis of algorithms; Longest common increasing subsequence (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9031-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:13:y:2007:i:3:d:10.1007_s10878-006-9031-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9031-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().