R package dpseg: piecewise linear segmentation by a simple dynamic programing algorithm

authors: "Rainer Machne, Peter F. Stadler"

This package performs piecewise linear segmentation of ordered data by a dynamic programing algorithm, provided via the function dpseg. It was developed for time series data, eg. growth curves, and for genome-wide read-count data from next generation sequencing.

The package and its documentation are also intended to serve as a tutorial on dynamic programing and the segmentation problem. A movie function visualizes the progress of the algorithm through the data.

Moreover, the package features generic implementations of dynamic programing routines, where new segmentation criteria ("scoring functions") can be tested in base R and efficient versions implemented in Rcpp.

Documentation

See the package vignette (vignette("dpseg")) for details.

Installation

Install package from within R via cran:

install.packages("dpseg")

Developtment Version

library(devtools)
install_gitlab("raim/dpseg")

Basic Usage

library(dpseg)
# get example data `oddata` - bacterial growth measured as optical density OD
x <- oddata$Time
y <- log(oddata[,"A2"]) # note: exponential growth -> log(y) is linear
segs <- dpseg(x=x, y=y, jumps=FALSE, P=0.0004)
## inspect resulting segments
print(segs)
## plot results
plot(segs)
## use predict method
lines(predict(segs),lty=2, lwd=3, col="yellow")
## view the algorithm in action
movie(segs)

Theory

Piecewise Linear Segmentation

The problem is to find break-points in 2-dimensional data, eg. timeseries, that split the data into linear segments. This can be formulated as an optimization problem that can be solved by dynamic programing: