Distribution of Statistics of h-GAP Clusters for a Collection of Words

• Activity Number: 681
• Type: Contributed
• Date/Time: Thursday, August 5, 2010 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Deidra Andrea Coleman*+ and Donald E.K. Martin
• Companies: North Carolina State University and North Carolina State University
• Keywords: auxiliary Markov chain ; clump counting ; h-gap clusters ; coarsest partition

Abstract

We give a recursive method for computing the exact distribution of the number of h-gap clusters of a collection of words and their coverage. An h-gap cluster begins with a word of the collection and continues while there is no gap between word occurrences that is greater than h. When h=-1, the words of a cluster must overlap, and the cluster is called a clump. The methods facilitate the computation of p-values for testing procedures. A word may contain other words of the collection, making the computation more general. The underlying sequence is assumed to be Markovian of an arbitrary order. Probabilities are updated recursively using an auxiliary Markov chain, making the computations easy to implement. Automata theory is used to help limit the number of states of the auxiliary chain. The methodology is applied to pattern discovery in DNA sequences.