189 – Recent Developments in Multiple Testing
Efficient Formation of Auxiliary Markov Chains Through Determining Rules for Equivalent States
Donald E.K Martin
North Carolina State University
When using an auxiliary Markov chain to compute probabilities for a statistic, 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 in recent years to facilitate efficient computation by reducing the number of states of the Markov chain. For example, when statistics of overlapping word occurrences are counted differently than non-overlapping occurrences, a DFA and an associated Markov chain have been generated to keep track of the overlapping structure of pattern occurrences, and then theory on minimizing DFA applied to minimize the number of Markov chain states. However, there are situations where forming a full automaton before minimizing it is computationally expensive. We give a way to determine rules for equivalent states so that they can be eliminated during the process of forming the state space, thus bypassing the formation of a full automaton before reducing its states. The utility of the procedure is illustrated on the problems of computing distributions associated with coverage of clumps and spaced seeds.