Alternating Pruned Dynamic Programming for Multiple Epidemic Change-Point Estimation

In this article, we study the problem of multiple change-point detection for a univariate sequence under the epidemic setting, where the behavior of the sequence alternates between a common normal state and different epidemic states. This is a nontrivial generalization of the classical (single) epidemic change-point testing problem. To explicitly incorporate the alternating structure of the problem, we propose a novel model selection based approach for simultaneous inference on both change-points and alternating states. Using the same spirit as profile likelihood, we develop a two-stage alternating pruned dynamic programming algorithm, which conducts efficient and exact optimization of the model selection criteria and has O(n2) as the worst case computational cost. As demonstrated by extensive numerical experiments, compared to classical general-purpose multiple change-point detection procedures, the proposed method improves accuracy for both change-point estimation and model parameter estimation. We further show promising applications of the proposed algorithm to multiple testing with locally clustered signals, and demonstrate its advantages over existing methods in large scale multiple testing, in DNA copy number variation detection, and in oceanographic study. Supplementary material for this article is available online.

本文针对流行病场景下单变量序列的多变点检测问题展开研究，该场景下序列的行为会在通用正常状态与多种不同的流行病态之间交替切换。该问题是经典（单）流行性变点检验问题的非平凡推广。为显式融入该问题的交替结构，我们提出一种新颖的基于模型选择的方法，用于对变点与交替状态开展联合推断。借鉴轮廓似然的核心思想，我们设计了一种两阶段交替剪枝动态规划算法，该算法可对模型选择准则进行高效且精确的优化，最坏情形下的计算复杂度为O(n²)。通过大量数值实验验证，相较于经典的通用型多变点检测方法，所提方法在变点估计与模型参数估计两方面均提升了精度。我们进一步证明了所提算法在带有局部聚类信号的多重检验中的良好应用前景，并通过大规模多重检验、DNA拷贝数变异检测以及海洋学研究三类场景，验证了其相较于现有方法的优势。本文的补充材料可在线获取。