×

Local alignment of Markov chains. (English) Zbl 1113.60054

This paper investigates local alignments without gaps of two independent Markov chains from a finite alphabet. Sufficient conditions are established for the number of essentially different local alignments with a score exceeding a high threshold to be asymptotically Poisson distributed. From the Poisson approximation a Gumbel approximation of the maximal local alignment score is obtained. The results extend known results for independent sequences of i.i.d random variables.

MSC:

60G70 Extreme value theory; extremal stochastic processes
60F10 Large deviations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alsmeyer, G. (2000). The ladder variables of a Markov random walk. Probab. Math. Statist. 20 151–168. · Zbl 0988.60069
[2] Arratia, R., Goldstein, L. and Gordon, L. (1989). Two moments suffice for Poisson approximations: The Chen–Stein method. Ann. Probab. 17 9–25. · Zbl 0675.60017 · doi:10.1214/aop/1176991491
[3] Asmussen, S. (2003). Applied Probability and Queues , 2nd ed. Springer, New York. · Zbl 1029.60001 · doi:10.1007/b97236
[4] Bundschuh, R. (2000). An analytic approach to significance assessment in local sequence alignment with gaps. In RECOMB 00 : Proceedings of the Fourth Annual International Conference on Computational Molecular Biology 86–95. ACM Press, New York.
[5] Çinlar, E. (1975). Introduction to Stochastic Processes . Prentice–Hall Inc., Englewood Cliffs, NJ.
[6] Dembo, A., Karlin, S. and Zeitouni, O. (1994). Limit distribution of maximal non-aligned two-sequence segmental score. Ann. Probab. 22 2022–2039. · Zbl 0836.60023 · doi:10.1214/aop/1176988493
[7] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Springer, New York. · Zbl 0896.60013
[8] den Hollander, F. (2000). Large Deviations . Amer. Math. Soc., Providence, RI. · Zbl 0949.60001
[9] Doukhan, P. (1994). Mixing . Springer, New York.
[10] Grossmann, S. and Yakir, B. (2004). Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments. Bernoulli 10 829–845. · Zbl 1068.60037 · doi:10.3150/bj/1099579157
[11] Karlin, S. and Dembo, A. (1992). Limit distributions of maximal segmental score among Markov-dependent partial sums. Adv. in Appl. Probab. 24 113–140. JSTOR: · Zbl 0767.60017 · doi:10.2307/1427732
[12] Kingman, J. F. C. (1961). A convexity property of positive matrices. Quart. J. Math. Oxford Ser. (2) 12 283–284. · Zbl 0101.25302 · doi:10.1093/qmath/12.1.283
[13] Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces . Springer, Berlin. · Zbl 0748.60004
[14] Mercier, S. (2001). Exact distribution for the local score of one i.i.d. random sequence. J. Comput. Biol. 8 373–380. Available at http://www.liebertonline.com/doi/abs/10.1089/106652701752236197.
[15] Mercier, S. and Hassenforder, C. (2003). Distribution exacte du score local, cas markovien. C. R. Math. Acad. Sci. Paris 336 863–868. · Zbl 1039.60066 · doi:10.1016/S1631-073X(03)00208-5
[16] O’Cinneide, C. (2000). Markov additive processes and Perron–Frobenius eigenvalue inequalities. Ann. Probab. 28 1230–1258. · Zbl 1025.15027 · doi:10.1214/aop/1019160333
[17] Siegmund, D. and Yakir, B. (2000). Approximate p -values for local sequence alignments. Ann. Statist. 28 657–680. · Zbl 1105.62377 · doi:10.1214/aos/1015951993
[18] Siegmund, D. and Yakir, B. (2003). Correction: “Approximate p -values for local sequence alignments” [ Ann. Statist. 28 (2000) 657–680 MR2002a:62140]. Ann. Statist. 31 1027–1031. · Zbl 1105.62377
[19] Steele, J. M. (1997). Probability Theory and Combinatorial Optimization . SIAM, Philadelphia. · Zbl 0916.90233
[20] Takahata, H. (1981). \(L_\infty\)-bound for asymptotic normality of weakly dependent summands using Stein’s result. Ann. Probab. 9 676–683. · Zbl 0465.60033 · doi:10.1214/aop/1176994375
[21] Waterman, M. S., ed. (1995). Introduction to Computational Biology . Chapman and Hall/CRC, Boca Raton, FL. · Zbl 0831.92011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.