  We describe a new algorithm and R package for peak detection in genomic data
sets using constrained changepoint algorithms. These detect changes from
background to peak regions by imposing the constraint that the mean should
alternately increase then decrease. An existing algorithm for this problem
exists, and gives state-of-the-art accuracy results, but it is computationally
expensive when the number of changes is large. We propose the GFPOP algorithm
that jointly estimates the number of peaks and their locations by minimizing a
cost function which consists of a data fitting term and a penalty for each
changepoint. Empirically this algorithm has a cost that is $O(N \log(N))$ for
analysing data of length $N$. We also propose a sequential search algorithm
that finds the best solution with $K$ segments in $O(\log(K)N \log(N))$ time,
which is much faster than the previous $O(KN \log(N))$ algorithm. We show that
our disk-based implementation in the PeakSegDisk R package can be used to
quickly compute constrained optimal models with many changepoints, which are
needed to analyze typical genomic data sets that have tens of millions of
observations.
