Inkrementelle Algorithmen zur Berechnung der Menge der Periodenmengen
Incremental computation of the set of period sets
Algorithmes incrémentaux pour le calcul de l'ensemble des ensembles de périodes
Résumé
Overlaps between words are crucial in many areas of computer science, such as code design, stringology, and bioinformatics. A self overlapping word is characterized by its periods and borders. A period of a word 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. Computing the period set of a word u takes linear time in the length of u. We address the question of computing, the set, denoted Γn , of all period sets of words of length n. Although period sets have been characterized, there is no formula to compute the cardinality of Γn (which is exponential in n), and the known dynamic programming algorithm to enumerate Γn suffers from its space complexity. We present an incremental approach to compute Γn from Γn−1 , which reduces the space complexity, and then a constructive certification algorithm useful for verification purposes. The incremental approach defines a parental relation between sets in Γn−1 and Γn , enabling one to investigate the dynamics of period sets, and their intriguing statistical properties. Moreover, the period set of a word u is key for computing the absence probability of u in random texts. Thus, knowing Γn is useful to assess the significance of word statistics, such as the number of missing words in a random text.
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 |
