2026-08-11T21:31:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23801 2026-02-09T06:17:10Z ddc:004 open_access

On the Construction of Elastic Degenerate Strings Rizzo, Nicola Mäkinen, Veli Pisanti, Nadia multiple sequence alignment pattern matching data structures segmentation algorithms founder reconstruction dynamic programming semi-dynamic range minimum queries positional Burrows-Wheeler transform 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicola Rizzo and Veli Mäkinen and Nadia Pisanti 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.2 urn:nbn:de:0030-drops-238014 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.2 eng https://creativecommons.org/licenses/by/4.0/legalcode