Single Change-Point Detection via Energy Distance with Application to Genomic Data

1. Problem Statement

The paper addresses the fundamental statistical problem of change-point detection in sequences of independent observations. Specifically, it focuses on:

• Single Change-Point Detection: Identifying a single unknown location $k^*$ in a sequence $X_1, \dots, X_n$ where the underlying distribution shifts from $F_1$ to $F_2$.
• Nonparametric Requirements: The method must be robust to various distributional assumptions (e.g., normal, skew-normal, exponential) and capable of detecting changes not just in location (mean), but also in scale (variance) and shape.
• Global Testing: The challenge of scanning the entire sequence to find the maximum evidence of a change while controlling Type I error rates, particularly when the test statistic is a maximum over dependent split points.
• Application Context: The method is motivated by genomic data analysis (specifically cDNA microarray CGH data), where detecting structural variations (copy number alterations) is critical, and data often exhibit non-normality and complex distributional shifts.

2. Methodology

The proposed approach utilizes Energy Distance, a metric between probability distributions introduced by Székely and Rizzo, integrated into a U-statistic framework.

A. The Test Statistic

The core of the method is a studentized energy scan statistic.

1. Energy Distance Definition: For two samples $X$ and $Y$, the empirical energy distance $E_{n,m}(X,Y)$ is defined using pairwise Euclidean distances with power $\omega=1$:
   $$E_{n,m}(X, Y) = \frac{2}{nm}\sum |X_i - Y_j| - \frac{1}{n^2}\sum |X_i - X_j| - \frac{1}{m^2}\sum |Y_i - Y_j|$$
2. U-Statistic Formulation: The energy distance between two segments split at index $k$ is expressed as a weighted two-sample U-statistic:
   $$E_k = 2U_{XY} - U_{XX} - U_{YY}$$
   where $U_{XY}$, $U_{XX}$, and $U_{YY}$ are U-statistics based on the kernel $h(x,y) = \|x-y\|$.
3. Studentization: To achieve asymptotic normality and stability, the statistic is standardized by an estimator of the degenerate kernel's variance ($s_{\Psi,n}$), derived from a double-centered kernel decomposition.
   $$Z_{n,k} = \frac{k(n-k)}{\sqrt{2}n s_{\Psi,n}} E_k$$
   This studentization ensures the statistic is asymptotically pivotal (converging to a standard normal) under the null hypothesis for interior split points.

B. Global Detection and Calibration

• Scan Statistic: The global test statistic is defined as the maximum absolute value of the studentized statistic over a trimmed interior set $K_\eta$ (to avoid boundary issues):
  $$T_n = \max_{k \in K_\eta} |Z_{n,k}|$$
• Critical Value Calibration: While the asymptotic distribution of $Z_{n,k}$ is $N(0,1)$, the distribution of the maximum $T_n$ is complex. The paper proposes using a permutation test to calibrate critical values. Under the null hypothesis of exchangeability, the data are permuted $L$ times (e.g., $L=999$) to generate an empirical null distribution for $T_n$.
• Multiple Change Points: To handle multiple change points, the single-change procedure is embedded within a Binary Segmentation framework. The algorithm recursively applies the test to segments, splitting at the detected change point until no significant changes remain.
• Handling Dependence: For genomic data with local serial dependence, the paper recommends a circular block permutation strategy to preserve short-range correlation during calibration, preventing false positives due to spatial artifacts.

3. Key Contributions

1. Asymptotic Theory: The paper derives the asymptotic properties of the proposed statistic.
   • Null Hypothesis: Proves that for any fixed interior split $k$, $Z_{n,k} \xrightarrow{d} N(0,1)$.
   • Alternative Hypothesis: Establishes the consistency of the estimated change-point location ($\hat{k}/n \xrightarrow{p} \tau^*$) and shows that the test statistic diverges to infinity under the alternative, ensuring consistency of the global test.
2. Explicit Studentization: Unlike many existing energy-based methods that rely heavily on resampling for standardization, this work provides an explicit analytical studentization that yields an asymptotically pivotal statistic, simplifying implementation and theoretical analysis.
3. Robustness: The method is designed to be distribution-free, capturing changes in location, scale, and shape simultaneously without requiring bandwidth selection (unlike kernel-based methods) or graph construction (unlike graph-based methods).
4. Genomic Application: The method is successfully applied to breast cancer CGH data, demonstrating its ability to detect subtle structural variations that other methods might smooth over.

4. Results

The paper presents extensive simulation studies and a real-data application.

A. Simulation Studies

The method (ED) was compared against Fused Lasso (FL), E-Divisive (ECP), and PELT across Normal, Skew-Normal, and Exponential distributions.

• Type I Error Control: ED demonstrated stable and accurate Type I error control (close to the nominal 0.05 level) across all distributions and sample sizes. In contrast, FL showed inflated Type I errors (liberal) in certain scenarios (e.g., Normal $n=100$), and ECP/PELT were sometimes overly conservative.
• Power Performance:
  • Mean/Scale Shifts: ED consistently outperformed or matched competitors, particularly in detecting small-to-moderate shifts and in boundary regions (where the change point is near the start or end of the sequence).
  • Skewness: Under Skew-Normal and Exponential distributions, ED maintained superior power, whereas other methods struggled with the non-symmetric shapes.
  • Joint Changes: When mean, variance, and shape changed simultaneously, ED showed the most rapid power growth as sample size increased.
• Localization Accuracy: ED provided highly accurate estimates of the change-point location, with scaled absolute errors comparable to the best-performing competitor (ECP) and significantly better than PELT and FL, especially for weak signals.
• Computational Efficiency: ED was computationally efficient, with runtimes comparable to ECP and faster than PELT and FL for the tested sample sizes ($n=200$).

B. Real Data Application (Breast Cancer CGH)

• Dataset: cDNA microarray CGH data from the MDA157 breast cancer cell line (6,691 probes).
• Findings:
  • The ED method detected a richer set of breakpoints compared to Fused Lasso (Tibshirani & Wang, 2008), particularly in chromosomes #3, #6, #8, and #19.
  • It identified subtle distributional shifts that FL tended to oversmooth.
  • It agreed with FL on stable regions (e.g., Chromosome #15) and provided a more parsimonious segmentation than Wild Binary Segmentation (WBS), avoiding over-segmentation caused by local noise.
  • The use of block-permutation calibration successfully mitigated the inflation of false positives due to spatial dependence in the genomic data.

5. Significance

This paper makes a significant contribution to the field of change-point detection by:

• Bridging Theory and Practice: It provides a rigorous theoretical foundation (asymptotic normality and consistency) for an energy-distance-based scan statistic, moving beyond purely algorithmic approaches.
• Enhanced Robustness: By leveraging energy distance, the method offers a unified framework that is robust to non-normality and capable of detecting complex distributional changes (shape/scale) that location-only tests miss.
• Genomic Utility: It offers a powerful, computationally efficient tool for genomic segmentation, capable of identifying biologically relevant copy number variations that are often missed by smoothing-based or parametric methods.
• Future Directions: The work lays the groundwork for extensions to high-dimensional data, sequential monitoring, and multi-change settings with temporal dependence.

In summary, the proposed Energy Distance (ED) scan statistic is a robust, theoretically sound, and practically effective method for detecting single and multiple change points, particularly in complex, non-Gaussian data environments like genomics.