Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences

Pierre Pudlo

ESAIM: Probability and Statistics (2010)

  • Volume: 14, page 435-455
  • ISSN: 1292-8100

Abstract

top
To establish lists of words with unexpected frequencies in long sequences, for instance in a molecular biology context, one needs to quantify the exceptionality of families of word frequencies in random sequences. To this aim, we study large deviation probabilities of multidimensional word counts for Markov and hidden Markov models. More specifically, we compute local Edgeworth expansions of arbitrary degrees for multivariate partial sums of lattice valued functionals of finite Markov chains. This yields sharp approximations of the associated large deviation probabilities. We also provide detailed simulations. These exhibit in particular previously unreported periodic oscillations, for which we provide theoretical explanations.

How to cite

top

Pudlo, Pierre. "Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences." ESAIM: Probability and Statistics 14 (2010): 435-455. <http://eudml.org/doc/250827>.

@article{Pudlo2010,
abstract = { To establish lists of words with unexpected frequencies in long sequences, for instance in a molecular biology context, one needs to quantify the exceptionality of families of word frequencies in random sequences. To this aim, we study large deviation probabilities of multidimensional word counts for Markov and hidden Markov models. More specifically, we compute local Edgeworth expansions of arbitrary degrees for multivariate partial sums of lattice valued functionals of finite Markov chains. This yields sharp approximations of the associated large deviation probabilities. We also provide detailed simulations. These exhibit in particular previously unreported periodic oscillations, for which we provide theoretical explanations. },
author = {Pudlo, Pierre},
journal = {ESAIM: Probability and Statistics},
keywords = {Markov chains; hidden Markov models; large deviations; edgeworth expansions; protein and DNA sequences; Edgeworth expansions},
language = {eng},
month = {12},
pages = {435-455},
publisher = {EDP Sciences},
title = {Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences},
url = {http://eudml.org/doc/250827},
volume = {14},
year = {2010},
}

TY - JOUR
AU - Pudlo, Pierre
TI - Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences
JO - ESAIM: Probability and Statistics
DA - 2010/12//
PB - EDP Sciences
VL - 14
SP - 435
EP - 455
AB - To establish lists of words with unexpected frequencies in long sequences, for instance in a molecular biology context, one needs to quantify the exceptionality of families of word frequencies in random sequences. To this aim, we study large deviation probabilities of multidimensional word counts for Markov and hidden Markov models. More specifically, we compute local Edgeworth expansions of arbitrary degrees for multivariate partial sums of lattice valued functionals of finite Markov chains. This yields sharp approximations of the associated large deviation probabilities. We also provide detailed simulations. These exhibit in particular previously unreported periodic oscillations, for which we provide theoretical explanations.
LA - eng
KW - Markov chains; hidden Markov models; large deviations; edgeworth expansions; protein and DNA sequences; Edgeworth expansions
UR - http://eudml.org/doc/250827
ER -

References

top
  1. C. Andriani and P. Baldi, Sharp estimates of deviations of the sample mean in many dimensions. Ann. Inst. H. Poincaré Probab. Statist.33 (1997) 371–385.  Zbl0882.60022
  2. R.R. Bahadur and R.R. Rao, On deviations of the sample mean. Ann. Math. Statist.31 (1960) 1015–1027.  Zbl0101.12603
  3. P. Barbe and M. Broniatowski, Large-deviation probability and the local dimension of sets, in Proceedings of the 19th Seminar on Stability Problems for Stochastic Models, Vologda, 1998, Part I. (2000), Vol. 99, pp. 1225–1233.  Zbl0962.60011
  4. N.R. Chaganty and J. Sethuraman, Strong large deviation and local limit theorems. Ann. Probab.21 (1993) 1671–1690.  Zbl0786.60026
  5. S. Datta and W.P. McCormick, On the first-order Edgeworth expansion for a Markov chain. J. Multivariate Anal.44 (1993) 345–359.  Zbl0770.60023
  6. A. Dembo and O. Zeitouni, Large deviations techniques and applications. Volume 38 of Appl. Math. (New York). Second edition. Springer-Verlag, New York (1998).  Zbl0896.60013
  7. P. Flajolet, W. Szpankowski and B. Vallée, Hidden word statistics. J. ACM53 (2006) 147–183 (electronic).  Zbl1316.68111
  8. M. Iltis, Sharp asymptotics of large deviations in Rd. J. Theoret. Probab.8 (1995) 501–522.  Zbl0831.60042
  9. M. Iltis, Sharp asymptotics of large deviations for general state-space Markov-additive chains in Rd. Statist. Probab. Lett.47 (2000) 365–380.  Zbl0988.60012
  10. I. Iscoe, P. Ney and E. Nummelin, Large deviations of uniformly recurrent Markov additive processes. Adv. Appl. Math.6 (1985) 373–412.  Zbl0602.60034
  11. J.L. Jensen, Saddlepoint approximations. The Clarendon Press Oxford University Press, New York (1995).  Zbl1274.62008
  12. V. Kargin, A large deviation inequality for vector functions on finite reversible Markov chains. Ann. Appl. Probab.17 (2007) 1202–1221.  Zbl1131.60067
  13. K. Knopp, Theory of Functions, Part I. Elements of the General Theory of Analytic Functions. Dover Publications, New York (1945).  
  14. I. Kontoyiannis and S.P. Meyn, Spectral theory and limit theorems for geometrically ergodic Markov processes. Ann. Appl. Probab.13 (2003) 304–362.  Zbl1016.60066
  15. C.A. León and F. Perron, Optimal Hoeffding bounds for discrete reversible Markov chains. Ann. Appl. Probab.14 (2004) 958–970.  Zbl1056.60070
  16. M.E. Lladser, M.D. Betterton and R. Knight, Multiple pattern matching: a Markov chain approach. J. Math. Biol.56 (2008) 51–92.  Zbl1147.65005
  17. B. Mann, Berry-Esseen Central Limit Theorems For Markov Chains. Ph.D. thesis, Harvard University, 1996.  
  18. H.D. Miller, A convexivity property in the theory of random variables defined on a finite Markov chain. Ann. Math. Statist.32 (1961) 1260–1270.  Zbl0108.15101
  19. P. Ney, Dominating points and the asymptotics of large deviations for random walk on Rd. Ann. Probab.11 (1983) 158–167.  Zbl0503.60035
  20. P. Ney and E. Nummelin, Markov additive processes, Part I. Eigenvalue properties and limit theorems. Ann. Probab.15 (1987) 561–592.  Zbl0625.60027
  21. P. Nicodème, B. Salvy and P. Flajolet, Motif statistics. In Algorithms – ESA '99, Prague. Lect. Notes Comput. Sci.1643. Springer, Berlin (1999), pp 194–211.  Zbl0944.92013
  22. G. Nuel, Numerical solutins for Patterns Statistics on Markov chains. Stat. Appl. Genet. Mol. Biol.5 (2006).  
  23. G. Nuel, Pattern Markov chains: optimal Markov chain embedding through deterministic finite automata. J. Appl. Probab.45 (2008) 226–243.  Zbl1142.65010
  24. R Development Core Team, R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2003). ISBN 3-900051-00-3.  
  25. M. Régnier, A unified approach to word occurrence probabilities. Discrete Appl. Math.104 (2000) 259–280, Combinatorial molecular biology.  Zbl0987.92017
  26. M. Régnier and A. Denise, Rare events and conditional events on random strings. Discrete Math. Theor. Comput. Sci.6 (2004) 191–213 (electronic).  Zbl1059.05008
  27. M. Régnier and W. Szpankowski, On pattern frequency occurrences in a Markovian sequence. Algorithmica22 (1998) 631–649.  Zbl0918.68108
  28. G. Reinert, S. Schbath and M.S. Waterman, Applied Combinatorics on Words. In Encyclopedia of Mathematics and its Applications, Vol. 105, chap. Statistics on Words with Applications to Biological Sequences. Cambridge University Press (2005).  
  29. S. Robin and J.-J. Daudin, Exact distribution of word occurrences in a random sequence of letters. J. Appl. Probab.36 (1999) 179–193.  Zbl0945.60008
  30. E. Roquain and S. Schbath, Improved compound Poisson approximation for the number of occurrences of any rare word family in a stationary Markov chain. Adv. Appl. Probab.39 (2007) 128–140.  Zbl1109.62012
  31. S. Schbath, Compound Poisson approximation of word counts in DNA sequences. ESAIM: PS1 (1997) 1–16.  Zbl0869.60067
  32. D. Serre, Matrices, volume 216 of Graduate Texts Math.. Springer-Verlag, New York (2002). Theory and applications, translated from the 2001 French original.  
  33. V.T. Stefanov, S. Robin and S. Schbath, Waiting times for clumps of patterns and for structured motifs in random sequences. Discrete Appl. Math.155 (2007) 868–880.  Zbl1112.60055

NotesEmbed ?

top

You must be logged in to post comments.