Discretization of time series data

Abstract

An increasing number of algorithms for biochemical network inference from experimental data require discrete data as input. For example, dynamic Bayesian network methods and methods that use the framework of finite dynamical systems, such as Boolean networks, all take discrete input. Experimental data, however, are typically continuous and represented by computer floating point numbers. The translation from continuous to discrete data is crucial in preserving the variable dependencies and thus has a significant impact on the performance of the network inference algorithms. We compare the performance of two such algorithms that use discrete data using several different discretization algorithms. One of the inference methods uses a dynamic Bayesian network framework, the other-a time-and state-discrete dynamical system framework. The discretization algorithms are quantile, interval discretization, and a new algorithm introduced in this article, SSD. SSD is especially designed for short time series data and is capable of determining the optimal number of discretization states. The experiments show that both inference methods perform better with SSD than with the other methods. In addition, SSD is demonstrated to preserve the dynamic features of the time series, as well as to be robust to noise in the experimental data. A C++ implementation of SSD is available from the authors at http://polymath.vbi.vt.edu/discretization .

FIG. 1.

Dentrogram representing the SLC algorithm applied to the data of Example 3.2. The column on the right gives the corresponding Shannon's entropy increasing at each consecutive level.

FIG. 2.

The complete weighted graph constructed from vector entries 1, 2, 7, 9, 10, and 11. Only the edge weights of the outer edges are given.

FIG. 3.

(A) Dependency graph of the A-Biochem-generated artificial gene network on five genes G_i. (B) Dependency graph of the reverse-engineered system.

FIG. 4.

(A) Wild-type time series generated by solving numerically the ODE system. (B) Corresponding discrete point time series.

FIG. 5.

Network 1: 10 genes and three environmental perturbations. In this network, the three environmental perturbations P1, P2, and P3 directly affect the expression rate of genes G1, G2, and G5, respectively.

FIG. 6.

Three in silico networks. The first network consists of 10 genes and the second and third networks consist of 5 genes. In these three networks, the interactions between genes are phenomenological and represent the result of the effect of transcription and translation on the regulation of the genes in the network.