Graphical time warping

Therefore, GTW generalizes DTW and could achieve a better alignment performance when similarity among pairs is expected.

Other applications include signature identification, binocular stereo depth calculation, and liquid chromatography–mass spectrometry (LC-MS) profile alignment in proteomics data analysis.

GTW is able to model constraints or similarities between warping paths by transforming the DTW-equivalent shortest path problem to the maximum flow problem in the dual graph, which can be solved by most max-flow algorithms.

However, when the data is large, these algorithms become time-consuming and the memory usage is high.

An efficient algorithm, Bidirectional pushing with Linear Component Operations (BILCO),[3] was developed to solve the GTW problem.

It could achieve an average 10-fold improvement in both computational and memory usage compared with the state of art generic maximum flow algorithms in GTW applications.

However, it is not clear how to efficiently solve it in its original form, and a naïve enumeration of the warping paths leads to an NP-hard problem.

This minimization problem can be reformulated into a minimum cut problem on a special graph termed GTW graph, where the minimum cut and the warping paths are equivalent.

As a result, the cut within a GTW subgraph is dual to a warping path in DTW graph, and the profile alignment cost term can be represented by the cut cost within subgraphs.

The infinite capacities of reverse edges are used to guarantee the monotonicity and continuity of warping paths.

Cross edges constrain the similarity of warping paths and contribute to the distance term in the objective function.

Thus, the distance term could be represented by the cut cost in cross edges.

Recalling the fact that the cut within each subgraph corresponds to the warping path of one time-series pair, the minimum cut of GTW graph corresponds to the optimal solution of warping paths in the joint alignment.

In the first stage, the prior structural knowledge among the sequences is utilized to obtain the warping functions.

In the second stage, these warping functions help to jointly align all sequences to a virtual reference, which does not need to be explicitly specified.

ncGTW was applied to LC-MS profile alignment problems in proteomics data and performed better than existing approaches.

[2] Solving the minimum cut problem on GTW graph through traditional maximum flow algorithms would take a long running time and large memory usage due to the large graph size, which limits the usage of GTW.

BILCO algorithm utilizes two important properties of the joint alignment problem and achieves an average 10-fold improvement in both running time and memory usage.

Compared with existing push-relabel-based maximum flow algorithms, BILCO significantly reduces redundant computation.

It is worth noting that such a strategy could be also utilized to help accelerate other push-relabel-based algorithms.

[3] In time-lapse bio-imaging data, signal propagation is a widely observed phenomenon in many cell types.

[4] Studying signal propagation may help uncover the function of these cells in both normal and pathological conditions.

The propagation information could be derived from the warping paths by aligning pixels’ curves with a reference signal.

Due to the low signal-to-noise ratio in bio-imaging data, pairwise alignment methods usually lead to unsatisfactory results.

Considering the spatial correlation of the signals, the similarity of warping paths between adjacent pixels can be utilized in GTW to enhance the alignment performance, which may lead to a more accurate calculation of propagation properties.

In binocular stereo images, alignment technique can be used to extract depth information.

Since the depth of adjacent rows should be similar, GTW could be utilized to enhance the extraction result.

[6] Those feature sequences are correlated, which indicates that when comparing two signatures, the distance measure obtained by pairwise alignment is not optimal.

GTW could take the dependency between features into account and provide a better distance measure.

Structural information between sequences also exists in DNA and amino acids data.

GTW graph construction. The first row demonstrates the process for constructing GTW subgraph from one time-series pair, where the min-cut of GTW subgraph is dual to the shortest path of DTW graph, as well as the optimal warping path. The second row shows the process of adding cross edges between related time-series pairs, where the cross edges are colored green. The area size between adjacent warping paths is proportional to the number of edges cut among cross edges.
The max-flow problem is analogized to pumping water from connected water tanks. Each GTW subgraph is a water tank and the flow is just the water flow. The algorithm iteratively operates Drain operations (drain water from water tank) and Discharge operations (exchange water between adjacent water tanks) until reaching the max-flow.