Elastic-Degenerate String Matching with 1 Error

Giulia Bernardini; Esteban Gabory; Solon P. Pissis; Leen Stougie; Michelle Sweering; Wiktor Zuba

doi:10.1007/978-3-031-20624-5_2

Elastic-Degenerate String Matching with 1 Error

Giulia Bernardini, Esteban Gabory, Solon P. Pissis, Leen Stougie, Michelle Sweering, Wiktor Zuba^*

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

58 Downloads (Pure)

Abstract

An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an O~ (nm^ω^-¹) + O(N) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where ω denotes the matrix multiplication exponent and the O~ (· ) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in O(k²mG+ kN) time under edit distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for k= 1, the existing algorithm runs in Ω(mN) time in the worst case. Here we make progress in this direction. We show that 1-EDSM can be solved in O((nm²+ N) log m) or O(nm³+ N) time under edit distance. For the decision version of the problem, we present a faster O(nm2logm+Nloglogm) -time algorithm. Our algorithms rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or range emptiness), which we show how to solve efficiently.

Original language	English
Title of host publication	LATIN 2022: Theoretical Informatics
Subtitle of host publication	15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings
Editors	Armando Castañeda, Francisco Rodríguez-Henríquez
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	20-37
Number of pages	18
ISBN (Electronic)	9783031206245
ISBN (Print)	9783031206238
DOIs	https://doi.org/10.1007/978-3-031-20624-5_2
Publication status	Published - 2022
Event	15th Latin American Symposium on Theoretical Informatics, LATIN 2022 - Guanajuato, Mexico Duration: 7 Nov 2022 → 11 Nov 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13568 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Latin American Symposium on Theoretical Informatics, LATIN 2022
Country/Territory	Mexico
City	Guanajuato
Period	7/11/22 → 11/11/22

Bibliographical note

Funding Information:
Keywords: String algorithms · Approximate string matching · Edit distance · Degenerate strings · Elastic-degenerate strings The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreements No 872539 and 956229, respectively; and the MUR - FSE REACT EU - PON R&I 2014–2020.

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Funding

Keywords: String algorithms · Approximate string matching · Edit distance · Degenerate strings · Elastic-degenerate strings The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreements No 872539 and 956229, respectively; and the MUR - FSE REACT EU - PON R&I 2014–2020.

Funders	Funder number
ALPACA
PANGAIA
Horizon 2020 Framework Programme	872539, 956229
Horizon 2020 Framework Programme
Faculty of Science and Engineering, University of Manchester
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	NETWORKS-024.002.003
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Keywords

Approximate string matching
Degenerate strings
Edit distance
Elastic-degenerate strings
String algorithms

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-031-20624-5_2

Elastic-Degenerate String Matching with 1 ErrorFinal published version, 527 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Bernardini, G., Gabory, E., Pissis, S. P., Stougie, L., Sweering, M., & Zuba, W. (2022). Elastic-Degenerate String Matching with 1 Error. In A. Castañeda, & F. Rodríguez-Henríquez (Eds.), LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings (pp. 20-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13568 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-20624-5_2

Bernardini, Giulia ; Gabory, Esteban ; Pissis, Solon P. et al. / Elastic-Degenerate String Matching with 1 Error. LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings. editor / Armando Castañeda ; Francisco Rodríguez-Henríquez. Springer Science and Business Media Deutschland GmbH, 2022. pp. 20-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a7e0691454144e289dec8d41cbf3b249,

title = "Elastic-Degenerate String Matching with 1 Error",

abstract = "An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an O~ (nmω-1) + O(N) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where ω denotes the matrix multiplication exponent and the O~ (· ) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in O(k2mG+ kN) time under edit distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for k= 1, the existing algorithm runs in Ω(mN) time in the worst case. Here we make progress in this direction. We show that 1-EDSM can be solved in O((nm2+ N) log m) or O(nm3+ N) time under edit distance. For the decision version of the problem, we present a faster O(nm2logm+Nloglogm) -time algorithm. Our algorithms rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or range emptiness), which we show how to solve efficiently.",

keywords = "Approximate string matching, Degenerate strings, Edit distance, Elastic-degenerate strings, String algorithms",

author = "Giulia Bernardini and Esteban Gabory and Pissis, {Solon P.} and Leen Stougie and Michelle Sweering and Wiktor Zuba",

note = "Funding Information: Keywords: String algorithms · Approximate string matching · Edit distance · Degenerate strings · Elastic-degenerate strings The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the PANGAIA and ALPACA projects that have received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreements No 872539 and 956229, respectively; and the MUR - FSE REACT EU - PON R&I 2014–2020. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 15th Latin American Symposium on Theoretical Informatics, LATIN 2022 ; Conference date: 07-11-2022 Through 11-11-2022",

year = "2022",

doi = "10.1007/978-3-031-20624-5_2",

language = "English",

isbn = "9783031206238",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

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

pages = "20--37",

editor = "Armando Casta{\~n}eda and Francisco Rodr{\'i}guez-Henr{\'i}quez",

booktitle = "LATIN 2022: Theoretical Informatics",

address = "Germany",

}

