Online Program Home
My Program

Abstract Details

Activity Number: 427
Type: Contributed
Date/Time: Tuesday, August 2, 2016 : 2:00 PM to 3:50 PM
Sponsor: Section on Statistical Computing
Abstract #319566 View Presentation
Title: Efficient Formation of Auxiliary Markov Chains for Computing the Distribution of the Number of Structured Motifs
Author(s): Donald Martin*
Companies: North Carolina State University
Keywords: auxiliary Markov chain ; deterministic finite automaton ; minimal state space ; structured motifs

When using an auxiliary Markov chain (AMC) to compute sampling distributions, the computational complexity is directly related to the number of Markov chain states. For certain complex pattern statistics, minimal deterministic finite automata (DFA) have been used to facilitate efficient computation by reducing the number of AMC states to a minimal set sufficient for computing the distribution. However, it can be the case that forming a DFA before applying a minimization algorithm is computationally expensive. To deal with these situations, we give a characterization of equivalent states so that extra ones (and their offspring) are deleted during the process of state space formation. The method is illustrated on the problem of computing the distribution of the number of structured motifs, a model that is useful for locating binding sites in DNA sequences. The underlying sequence is modeled as a Markov chain.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2016 program

Copyright © American Statistical Association