Limits...
Network-based segmentation of biological multivariate time series.

Omranian N, Klie S, Mueller-Roeber B, Nikoloski Z - PLoS ONE (2013)

Bottom Line: As a result, MTS data capture the dynamics of biochemical processes and components whose couplings may involve different scales and exhibit temporal changes.We demonstrate that the problem of partitioning MTS data into [Formula: see text] segments to maximize a distance function, operating on polynomially computable network properties, often used in analysis of biological network, can be efficiently solved.To enable biological interpretation, we also propose a breakpoint-penalty (BP-penalty) formulation for determining MTS segmentation which combines a distance function with the number/length of segments.

View Article: PubMed Central - PubMed

Affiliation: Institute of Biochemistry and Biology, University of Potsdam, Potsdam-Golm, Germany.

ABSTRACT
Molecular phenotyping technologies (e.g., transcriptomics, proteomics, and metabolomics) offer the possibility to simultaneously obtain multivariate time series (MTS) data from different levels of information processing and metabolic conversions in biological systems. As a result, MTS data capture the dynamics of biochemical processes and components whose couplings may involve different scales and exhibit temporal changes. Therefore, it is important to develop methods for determining the time segments in MTS data, which may correspond to critical biochemical events reflected in the coupling of the system's components. Here we provide a novel network-based formalization of the MTS segmentation problem based on temporal dependencies and the covariance structure of the data. We demonstrate that the problem of partitioning MTS data into [Formula: see text] segments to maximize a distance function, operating on polynomially computable network properties, often used in analysis of biological network, can be efficiently solved. To enable biological interpretation, we also propose a breakpoint-penalty (BP-penalty) formulation for determining MTS segmentation which combines a distance function with the number/length of segments. Our empirical analyses of synthetic benchmark data as well as time-resolved transcriptomics data from the metabolic and cell cycles of Saccharomyces cerevisiae demonstrate that the proposed method accurately infers the phases in the temporal compartmentalization of biological processes. In addition, through comparison on the same data sets, we show that the results from the proposed formalization of the MTS segmentation problem match biological knowledge and provide more rigorous statistical support in comparison to the contending state-of-the-art methods.

Show MeSH
Directed acyclic graph (DAG) used as input in Algorithm 1 (Fig. 3).The DAG  for  time points is depicted. It contains  nodes, including the special nodes  and . The label  of each node corresponds to the time points , , and .
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3646968&req=5

pone-0062974-g002: Directed acyclic graph (DAG) used as input in Algorithm 1 (Fig. 3).The DAG for time points is depicted. It contains nodes, including the special nodes and . The label of each node corresponds to the time points , , and .

Mentions: In the following, we show that the MULTSEG problem is polynomially solvable for distance measures which are computable in polynomial time. To this end, we first transform an instance of the problem into an edge-weighted directed acyclic graph (DAG), , as follows: (1) include two special nodes, a source and a target , (2) for each of the values , establish a corresponding node , (3) there is a directed zero-weight edge from to each , where pā€Š=ā€Š1, (4) a directed edge from to is included if , and is assigned a weight of , and, finally, (5) a directed edge of weight is established from node to node if and only if and . An illustration of the resulting graph for is given in Fig. 2. The resulting directed acyclic graph has nodes and edges. Finding the minimum number of weights as the first objective while maximizing the second objective is then equivalent to determining the path of maximum weight with the smallest length (i.e., the minimum number of edges) in .


Network-based segmentation of biological multivariate time series.

Omranian N, Klie S, Mueller-Roeber B, Nikoloski Z - PLoS ONE (2013)

Directed acyclic graph (DAG) used as input in Algorithm 1 (Fig. 3).The DAG  for  time points is depicted. It contains  nodes, including the special nodes  and . The label  of each node corresponds to the time points , , and .
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3646968&req=5

pone-0062974-g002: Directed acyclic graph (DAG) used as input in Algorithm 1 (Fig. 3).The DAG for time points is depicted. It contains nodes, including the special nodes and . The label of each node corresponds to the time points , , and .
Mentions: In the following, we show that the MULTSEG problem is polynomially solvable for distance measures which are computable in polynomial time. To this end, we first transform an instance of the problem into an edge-weighted directed acyclic graph (DAG), , as follows: (1) include two special nodes, a source and a target , (2) for each of the values , establish a corresponding node , (3) there is a directed zero-weight edge from to each , where pā€Š=ā€Š1, (4) a directed edge from to is included if , and is assigned a weight of , and, finally, (5) a directed edge of weight is established from node to node if and only if and . An illustration of the resulting graph for is given in Fig. 2. The resulting directed acyclic graph has nodes and edges. Finding the minimum number of weights as the first objective while maximizing the second objective is then equivalent to determining the path of maximum weight with the smallest length (i.e., the minimum number of edges) in .

Bottom Line: As a result, MTS data capture the dynamics of biochemical processes and components whose couplings may involve different scales and exhibit temporal changes.We demonstrate that the problem of partitioning MTS data into [Formula: see text] segments to maximize a distance function, operating on polynomially computable network properties, often used in analysis of biological network, can be efficiently solved.To enable biological interpretation, we also propose a breakpoint-penalty (BP-penalty) formulation for determining MTS segmentation which combines a distance function with the number/length of segments.

View Article: PubMed Central - PubMed

Affiliation: Institute of Biochemistry and Biology, University of Potsdam, Potsdam-Golm, Germany.

ABSTRACT
Molecular phenotyping technologies (e.g., transcriptomics, proteomics, and metabolomics) offer the possibility to simultaneously obtain multivariate time series (MTS) data from different levels of information processing and metabolic conversions in biological systems. As a result, MTS data capture the dynamics of biochemical processes and components whose couplings may involve different scales and exhibit temporal changes. Therefore, it is important to develop methods for determining the time segments in MTS data, which may correspond to critical biochemical events reflected in the coupling of the system's components. Here we provide a novel network-based formalization of the MTS segmentation problem based on temporal dependencies and the covariance structure of the data. We demonstrate that the problem of partitioning MTS data into [Formula: see text] segments to maximize a distance function, operating on polynomially computable network properties, often used in analysis of biological network, can be efficiently solved. To enable biological interpretation, we also propose a breakpoint-penalty (BP-penalty) formulation for determining MTS segmentation which combines a distance function with the number/length of segments. Our empirical analyses of synthetic benchmark data as well as time-resolved transcriptomics data from the metabolic and cell cycles of Saccharomyces cerevisiae demonstrate that the proposed method accurately infers the phases in the temporal compartmentalization of biological processes. In addition, through comparison on the same data sets, we show that the results from the proposed formalization of the MTS segmentation problem match biological knowledge and provide more rigorous statistical support in comparison to the contending state-of-the-art methods.

Show MeSH