Faster Exact Probabilities for Statistics of Overlapping Pattern Occurrences

• Activity Number: 176
• Type: Contributed
• Date/Time: Monday, August 4, 2014 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Donald Martin*+
• Companies: North Carolina State University
• Keywords: spaced seeds ; deterministic finite automaton ; distribution of pattern statistic ; statistical inference

Abstract

When using an auxiliary Markov chain to compute probabilities for pattern statistics, the computational complexity is directly related to the number of Markov chain states. Thus in recent years, minimal deterministic finite automata have been used as data structures that facilitate computation while keeping the number of states at a minimum. For statistics where overlapping and non-overlapping pattern occurrences are treated differently, one could form an extended automaton that includes prefixes of initial and overlapping word occurrences, and then minimize the extended automaton. However, there are situations where forming a full extended automaton and then minimizing it is computationally expensive. We give a method to bypass the formation of a full extended automaton before minimization that facilitates efficient computation. The method is applied to the distribution of the number of sequence positions covered by spaced seed hits, a pattern matching paradigm that has proven fruitful in similarity searches for DNA sequences.