Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction

We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biology. We provide a number of new and improved bounds for exact string reconstruction for settings where either the string or the queries are “mixed-up”. For example, we show that a periodic (i.e., “mixed-up”) string, $S=p^k{p}^{\mathrm{\prime }}$, of smallest period $p$, where $\mathrm{\mid }{p}^{\mathrm{\prime }}\mathrm{\mid }<\mathrm{\mid }p\mathrm{\mid }$, can be reconstructed using $O(\sigma \mathrm{\mid }p\mathrm{\mid }+\lg n)$ substring queries, where $\sigma$ is the alphabet size, if $n=\mathrm{\mid }S\mathrm{\mid }$ is unknown. We also show that we can reconstruct $S$ after having been corrupted by a small number of errors $d$, measured by Hamming distance. In this case, we give an algorithm that uses $O(d\sigma \mathrm{\mid }p\mathrm{\mid }+d\mathrm{\mid }p\mathrm{\mid }\lg \frac{n}{d+1})$ queries. In addition, we show that a periodic string can be reconstructed using $2\sigma\lceil\lg n\rceil + 2|p|\lceil\lg \sigma\rceil$ subsequence queries, and that general strings can be reconstructed using $2\sigma \lceil \lg n\rceil +n\lceil \lg \sigma \rceil$ subsequence queries, without knowledge of $n$ in advance. This latter result improves the previous best, decades-old result, by Skiena and Sundaram. Finally, we believe we are the first to study the exact-learning query complexity for string reconstruction using jumbled-index queries, which are a “mixed-up” typeA of query that have received much attention of late.