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
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
