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.本文针对疫变设定下单变量序列（univariate sequence）的多变点检测（change-point detection）问题展开研究，该场景下序列的行为会在常见常态与不同疫变状态间交替。这是对经典（单）疫变变点检验问题的非平凡推广。为显式纳入该问题的交替结构，我们提出一种基于模型选择的新颖方法，可同时对变点与交替状态进行统计推断。借鉴轮廓似然（profile likelihood）的思想，我们设计了两阶段交替剪枝动态规划算法，该算法可对模型选择准则进行高效且精确的优化，最坏情况下的计算复杂度为$O(n^2)$。大量数值实验结果表明，相较于经典的通用型多变点检测方法，本文所提方法在变点估计与模型参数估计两方面均提升了精度。我们进一步展示了所提算法在局部聚类信号多重检验中的良好应用前景，并在大规模多重检验、DNA拷贝数变异检测以及海洋学研究中验证了其相较于现有方法的优势。本文补充材料可在线获取。