A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2010

A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems

Résumé

The analysis of pattern occurrences has numerous applications, in particular in biology. In this article, a symbolic method is proposed to compute the distribution associated to the number of occurences of a specific pattern in a random text generated by a stochastic 0L-system. To that purpose, a semiring structure is set for combinatorial classes composed of weighted words. This algebraic structure relies on new union and concatenation operators which, under some assumptions, are admissible constructions. Decomposing the combinatorial classes of interest by using these binary operators enables the direct translation of specifications into a set of functional equations relating generating functions thanks to transformation rules. The article ends with two examples. The first one deals with unary patterns and the connection with multitype branching process is established. The second one is about a pattern composed of two letters and underlines the importance of writing a proper specification.
Les études portant sur les occurrences de patterns dans un mot ont déjà donné lieu à de nombreuses applications, notamment en biologie. Dans cet article, une méthode symbolique permettant le calcul de la distribution associée au nombre d'occurrences d'un pattern donné dans un mot aléatoire généré par un 0L-système stochastique est proposée. Dans cette optique, une structure de semi-anneau est mise en place pour des classes combinatoires composées de mots pondérés. Cette structure algébrique utilise de nouveaux opérateurs d'union et de concaténation, lesquels sont, sous certaines hypothèses, des constructions admissibles. Ainsi, décomposer les classes combinatoires d'intérêt en utilisant ces opérateurs binaires permet la traduction directe des spécifications en un système d'équations fonctionnelles impliquant les fonctions génératrices correspondantes grâce à un ensemble de règles de transformation. L'article se termine par deux exemples. Le premier traite de patterns unaires et le lien avec les processus de branchement multitypes est établi. Le second concerne un pattern composé de deux lettres et met en évidence l'importance d'avoir une bonne spécification.
Fichier principal
Vignette du fichier
FinalLoiAOFA2010.pdf (179.9 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

inria-00529137 , version 1 (25-10-2010)
inria-00529137 , version 2 (20-08-2015)

Identifiants

  • HAL Id : inria-00529137 , version 1

Citer

Cedric Loi, Paul-Henry Cournède, Jean Françon. A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems. Discrete Mathematics and Theoretical Computer Science, 2010, pp.461-476. ⟨inria-00529137v1⟩

Collections

ECP-DR MAS
280 Consultations
651 Téléchargements

Partager

Gmail Facebook X LinkedIn More