Efficient Formation of Auxiliary Markov Chains Through Determining Rules for Equivalent States

• Activity Number: 189
• Type: Contributed
• Date/Time: Monday, August 10, 2015 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Donald Martin*
• Companies: North Carolina State University
• Keywords: active proper suffix ; extended patterns ; failure sequence ; minimal deterministic finite automaton ; seeded alignments ; spaced seed coverage

Abstract

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.