Compound Poisson approximation of word counts in DNA sequences

Institut National de la Recherche Agronomique, France

Abstract

Identifying words with unexpected frequencies is an important problem in the analysis of long DNA sequences. To solve it, we need an approximation of the distribution of the number of occurrences N(W) of a word W. Modeling DNA sequences with m-order Markov chains, we use the Chen-Stein method to obtain Poisson approximations for two different counts. We approximate the “declumped” count of W by a Poisson variable and the number of occurrences N(W) by a compound Poisson variable. Combinatorial results are used to solve the general case of overlapping words and to calculate the parameters of these distributions.

Résumé

La recherche de mots de fréquence exceptionnelle est un problème important dans l'analyse des longues séquences d'ADN. Elle nécessite de connaître la distribution, du moins asymptotique, du nombre d'occurrences N(W) d'un mot W dans une séquence. En modélisant une séquence par une chaîne de Markov homogène d'ordre m, nous utilisons la méthode de Chen-Stein pour obtenir des approximations de Poisson pour deux types de comptage des mots. Lorsque la longueur du mot W est assez grande, nous approchons la loi du nombre de trains d'occurrences chevauchantes de W par une loi de Poisson, tandis que la loi du nombre d'occurrences chevauchantes, N(W), est approchée par une loi de Poisson composée. Le calcul des paramètres de ces lois nécessite une étude soigneuse de la structure périodique des mots pour prendre en compte tous les chevauchements possibles.