STATISTICAL TESTS FOR LARGE TREE-STRUCTURED DATA

Abstract

We develop a general statistical framework for the analysis and inference of large tree-structured data, with a focus on developing asymptotic goodness-of-fit tests. We first propose a consistent statistical model for binary trees, from which we develop a class of invariant tests. Using the model for binary trees, we then construct tests for general trees by using the distributional properties of the Continuum Random Tree, which arises as the invariant limit for a broad class of models for tree-structured data based on conditioned Galton-Watson processes. The test statistics for the goodness-of-fit tests are simple to compute and are asymptotically distributed as χ ² and F random variables. We illustrate our methods on an important application of detecting tumour heterogeneity in brain cancer. We use a novel approach with tree-based representations of magnetic resonance images and employ the developed tests to ascertain tumor heterogeneity between two groups of patients.

Keywords: Conditioned Galton-Watson trees; Consistent statistical models; Dyck path; Goodness-of-fit tests.

Figure 1

Left: Binary tree with n = 10 vertices, 9 edges, 5 leaves (v₁, v₂, v₃, v₄, v₅) with a candidate 5-dimensional distribution f₅. Middle: Identical binary tree with labels of vertices permuted; it is required that the distribution is still f₅. Right: Resulting binary tree when leaves v₄ and v₅ are removed from the tree on the left; it is required that the distribution becomes the 3-dimensional f₃, and is invariant to labeling.

Figure 2

A tree on the left and its L-tree on the right corresponding to vertices {v₁, v₂, v₃, v₄}. The L-tree contains the root, the branch points b₁, b₂ and the set of vertices {v₁, v₂, v₃, v₄}. All the vertices chosen are leaves.

Figure 3

(i), (ii), (iii): Construction of binary tree τ(3) with 3 leaves and 2×3-1= 5 edges, 6 vertices (including root) from nonhomogeneous Poisson process model with arrival times t₁, t₂ and t₃. (iv): A binary tree isomorphic to the tree in (iii) where a+b+e=t₁, c=t₃ −t₂ and d=t₂ −t₁.

Figure 4

A tree with root at the bottom and its corresponding Dyck path. The x axis ranges from 0 to twice the sum of lengths of the edges; the Dyck path is constructed by traversing the tree in a depth-first manner at unit speed.

Figure 5

Preprocessing steps starting from a MR image to the computation of total path length of an L-tree constructed from the resulting binary tree.

Figure 6

T2-weighted Brain MR images of segmented tumors (outlined in black) and dendrograms for a patient who experiences (left) a long survival time of 57.8 months and (right) a short survival time of 0.723 months. Dendrograms were constructed from pixels obtained from only the segmented regions.