Inkrementelle Algorithmen zur Berechnung der Menge der Periodenmengen
Incremental algorithms for computing the set of period sets
Algorithmes incrémentaux pour le calcul de l'ensemble des ensembles de périodes
Résumé
Overlaps between strings are crucial in many areas of computer science, such as bioinformatics, code design, and stringology. A self overlapping string is characterized by its periods and borders. A period of a string $u$ is the starting position of a suffix of $u$ that is also a prefix $u$, and such a suffix is called a border. Each word of length, say $n>0$, has a set of periods, but not all combinations of integers are sets of periods. The question we address is how to compute the set, denoted $\Gamma_n$, of all period sets of strings of length $n$. Computing the period set for all possible words of length $n$ is clearly prohibitive. The cardinality of $\Gamma_n$ is exponential in $n$. One dynamic programming algorithm exists for enumerating $\Gamma_n$, but it suffers from an expensive space complexity. After stating some combinatorial properties of period sets, we present a novel algorithm that computes $\Gamma_n$ from $\Gamma_{n-1}$, for any length $n>1$.
The period set of a string $u$ is a key information for computing the absence probability of $u$ in random texts. Hence, computing $\Gamma_n$ is useful for assessing the significance of word statistics, such as the number of missing $k$-mers in a random text, or the number of shared $k$-mers between two random texts. Besides applications, investigating $\Gamma_n$ is interesting per se as it unveils combinatorial properties of string overlaps.
Les chevauchements entre chaînes de caractères sont cruciaux dans de nombreux domaines de l'informatique, tels que la bio-informatique, la conception de codes et l'algorithmique du texte. Une chaîne qui se chevauche elle-même est caractérisée par ses périodes et ses bordures. Une période d'une chaîne u est la position de départ d'un suffixe de u qui est aussi un préfixe u, et un tel suffixe est nommé bordure. Chaque mot de longueur, disons n > 0, possède un ensemble de périodes, mais toutes les combinaisons d'entiers ne sont pas des ensembles de périodes. La question que nous nous posons est de savoir comment calculer l'ensemble, noté Γn , de tous les ensembles de périodes des chaînes de longueur n. Calculer l'ensemble de périodes pour tous les mots possibles de longueur n est clairement prohibitif, puisque la cardinalité de Γn est exponentielle en n. Un algorithme de programmation dynamique existe pour énumérer Γn, mais il souffre d'une complexité spatiale trop coûteuse. Après avoir énoncé quelques propriétés combinatoires des ensembles de périodes, nous présentons des algorithmes qui calculent Γn à partir de Γn-1, pour toute longueur n > 1. L'ensemble de périodes d'une chaîne de caractères u est une information clé pour calculer la probabilité d'absence de u dans des textes aléatoires. Par conséquent, le calcul de Γn est utile pour évaluer l'importance des statistiques sur les mots, telles que le nombre de k-mers manquants dans un texte aléatoire ou le nombre de k-mers communs à deux textes aléatoires. Outre ses applications, l'étude de Γn est intéressante en soi car elle révèle les propriétés combinatoires des chevauchements de chaînes de caractères.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| Licence |
