TY - GEN
T1 - Efficient algorithms for finding a longest common increasing subsequence
AU - Chan, Wun-Tat
AU - Zhang, Yong
AU - Fung, Stanley P. Y.
AU - Ye, Deshi
AU - Zhu, Hong
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2005
Y1 - 2005
N2 - 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 ℓ, nℓ + 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 ℓ is the length of the LCIS. For m sequences where m ≥ 3, we find the LCIS in O(min(mr2, mr log ℓ logm 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(n2) and O(nℓ log n) time. Our algorithm is faster when r is relatively small, e.g., for r < min(n2/ log log n, nℓ). © Springer-Verlag Berlin Heidelberg 2005.
AB - 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 ℓ, nℓ + 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 ℓ is the length of the LCIS. For m sequences where m ≥ 3, we find the LCIS in O(min(mr2, mr log ℓ logm 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(n2) and O(nℓ log n) time. Our algorithm is faster when r is relatively small, e.g., for r < min(n2/ log log n, nℓ). © Springer-Verlag Berlin Heidelberg 2005.
UR - http://www.scopus.com/inward/record.url?scp=33744955930&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33744955930&origin=recordpage
U2 - 10.1007/11602613_67
DO - 10.1007/11602613_67
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540309357
SN - 9783540309352
VL - 3827 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 665
EP - 674
BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
PB - Springer Verlag
T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005
Y2 - 19 December 2005 through 21 December 2005
ER -