Bernardini, G, Gabory, E, Pissis, SP , Stougie, L, Sweering, M & Zuba, W 2022, Elastic-Degenerate String Matching with 1 Error. in A Castañeda & F Rodríguez-Henríquez (eds), LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13568 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 20-37, 15th Latin American Symposium on Theoretical Informatics, LATIN 2022, Guanajuato, Mexico, 7/11/22. https://doi.org/10.1007/978-3-031-20624-5_2

Elastic-Degenerate String Matching with 1 Error. / Bernardini, Giulia; Gabory, Esteban; Pissis, Solon P. et al.
LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings. ed. / Armando Castañeda; Francisco Rodríguez-Henríquez. Springer Science and Business Media Deutschland GmbH, 2022. p. 20-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13568 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Elastic-Degenerate String Matching with 1 Error

AU - Bernardini, Giulia

AU - Gabory, Esteban

AU - Pissis, Solon P.

AU - Stougie, Leen

AU - Sweering, Michelle

AU - Zuba, Wiktor

N1 - Funding Information: Keywords: String algorithms · Approximate string matching · Edit distance · Degenerate strings · Elastic-degenerate strings The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreements No 872539 and 956229, respectively; and the MUR - FSE REACT EU - PON R&I 2014–2020. Publisher Copyright: © 2022, Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an O~ (nmω-1) + O(N) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where ω denotes the matrix multiplication exponent and the O~ (· ) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in O(k2mG+ kN) time under edit distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for k= 1, the existing algorithm runs in Ω(mN) time in the worst case. Here we make progress in this direction. We show that 1-EDSM can be solved in O((nm2+ N) log m) or O(nm3+ N) time under edit distance. For the decision version of the problem, we present a faster O(nm2logm+Nloglogm) -time algorithm. Our algorithms rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or range emptiness), which we show how to solve efficiently.

AB - An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an O~ (nmω-1) + O(N) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where ω denotes the matrix multiplication exponent and the O~ (· ) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in O(k2mG+ kN) time under edit distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for k= 1, the existing algorithm runs in Ω(mN) time in the worst case. Here we make progress in this direction. We show that 1-EDSM can be solved in O((nm2+ N) log m) or O(nm3+ N) time under edit distance. For the decision version of the problem, we present a faster O(nm2logm+Nloglogm) -time algorithm. Our algorithms rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or range emptiness), which we show how to solve efficiently.

KW - Approximate string matching

KW - Degenerate strings

KW - Edit distance

KW - Elastic-degenerate strings

KW - String algorithms

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

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

U2 - 10.1007/978-3-031-20624-5_2

DO - 10.1007/978-3-031-20624-5_2

M3 - Conference contribution

AN - SCOPUS:85144528755

SN - 9783031206238

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 20

EP - 37

BT - LATIN 2022: Theoretical Informatics

A2 - Castañeda, Armando

A2 - Rodríguez-Henríquez, Francisco

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th Latin American Symposium on Theoretical Informatics, LATIN 2022

Y2 - 7 November 2022 through 11 November 2022

ER -

Bernardini G, Gabory E, Pissis SP , Stougie L, Sweering M, Zuba W. Elastic-Degenerate String Matching with 1 Error. In Castañeda A, Rodríguez-Henríquez F, editors, LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 20-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2022 Oct 29. doi: 10.1007/978-3-031-20624-5_2