Minimal auxiliary Markov chains through sequential elimination of states

References

• Aho, A. V., and M. J. Corasick. 1975. Efficient string matching: An aid to bibliographic search. Communications of the ACM 18 (6), 333–40.
   Google Scholar
• Aston, J. A. D., and D. E. K. Martin. 2007. Distributions associated with general runs and patterns in hidden Markov models. Annals of Applied Statistics 1 (2), 585–611.
   Google Scholar
• Benson, G. 1999. Tandem repeats finder: a program to analyze DNA sequences. Nucleic Acids Research 27, 573–80.
   Google Scholar
• Benson, G., and D. Y. F. Mak. 2009. Exact distribution of a spaced seed statistic for DNA homology detection. String Processing and Information Retrieval, Lecture Notes in Computer Science 5280, pp. 282–93.
   Google Scholar
• Brookner, E. 1966. Recurrent events in a Markov chain. Information and Control 9, 215–29.
   Google Scholar
• Fu, J. C., and M. V. Koutras. 1994. Distribution theory of runs: a Markov chain approach. Journal of the American Statistical Association 89, 1050–8.
   Google Scholar
• Hopcroft, J. E. 1971. An n log n algorithm for minimizing states in a finite automaton. In: Z. Kohavi and A. Paz (Ed.), Theory of Machines and Computations. New York: Academic Press, pp. 189–96.
   Google Scholar
• Hopcroft, J. E., R. Motwani, and J. D. Ullman. 2001. Introduction to Automata Theory, Languages, and Computation. New York: Addison-Wesley.
   Google Scholar
• Keich, U., M. Li, B. Ma, and J. Tromp. 2004. On spaced seeds for similarity search. Discrete Applied Mathematics 138 (3), 253–63.
   Google Scholar
• Koutras, M. V. and V. A. Alexandrou. 1995. Runs, scans and urn models: A unified Markov chain approach. Annals of the Institute of Statistical Mathematics 47, 743–66.
   Google Scholar
• Lladser, M. E. 2007. Minimal Markov chain embeddings of pattern problems. Proceedings of the 2007 Information Theory and Applications Workshop, University of California, San Diego.
   Google Scholar
• Lladser, M. E., M. D. Betterton, and R. Knight. 2008. Multiple pattern matching: a Markov chain approach. Journal of Mathematical Biology 56, 51–92.
   Google Scholar
• Ma, B., J. Tromp, and M. Li. 2002. PatternHunter: faster and more sensitive homology search. Bioinformatics 18 (3), 440–5.
   Google Scholar
• Marshall, T., and S. Rahmann. 2008. Probabilistic arithmetic automata and their application to pattern matching statistics. Lecture Notes in Computer Science 5029, Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching, pp. 95–106).
   Google Scholar
• Martin, D. E. K. 2006. The exact joint distribution of the sum of heads and apparent size statistics of a tandem repeats finder algorithm. Bulletin of Mathematical Biology 68, 2353–64.
   Google Scholar
• Martin, D. E. K. 2015. P-values for the discrete scan statistic through slack variables. Communication in Statistics—Simulation & Computation 44 (9), 2223–39.
   Google Scholar
• Martin, D. E. K., and J. A. D. Aston. 2008. Waiting time distribution of generalized later patterns. Computational Statistics and Data Analysis 52, 4879–90.
   Google Scholar
• Martin, D. E. K., and J. A. D. Aston. 2013. Distributions of statistics of hidden state sequences through the sum-product algorithm. Methodology and Computing in Applied Probability 15 (4), 897–918.
   Google Scholar
• Martin, D. E. K., and D. A. Coleman. 2011. Distributions of clump statistics for a collection of words. Journal of Applied Probability 48, 1049–59.
   Google Scholar
• Martin, D. E. K., and L. Noé. 2017. Faster exact probabilities for statistics of overlapping pattern occurrences. Annals of the Institute of Statistical Mathematics 69 (1), 231–48.
   Google Scholar
• Mealy, G. H. 1955. A method for synthesizing sequential circuits. Bell System Technical Journal 34 (5), 1045–79.
   Google Scholar
• Nuel, G. 2008. Pattern Markov chains: Optimal Markov chain embedding through deterministic finite automata. Journal of Applied Probability 45 (1), 226–43.
   Google Scholar
• Ribeca, P., and E. Raineri. 2008. Faster exact Markovian probability functions for motif occurrences: a DFA-only approach. Bioinformatics 24, 2839–48.
   Google Scholar
• Robin, S., F. Rodolphe, S. Schbath. 2005. DNA, Words and Models. UK: Cambridge University Press.
   Google Scholar
• Robin, S., J. J. Daudin, H. Richard, M. F. Sagot, S. Schbath. 2002. Occurrence probability of structured motifs in random sequences. Journal of Computational Biology 9 (6), 761–73.
   Google Scholar
• Stefanov, V. T., S. Robin, S. Schbath. 2007. Waiting times for clumps of patterns and for structured motifs in random sequences. Discrete Applied Mathematics 155, 868–80.
   Google Scholar
• Tewari, A., U. Srivastava, and P. Gupta. 2002. A parallel DFA minimization algorithm. Lecture Notes in Computer Science 2552, pp. 34–40.
   Google Scholar