Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graphical time warping
open-in-new
<p>Graphical time warping (GTW) is a framework for jointly aligning multiple pairs of <a href="/facts/Time_series/fSXPR817">time series</a> or sequences. GTW considers both the alignment accuracy of each sequence pair and the similarity among pairs. On contrary, alignment with <a href="/facts/Dynamic_time_warping/guEHSMw4">dynamic time warping</a> (DTW) considers the pairs independently and minimizes only the distance between the two sequences in a given pair. Therefore, GTW generalizes DTW and could achieve a better alignment performance when similarity among pairs is expected. </p><p>One application of GTW is <a href="/facts/Signal_propagation/I3EeyInV">signal propagation</a> analysis in time-lapse <a href="/facts/Microscopy/GpHlElDS">bio-imaging</a> data, where the propagation patterns in adjacent pixels are generally similar. Other applications include <a href="/facts/Image_processing/zenalNCf">signature identification</a>, binocular <a href="/facts/Stereo_images/gVB7Yn2h">stereo</a> depth calculation, and <a href="/facts/Liquid_chromatography%25E2%2580%2593mass_spectrometry/nGlDC6Hw">liquid chromatography–mass spectrometry</a> (LC-MS) profile alignment in <a href="/facts/Proteomics/3aqQ1tFh">proteomics</a> data analysis. Indeed, as long as the data are structured with inter-dependent time series/sequences, they can be analyzed with GTW. </p><p>GTW is able to model constraints or similarities between warping paths by transforming the DTW-equivalent shortest path problem to the <a href="/facts/Maximum_flow_problem/aSal0FGF">maximum flow problem</a> in the <a href="/facts/Dual_graph/1t14hhEF">dual graph</a>, 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), 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. </p>