Longest common subsequence with gap constraints

Duncan Adamson; Maria Kosche; Tore Koß; Florin Manea; Stefan Siemer

doi:10.1007/978-3-031-33180-0_5

Longest common subsequence with gap constraints

Duncan Adamson, Maria Kosche, Tore Koß^*, Florin Manea, Stefan Siemer

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings.

Original language	English
Title of host publication	Combinatorics on words
Subtitle of host publication	14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings
Editors	Anna Frid, Robert Mercaş
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	60-76
Number of pages	17
ISBN (Electronic)	9783031331800
ISBN (Print)	9783031331794
DOIs	https://doi.org/10.1007/978-3-031-33180-0_5
Publication status	Published - 2023
Event	14th International Conference on Combinatorics on Words, WORDS 2023 - Umeå, Sweden Duration: 12 Jun 2023 → 16 Jun 2023 Conference number: 14 https://dltwords2023.cs.umu.se/index.html

Publication series

Name	Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)
Publisher	Springer
Volume	13899 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Combinatorics on Words, WORDS 2023
Abbreviated title	WORDS 2023
Country/Territory	Sweden
City	Umeå
Period	12/06/23 → 16/06/23
Internet address	https://dltwords2023.cs.umu.se/index.html

Access to Document

10.1007/978-3-031-33180-0_5

https://livrepository.liverpool.ac.uk/id/eprint/3170913Licence: CC BY

Cite this

Adamson, D., Kosche, M., Koß, T., Manea, F., & Siemer, S. (2023). Longest common subsequence with gap constraints. In A. Frid, & R. Mercaş (Eds.), Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings (pp. 60-76). (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13899 LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-33180-0_5

Adamson, Duncan ; Kosche, Maria ; Koß, Tore et al. / Longest common subsequence with gap constraints. Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. editor / Anna Frid ; Robert Mercaş. Cham : Springer Nature Switzerland AG, 2023. pp. 60-76 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)).

@inproceedings{42323badc5004f84a2de5cef616fb760,

title = "Longest common subsequence with gap constraints",

abstract = "We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings.",

author = "Duncan Adamson and Maria Kosche and Tore Ko{\ss} and Florin Manea and Stefan Siemer",

year = "2023",

doi = "10.1007/978-3-031-33180-0_5",

language = "English",

isbn = "9783031331794",

series = "Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)",

publisher = "Springer Nature Switzerland AG",

pages = "60--76",

editor = "Anna Frid and Robert Merca{\c s}",

booktitle = "Combinatorics on words",

address = "Switzerland",

note = "14th International Conference on Combinatorics on Words, WORDS 2023, WORDS 2023 ; Conference date: 12-06-2023 Through 16-06-2023",

url = "https://dltwords2023.cs.umu.se/index.html",

}

Adamson, D, Kosche, M, Koß, T, Manea, F & Siemer, S 2023, Longest common subsequence with gap constraints. in A Frid & R Mercaş (eds), Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics), vol. 13899 LNCS, Springer Nature Switzerland AG, Cham, pp. 60-76, 14th International Conference on Combinatorics on Words, WORDS 2023, Umeå, Sweden, 12/06/23. https://doi.org/10.1007/978-3-031-33180-0_5

Longest common subsequence with gap constraints. / Adamson, Duncan; Kosche, Maria; Koß, Tore et al.
Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. ed. / Anna Frid; Robert Mercaş. Cham: Springer Nature Switzerland AG, 2023. p. 60-76 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13899 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Longest common subsequence with gap constraints

AU - Adamson, Duncan

AU - Kosche, Maria

AU - Koß, Tore

AU - Manea, Florin

AU - Siemer, Stefan

N1 - Conference code: 14

PY - 2023

Y1 - 2023

N2 - We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings.

AB - We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings.

U2 - 10.1007/978-3-031-33180-0_5

DO - 10.1007/978-3-031-33180-0_5

M3 - Conference contribution

AN - SCOPUS:85168848420

SN - 9783031331794

T3 - Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)

SP - 60

EP - 76

BT - Combinatorics on words

A2 - Frid, Anna

A2 - Mercaş, Robert

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 14th International Conference on Combinatorics on Words, WORDS 2023

Y2 - 12 June 2023 through 16 June 2023

ER -

Adamson D, Kosche M, Koß T, Manea F, Siemer S. Longest common subsequence with gap constraints. In Frid A, Mercaş R, editors, Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. Cham: Springer Nature Switzerland AG. 2023. p. 60-76. (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)). Epub 2023 May 31. doi: 10.1007/978-3-031-33180-0_5