Fully incremental LCS computation

Yusuke Ishida; Shunsuke Inenaga; Ayumi Shinohara; Masayuki Takeda

doi:10.1007/11537311_49

Fully incremental LCS computation

Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Mathematical Informatics

Research output: Contribution to journal › Conference article › peer-review

11 Citations (Scopus)

Abstract

Sequence comparison is & fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between biological sequences. A common scheme for sequence comparison is the longest common subsequence (LCS) metric. This paper considers the fully incremental LCS computation problem as follows: For any strings A, B and characters a, b, compute LCS(aA, B), LCS(A, bB), LCS(Aa, B), and LCS(A, Bb), provided that L = LCS(A, B) is already computed. We present an efficient algorithm that computes the four LCS values above, in O(L) or O(n) time depending on where a new character is added, where n is the length of A. Our algorithm is superior in both time and space complexities to the previous known methods.

Original language	English
Pages (from-to)	563-574
Number of pages	12
Journal	Lecture Notes in Computer Science
Volume	3623
DOIs	https://doi.org/10.1007/11537311_49
Publication status	Published - 2005
Event	15th International Symposium on Fundamentals of Computation Theory, FCT 2005 - Lubeck, Germany Duration: Aug 17 2005 → Aug 20 2005

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11537311_49

Cite this

@article{5d21b112356b4796b499cd565aa82d8d,

title = "Fully incremental LCS computation",

abstract = "Sequence comparison is & fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between biological sequences. A common scheme for sequence comparison is the longest common subsequence (LCS) metric. This paper considers the fully incremental LCS computation problem as follows: For any strings A, B and characters a, b, compute LCS(aA, B), LCS(A, bB), LCS(Aa, B), and LCS(A, Bb), provided that L = LCS(A, B) is already computed. We present an efficient algorithm that computes the four LCS values above, in O(L) or O(n) time depending on where a new character is added, where n is the length of A. Our algorithm is superior in both time and space complexities to the previous known methods.",

author = "Yusuke Ishida and Shunsuke Inenaga and Ayumi Shinohara and Masayuki Takeda",

year = "2005",

doi = "10.1007/11537311_49",

language = "English",

volume = "3623",

pages = "563--574",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "15th International Symposium on Fundamentals of Computation Theory, FCT 2005 ; Conference date: 17-08-2005 Through 20-08-2005",

}

TY - JOUR

T1 - Fully incremental LCS computation

AU - Ishida, Yusuke

AU - Inenaga, Shunsuke

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

PY - 2005

Y1 - 2005

N2 - Sequence comparison is & fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between biological sequences. A common scheme for sequence comparison is the longest common subsequence (LCS) metric. This paper considers the fully incremental LCS computation problem as follows: For any strings A, B and characters a, b, compute LCS(aA, B), LCS(A, bB), LCS(Aa, B), and LCS(A, Bb), provided that L = LCS(A, B) is already computed. We present an efficient algorithm that computes the four LCS values above, in O(L) or O(n) time depending on where a new character is added, where n is the length of A. Our algorithm is superior in both time and space complexities to the previous known methods.

AB - Sequence comparison is & fundamental task in pattern matching. Its applications include file comparison, spelling correction, information retrieval, and computing (dis)similarities between biological sequences. A common scheme for sequence comparison is the longest common subsequence (LCS) metric. This paper considers the fully incremental LCS computation problem as follows: For any strings A, B and characters a, b, compute LCS(aA, B), LCS(A, bB), LCS(Aa, B), and LCS(A, Bb), provided that L = LCS(A, B) is already computed. We present an efficient algorithm that computes the four LCS values above, in O(L) or O(n) time depending on where a new character is added, where n is the length of A. Our algorithm is superior in both time and space complexities to the previous known methods.

UR - http://www.scopus.com/inward/record.url?scp=26844489395&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26844489395&partnerID=8YFLogxK

U2 - 10.1007/11537311_49

DO - 10.1007/11537311_49

M3 - Conference article

AN - SCOPUS:26844489395

SN - 0302-9743

VL - 3623

SP - 563

EP - 574

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 15th International Symposium on Fundamentals of Computation Theory, FCT 2005

Y2 - 17 August 2005 through 20 August 2005

ER -

Fully incremental LCS computation

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this