The gapped k-deck problem

Reconstructing an unknown string from information about its subsequences is known as the string reconstruction problem and has applications in many different contexts such as bioinformatics and computer science. We study the $k$-deck problem, finding the smallest positive integer $S(k)$ such that there exist at least two strings of length $S(k)$ that share the same $k$-deck, i.e., the multiset of subsequences of length $k$. We introduce the new problem of gapped $k$-deck reconstruction: For a given gap parameter $s$, we seek the smallest positive integer G_s(k) such that there exist at least two distinct strings of length G_s(k) that cannot be distinguished based on a ``gapped'' set of $k$-subsequences. The gap constraint requires the elements in the subsequences to be at least $s$ positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same $2$-gapped $k$-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on G<sub>2</sub>(k). Second, we dicuss some properties of the ``padded"-Morse-Thue sequence. Lastly, we improve the bound on G₂(k) using the approach by Dudik and Schulman.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Golm, Rebecca

Contributors dc:contributor

• Milenkovic, Olgica

• Gapped Subsequences
• K-deck
• Morse-thue Sequences
• String Reconstruction

Statement dc:rights

• Copyright 2023 Rebecca Golm

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120117

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120117