Testing statistical hypothesis on random trees and applications to the protein classification problem

DOI10.1214/08-AOAS218zbMATH Open1166.62079arXivmath/0603378WikidataQ105584241 ScholiaQ105584241MaRDI QIDQ2270660FDOQ2270660

Ana Georgina Flesia, Sebastian P. Grynberg, Jorge R. Busch, Florencia Leonardi, Pablo A. Ferrari, Ricardo Fraiman

Publication date: 29 July 2009

Published in: The Annals of Applied Statistics (Search for Journal in Brave)

Abstract: 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 Balding et al. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. 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 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.

Full work available at URL: https://arxiv.org/abs/math/0603378

zbMATH Keywords

hypothesis testingrandom treesprotein classificationvariable length Markov chains

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Object oriented data analysis: sets of trees
• Context tree estimation for not necessarily finite memory processes, via BIC and MDL
• A universal data compression system
• Metric models for random graphs
• Exponential inequalities for VLMC empirical trees
• Limit theorems for sequences of random trees
• The power of amnesia: Learning probabilistic automata with variable memory length
• Variable length Markov chains
• Alignment Uncertainty and Genomic Analysis

Cited In (10)

• A note on density estimation for binary sequences
• Context tree selection: a unifying view
• Limit theorems for sequences of random trees
• Overview of object oriented data analysis
• Coupling and perturbation techniques for categorical time series
• Nonparametric statistical inference for the context tree of a stationary ergodic process
• Detecting renewal states in chains of variable length via intrinsic Bayes factors
• Perfect simulation of processes with long memory: A “coupling into and from the past” algorithm
• Variable length memory chains: characterization of stationary probability measures
• A Note on Distinguishing Random Trees Populations

Uses Software

• Pfam

This page was built for publication: Testing statistical hypothesis on random trees and applications to the protein classification problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2270660)