A log-linear time algorithm for constrained changepoint detection
From MaRDI portal
Publication:150266
DOI10.48550/ARXIV.1703.03352arXiv1703.03352MaRDI QIDQ150266FDOQ150266
Authors: Toby Dylan Hocking, Guillem Rigaill, Paul Fearnhead, Guillaume Bourque 
Publication date: 9 March 2017
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
Cited In (1)
This page was built for publication: A log-linear time algorithm for constrained changepoint detection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q150266)
