The gapped k-deck problem

Golm, Rebecca

Permalink

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

Description

Title

The gapped k-deck problem

Author(s)

Golm, Rebecca

Issue Date

2023-05-01

Director of Research (if dissertation) or Advisor (if thesis)

Milenkovic, Olgica

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Gapped subsequences
• k-deck
• Morse-Thue sequences
• String reconstruction

Abstract

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_2(k)$. Second, we dicuss some properties of the ``padded"-Morse-Thue sequence. Lastly, we improve the bound on $G_2(k)$ using the approach by Dudik and Schulman.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Rebecca Golm

Owning Collections