Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Efficient Algorithms for Finding a Longest Common Increasing Subsequence
verfasst von : Wun-Tat Chan, Yong Zhang, Stanley P. Y. Fung, Deshi Ye, Hong Zhu
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
)loglog
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(
mr
2
,
mr
log ℓ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
(
n
ℓ log
n
) time. Our algorithm is faster when
r
is relatively small, e.g., for
r
< min(
n
2
/loglog
n
,
n
ℓ).