On the Construction of Elastic Degenerate Strings

Nicola Rizzo; Veli Mäkinen; Nadia Pisanti

doi:10.4230/OASIcs.Grossi.2

On the Construction of Elastic Degenerate Strings

Nicola Rizzo
, Veli Mäkinen
, Nadia Pisanti

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

Abstract

An elastic degenerate string (EDS) is a sequence of sets of strings. In the context of bioinformatics, EDSes can be used to represent the variations observed in a population from its consensus genome. Pattern matching and comparison problems on EDSes have been widely studied in the literature, but their construction has been largely omitted. We fill this gap by showing how algorithms originally developed for related problems of founder reconstruction can be adapted to minimize the total cardinality of the EDS sets and total length of the EDS strings in linear time, given suitable multiple alignments representing the input data.

Original language	English
Title of host publication	From Strings to Graphs, and Back Again : A Festschrift for Roberto Grossi's 60th Birthday
Editors	Alessio Conte, Alessio Conte, Andrea Marino, Giovanna Rosone, Jeffrey Scott Vitter, Jeffrey Scott Vitter
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	11 Aug 2025
Article number	2
ISBN (Electronic)	978-3-95977-391-1
DOIs	https://doi.org/10.4230/OASIcs.Grossi.2
Publication status	Published - 11 Aug 2025
MoE publication type	A4 Article in conference proceedings
Event	From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025 - Venice, Italy Duration: 25 Jul 2025 → …

Publication series

Name	OpenAccess Series in Informatics
Volume	132
ISSN (Print)	2190-6807

Bibliographical note

Publisher Copyright:
© Nicola Rizzo, Veli Mäkinen, and Nadia Pisanti;

Fields of Science

data structures
dynamic programming
founder reconstruction
multiple sequence alignment
pattern matching
positional Burrows–Wheeler transform
segmentation algorithms
semi-dynamic range minimum queries
113 Computer and information sciences

Access to Document

10.4230/OASIcs.Grossi.2Licence: CC BY

OASIcs.Grossi.2Final published version, 1.39 MBLicence: CC BY

Cite this

Rizzo, N., Mäkinen, V., & Pisanti, N. (2025). On the Construction of Elastic Degenerate Strings. In A. Conte, A. Conte, A. Marino, G. Rosone, J. S. Vitter, & J. S. Vitter (Eds.), From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday Article 2 (OpenAccess Series in Informatics; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/OASIcs.Grossi.2

Rizzo, Nicola ; Mäkinen, Veli ; Pisanti, Nadia. / On the Construction of Elastic Degenerate Strings. From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. editor / Alessio Conte ; Alessio Conte ; Andrea Marino ; Giovanna Rosone ; Jeffrey Scott Vitter ; Jeffrey Scott Vitter. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. (OpenAccess Series in Informatics).

@inproceedings{e2f1ad559d45470a9167f306c13ee131,

title = "On the Construction of Elastic Degenerate Strings",

abstract = "An elastic degenerate string (EDS) is a sequence of sets of strings. In the context of bioinformatics, EDSes can be used to represent the variations observed in a population from its consensus genome. Pattern matching and comparison problems on EDSes have been widely studied in the literature, but their construction has been largely omitted. We fill this gap by showing how algorithms originally developed for related problems of founder reconstruction can be adapted to minimize the total cardinality of the EDS sets and total length of the EDS strings in linear time, given suitable multiple alignments representing the input data.",

keywords = "data structures, dynamic programming, founder reconstruction, multiple sequence alignment, pattern matching, positional Burrows–Wheeler transform, segmentation algorithms, semi-dynamic range minimum queries, 113 Computer and information sciences",

author = "Nicola Rizzo and Veli M{\"a}kinen and Nadia Pisanti",

note = "Publisher Copyright: {\textcopyright} Nicola Rizzo, Veli M{\"a}kinen, and Nadia Pisanti;; From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025 ; Conference date: 25-07-2025",

year = "2025",

month = aug,

day = "11",

doi = "10.4230/OASIcs.Grossi.2",

language = "English",

series = "OpenAccess Series in Informatics",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Alessio Conte and Alessio Conte and Andrea Marino and Giovanna Rosone and Vitter, \{Jeffrey Scott\} and Vitter, \{Jeffrey Scott\}",

booktitle = "From Strings to Graphs, and Back Again",

address = "Germany",

}

Rizzo, N , Mäkinen, V & Pisanti, N 2025, On the Construction of Elastic Degenerate Strings. in A Conte, A Conte, A Marino, G Rosone, JS Vitter & JS Vitter (eds), From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday., 2, OpenAccess Series in Informatics, vol. 132, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025, Venice, Italy, 25/07/2025. https://doi.org/10.4230/OASIcs.Grossi.2

On the Construction of Elastic Degenerate Strings. / Rizzo, Nicola ; Mäkinen, Veli; Pisanti, Nadia.
From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. ed. / Alessio Conte; Alessio Conte; Andrea Marino; Giovanna Rosone; Jeffrey Scott Vitter; Jeffrey Scott Vitter. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. 2 (OpenAccess Series in Informatics; Vol. 132).

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

TY - GEN

T1 - On the Construction of Elastic Degenerate Strings

AU - Rizzo, Nicola

AU - Mäkinen, Veli

AU - Pisanti, Nadia

N1 - Publisher Copyright: © Nicola Rizzo, Veli Mäkinen, and Nadia Pisanti;

PY - 2025/8/11

Y1 - 2025/8/11

N2 - An elastic degenerate string (EDS) is a sequence of sets of strings. In the context of bioinformatics, EDSes can be used to represent the variations observed in a population from its consensus genome. Pattern matching and comparison problems on EDSes have been widely studied in the literature, but their construction has been largely omitted. We fill this gap by showing how algorithms originally developed for related problems of founder reconstruction can be adapted to minimize the total cardinality of the EDS sets and total length of the EDS strings in linear time, given suitable multiple alignments representing the input data.

AB - An elastic degenerate string (EDS) is a sequence of sets of strings. In the context of bioinformatics, EDSes can be used to represent the variations observed in a population from its consensus genome. Pattern matching and comparison problems on EDSes have been widely studied in the literature, but their construction has been largely omitted. We fill this gap by showing how algorithms originally developed for related problems of founder reconstruction can be adapted to minimize the total cardinality of the EDS sets and total length of the EDS strings in linear time, given suitable multiple alignments representing the input data.

KW - data structures

KW - dynamic programming

KW - founder reconstruction

KW - multiple sequence alignment

KW - pattern matching

KW - positional Burrows–Wheeler transform

KW - segmentation algorithms

KW - semi-dynamic range minimum queries

KW - 113 Computer and information sciences

U2 - 10.4230/OASIcs.Grossi.2

DO - 10.4230/OASIcs.Grossi.2

M3 - Conference contribution

AN - SCOPUS:105013465227

T3 - OpenAccess Series in Informatics

BT - From Strings to Graphs, and Back Again

A2 - Conte, Alessio

A2 - Marino, Andrea

A2 - Rosone, Giovanna

A2 - Vitter, Jeffrey Scott

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 2025

Y2 - 25 July 2025

ER -

Rizzo N , Mäkinen V, Pisanti N. On the Construction of Elastic Degenerate Strings. In Conte A, Conte A, Marino A, Rosone G, Vitter JS, Vitter JS, editors, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. 2. (OpenAccess Series in Informatics). doi: 10.4230/OASIcs.Grossi.2