Abstract
Strings or words, considered as sequences of letters, play a crucial role in both computer science and mathematics, with applications in areas as diverse as word statistics, string processing, code design, or bioinformatics. In bioinformatics for instance, the question of genome assembly requires to compute overlaps between millions of short strings, represent them in an assembly graph, and then to find an appropriate path in this graph to infer the target genome sequence.This thesis investigates several theoretical problems related to overlaps in strings.We first explore the concept of period sets, which describes how a word overlaps with itself. Revisiting Guibas and Odlyzko’s 1981 conjecture on the growth of the number of valid period sets, we provide an upper bound for the ratio of logarithms of the number of period sets and word length, establishing the convergence of this ratio and closing this longstanding conjecture.Next, we investigate correlations, which capture overlaps between two words by identifying where a suffix of one word matches a prefix of the other. We first characterize correlations and study the number of correlations for a given word length. We prove an asymptotic convergence result that is similar to the one obtained for period sets. By calculating how many pairs of words share the same correlation, we address important questions on word overlaps, including two open problems posed by Gabric in 2022 concerning the longest border between two words.In the appendix, we generalize these questions to the case where words of a pair can have different lengths, and then solve, in the general case, the open questions proposed by Gabric in 2022.Furthermore, we study periodicity in degenerate strings, a generalization of strings which models uncertainty in sequences, and was proposed as representations of pan-genomes. We propose new notions of periodicity, provide conditions for recognizing valid period sets, and analyze the convergence of the number of period sets for degenerate strings of a given length.To improve our understanding of string overlaps, we employ several mathematical tools and techniques, including combinatorics, graph theory, probability, and algorithmic analysis.Finally, we propose several open questions and conjectures that offer new perspectives on string overlaps.