×

Testing statistical hypothesis on random trees and applications to the protein classification problem. (English) Zbl 1166.62079

Summary: Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by D. Balding et al. [Limit theorems for sequences of random trees. DOI: 10.1007/s11749-008-0092-z (2008)]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of the Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

MSC:

62P10 Applications of statistics to biology and medical sciences; meta analysis
92C40 Biochemistry, molecular biology
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62G10 Nonparametric hypothesis testing
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
05C90 Applications of graph theory
05C80 Random graphs (graph-theoretic aspects)

Software:

Pfam
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Balding, D., Ferrari, P., Fraiman, R. and Sued, M. (2008). Limit theorems for sequences of random trees. Test (online). DOI: 10.1007/s11749-008-0092-z. · Zbl 1203.60038 · doi:10.1007/s11749-008-0092-z
[2] Banks, D. and Constantine, G. (1998). Metric models for random graphs. J. Classification 15 199-223. · Zbl 0912.62074 · doi:10.1007/s003579900031
[3] Bejerano, G. (2003). Automata learning and stochastic modeling for biosequence analysis. Ph.D. thesis, Hebrew Univ.
[4] Bejerano, G. (2004). Algorithms for variable length Markov chain modeling. Bioinformatics 20 788-789.
[5] Bejerano, G. and Yona, G. (2001). Variations on probabilistic suffix trees: Statistical modeling and prediction of protein families. Bioinformatics 17 23-43.
[6] Bühlmann, P. and Wyner, A. J. (1999). Variable length Markov chains. Ann. Statist. 27 480-513. · Zbl 0983.62048 · doi:10.1214/aos/1018031204
[7] Csiszár, I. and Talata, Z. (2006). Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Inform. Theory 52 1007-1016. · Zbl 1284.94027 · doi:10.1109/TIT.2005.864431
[8] Finn, R. D., Mistry, J., Schuster-Böckler, B., Griffiths-Jones, S., Hollich, V., Lassmann, T., Moxon, S., Marshall, M., Khanna, A., Durbin, R., Eddy, S. R., Sonnhammer, E. L. L. and Bateman, A. (2006). Pfam: Clans, web tools and services. Nucleic Acids Res. 34 D247-D51.
[9] Galves, A., Galves, C., Garcia, N. and Peixoto, C. (2004). Correlates of rhythm in written texts of Brazilian and European Portuguese. Preprint. Available as Technical Report 08/08, IMECC/UNICAMP.
[10] Galves, A., Maume-Deschamps, V. and Schmitt, B. (2008). Exponential inequalities for VMLC empirical trees. ESAIM Probab. Stat. 12 219-229. · Zbl 1182.62165 · doi:10.1051/ps:2007035
[11] Greig, D., Porteous, B. and Seheult, A. (1989). Exact maximum a posteriori estimation for binary images. J. Roy. Statist. Soc. Ser. B 51 271-279.
[12] Kolmogorov, V. and Zabih, R. (2004). What energy functions can be minimized via graphs cuts? IEEE Trans. Pattern Analysis and Machine Intelligence 26 147-159. · Zbl 1039.68666
[13] Leonardi, F., Matioli, S. R., Armelin, H. A. and Galves, A. (2007). Detecting phylogenetic relations out from sparse context trees. Available at
[14] Manly, B. F. J. (2007). Randomization, Bootstrap and Monte Carlo Methods in Biology , 3rd ed. Chapman & Hall/CRC, New York. · Zbl 1269.62076
[15] Rissanen, J. (1983). A universal data compression system. IEEE Trans. Inform. Theory 29 656-664. · Zbl 0521.94010 · doi:10.1109/TIT.1983.1056741
[16] Ron, D., Singer, Y. and Tishby, N. (1996). The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning 25 117-149. · Zbl 0869.68066 · doi:10.1007/BF00114008
[17] Stein, L. (2001). Genome annotation: From sequence to biology. Nat. Rev. Genet. 2 493-505.
[18] Wang, H., and Marron, J. S. (2007). Object oriented data analysis: Sets of trees. Ann. Statist. 35 1849-1873. · Zbl 1126.62002 · doi:10.1214/009053607000000217
[19] Wong, K. M., Suchard, M. A. and Huelsenbeck, J. P. (2008). Alignment uncertainty and genomic analysis. Science 319 473-476. · Zbl 1226.92028 · doi:10.1126/science.1151532
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.