dynamic time warping ( dtw ) , described in the text of kruskal and liberman ( 1 ) , is an algorithm to compute the optimal alignment of numerical sequences .
using dynamic programming ( 2 ) , dtw was first introduced by vintsyuk ( 3 ) and applied in speech recognition by sakoe and chiba ( 4 ) .
while most applications of dtw are in the area of speech recognition ( 5 ) , dtw has recently been applied to the fields of data mining ( 68 ) , medicine ( electrocardiograms ) ( 9 ) and bioinformatics ( 10,11 ) . in bioinformatics , aach and church ( 10 )
implement some variants of classical dtw along with interpolative dtw , investigated robustness and statistical significance of time warping alignments , and analyzed published cell - cycle gene expression data of saccharomyces cerevisiae .
very recently , criel and tsiporkova ( 11 ) describe their publicly available java program , gent  warper , which implements classical time warping and provides a user - friendly graphical user interface suitable for biological investigation of gene expression data .
dtw is a variant of sequence alignment for numerical sequences , as opposed to sequences of amino acids or nucleotides , where the analogue of a linear gap penalty in sequence alignment is played by time expansion or contraction . despite the similarity with sequence alignment
let a = a1 ,    ,  an be numerical values measured at times 0 ,  , 2 ,    ,  ( n  1) , and let b = b1 ,    ,  bm be numerical values measured at times 0 ,  , 2 ,    ,  ( m  1). for each 1 
i  n , 1  j  m , define 
 di , j = min{di1,j1++2aibjdi1,j+2aibjdi , j1+2aibj 
 with this notation , ( classical ) time warping distance between a and b is defined to be dn , m ; the optimal alignment is obtained using tracebacks . clearly
the computation of time warping distance can be performed in quadratic time using quadratic memory resources . using the method of hirschberg
( 12 ) , it is possible to reduce memory resources to a linear factor ; however , given the current number of time points in gene expression data , this additional complication is unwarranted . as in sequence alignment ,
time warping can alternatively be viewed as a method to determine the minimum cost path , which proceeds in a left - to - right and bottom - to - top manner from the point ( 1,1 ) to the point ( n , m ) , such that each path edge is one step in the horizontal , vertical or diagonal direction .
see figure 1 for an example of the optimal path graph between two small numerical sequences , and notice that unlike the case for sequence alignment , dtw is not symmetric 
time warping distance between sequences a , b is not necessarily equal to that of the reversal of a with the reversal of b. a sakoe 
chiba band ( 4 ) is used to define a warping window that constrains the path close to the diagonal , restricting the portion of the matrix that the path is allowed to visit to 
 ijnm<pn 
 given a parameter p between 0 and 1 . in ( 13 ) ,
clote and straubhaar describe a new variant of time warping , which is proved to be symmetric in the sense just described .
the paper ( 13 ) includes a quadratic time computation of the boltzmann forward partition function fzi , j =   exp(di , j / rt ) , where the sum is over all time warpings of a1 ,    ,  ai with b1 ,    ,  bj , di , j is the ( new , symmetric and modified ) time warping distance between a1 ,    ,  ai and b1 ,    ,  bj , r is the universal gas constant and t is absolute temperature . in the context of time
symmetry allows the unambiguous computation of the backward partition function bzij , where the sum is over all time warpings of ai ,    ,  an with bj ,    ,  bm .
together we obtain the boltzmann pair probability pr[ai , bj ] that ai is aligned with bj , defined by 
 pr[ai , bj]=fzi1,j1exp((+)aibj2rt)bzi+1,j+1fz1,n 
 this expression is a slight simplification  see ( 13 ) for more details .
boltzmann pair probabilities indicate possible biological significance for certain alignment positions in time warping of gene expression data .
for instance , it could be that the alignment of expression values in cell - cycle phases g1 and s is more significant than those in phases g2 and m. indeed , in the context of sequence alignment , ( 14 ) has shown that boltzmann pair probabilities do indicate biological significance of certain positions in sequence alignments ; see also ( 15 ) .
although currently available gene expression time series data include only a small number of time points , future datasets are certain to include more time points , as costs decrease and accuracy is improved .
figure 2 displays a screen shot of the btw web server which computes the optimal symmetric time warping distance between two numerical sequences , and allows the user to obtain the boltzmann pair probabilities pr[ai , bj ] that ai and bj are aligned .
the btw web server currently allows a user to upload two tab - separated text files , a and b , each containing gene expression time series data .
the first line is required to contain the time points , measured in minutes  for instance , file a might contain values t1 ,    ,  tn equal to 0 , 10 , 20 ,    ,  160 as in cho 's expression data for s.cerevisiae ( 16 ) , and file b might contain values t1 ,    ,  tm equal to 0 , 120 , 240 ,    ,  1440 as in cho 's expression data for homo sapiens ( 17 ) .
time intervals need not be constant ; for instance , a time series might consist of values measured at times 0 , 20 , 40 , 80 , 160 .
d , set by default to 1 , in order to allow scaling between  and  ; i.e.  = c   resp .
 = d  . for instance , since approximately two cell - cycles for s.cerevisiae occur in 160 min for the data of ( 16 ) with intervals of 10 min , and since approximately two cell - cycles for h.sapiens occur in 1440 min ( 24 h ) or the data of ( 17 ) with intervals of 120 min , there are 16 non - zero time points for yeast compared with 12 time points for human
. hence one could take c = 1/10 , d = 4/31/120 or alternatively c = 1 , d = 4/31/12 .
b is required to contain normalized log expression values , with no missing data  the user is assumed to complete missing data by using interpolation , splines ( 18 ) or another method .
the btw web server computes the ( symmetric ) time warping distance between each gene of a and each gene of b , where due to time and space constraints , file a resp .
time warping scores for gene pairs are sorted by increasing distance , or available in lexicographic order of gene pairs . for up to 100 user - specified gene pairs ,
boltzmann pair probabilities are available in both text and graphical format , the latter depicted in figure 3 . since clote and straubhaar ( 13 ) proved the symmetry of one of the four variants of dtw in ( 10 ) , the btw web server allows the user to choose either the algorithm of clote or that of aach . [ after seeing a preprint of ( 13 ) aach conjectured that his dtw program genewarp with flag -a 2 is symmetric .
current hardware supporting the btw web server consists of a beowulf - style cluster comprising 6 dell 1650 , 2  1300 mhz pentium iii , 2 gb ram with 4 apple xserve , 2  1333 mhz g4 , 2 gb ram and finally 12 dell 1850 , 2  2800 mhz xeon em64 t , 2 gb ram .
pentium iii nodes are running 32-bit centos 4.2 , xeon em64 t nodes are running 64-bit centos 4.2 and g4 nodes are running macos 10.2.8 .
7077 human ( 16,17 ) ] time warping distances between each yeast and each human gene is depicted in figure 4a .
this figure suggests that time warping distances could follow an extreme value distribution , known by ( 19 ) to be the distribution of blast hits . from the method of moments
, we fit the histogram of figure 4a to an extreme value distribution with cumulative distribution function cdf(x)=ee(x93.87)/12.20 .
this would allow us to compute a p - value for significance of human genes , whose time warping distance with a given yeast gene is less than a fixed threshold .
path graph for classic dtw for ( toy ) sequences a = ( a1,a2,a3,a4,a5 ) = ( 2,1,3,6,8 ) and ( b1,b2,b3,b4 ) = ( 2,2,7,8 ) of unequal length . here
 bj| is euclidean distance , and time expansion / compression intervals are  = 10 = . ( left ) optimal path graph with distance 25.0 for aligning a with b. ( right ) optimal path graph with distance 20.0 for aligning the reversal of a with the reversal of b. note that classic dtw is not symmetric , unlike the situation for sequence alignment algorithm of needleman and wunsch ( 20 ) .
output from btw : top ranking time warping distance for genes from file a with those from file b. small time warping distance could indicate a related biological function , as determined in the gene ontology . for each gene pair ,
the user can retrieve a graphical description of the optimal alignment , as well as text and graphical output for the boltzmann pair probabilities pr[ai , bj ] .
optimal alignment and pair probabilities graphical output is shown in figure 3 . optimal alignment ( upper panel ) and
boltzmann pair probabilities ( lower panel ) for alignment positions in optimal time warping between yeast gene ygl116w ( 17 time points ) and human gene u05340 ( 13 time points ) .
boltzmann probabilities are computed with k = 1 and for the values 0.5 , 1.0 and 2.0 of t. with increasing values of t , the boltzmann probability values decrease ; this enhances the depiction of presumed biological significance of aligned positions in this optimal time warping .
( a ) histogram of ( symmetric ) time warping distances between each yeast and human gene , using gene expression data from cho et al .
( 16,17 ) ; mean  = 100.91 , sd  = 15.647 , max = 221.74 , min = 19.99 .
( b ) histogram of ( symmetric ) time warping distances between each yeast and human gene from a sample of 188 homologous pairs of yeast / human genes ; mean  = 101.73 , sd  = 17.75 , max = 167.41 , min = 48.03 .
 dynamic time warping ( dtw ) is a well - known quadratic time algorithm to determine the smallest distance and optimal alignment between two numerical sequences , possibly of different length . 
 originally developed for speech recognition , this method has been used in data mining , medicine and bioinformatics . for gene expression time series data , time warping distance is arguably a more flexible tool to determine genes having similar temporal expression , hence possibly related biological function , than either euclidean distance or correlation coefficient  especially since time warping accommodates sequences of different length . 
 the btw web server allows a user to upload two tab - separated text files a , b of gene expression data , each possibly having a different number of time intervals of different durations . 
 btw then computes time warping distance between each gene of a with each gene of b , using a recently developed symmetric algorithm which additionally computes the boltzmann partition function and outputs boltzmann pair probabilities . 
 the boltzmann pair probabilities , not available with any other existent software , suggest possible biological significance of certain positions in an optimal time warping alignment . 
 availability : . 
INTRODUCTION
WEB SERVER
DISCUSSION
Figures and Tables