A log-linear time algorithm for constrained changepoint detection

Toby Dylan Hocking, Guillem Rigaill, Paul Fearnhead, Guillaume Bourque
3/9/2017
stat.COq-bio.GNstat.ML

Official code: tdhock/PeakSegOptimal (6 stars, last commit 2026-03-27).

Abstract

Changepoint detection is a central problem in time series and genomic data. For some applications, it is natural to impose constraints on the directions of changes. One example is ChIP-seq data, for which adding an up-down constraint improves peak detection accuracy, but makes the optimization problem more complicated. We show how a recently proposed functional pruning technique can be adapted to solve such constrained changepoint detection problems. This leads to a new algorithm which can solve problems with arbitrary affine constraints on adjacent segment means, and which has empirical time complexity that is log-linear in the amount of data. This algorithm achieves state-of-the-art accuracy in a benchmark of several genomic data sets, and is orders of magnitude faster than existing algorithms that have similar accuracy. Our implementation is available as the PeakSegPDPA function in the coseg R package, https://github.com/tdhock/coseg

View on arXivView PDF

Code Implementations(1)

tdhock/PeakSegOptimalOfficial100%

Constrained Optimal Segmentation

623C, RJun 10, 20166 months ago

Similar Papers

Generalized Functional Pruning Optimal Partitioning (GFPOP) for Constrained Changepoint Detection in Genomic Data

85% match2018

Penalty Learning for Optimal Partitioning using Multilayer Perceptron

78% match1 repo2024

Greedy online change point detection

78% match2023

Selective review of offline change point detection methods

76% match1 repo2.1k2018

Neural Network-Based Change Point Detection for Large-Scale Time-Evolving Data

76% match2025

Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions

76% match2023

Cite this paper

@article{hocking2017loglinear,
  title  = {A log-linear time algorithm for constrained changepoint detection},
  author = {Toby Dylan Hocking and Guillem Rigaill and Paul Fearnhead and Guillaume Bourque},
  year   = {2017},
  eprint = {1703.03352},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1703.03352}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1703.03352.svg)](https://codeofpaper.com/paper/1703.03352)

Discussion