Fast multisegment alignments for temporal expression profiles.
We present two heuristics for speeding up a time series alignment algorithm that is related to dynamic time warping (DTW). In previous work, we developed our multisegment alignment algorithm to answer similarity queries for toxicogenomic time-series data. Our multisegment algorithm returns more accurate alignments than DTW at the cost of time complexity; the multisegment algorithm is O(n(5)) whereas DTW is O(n(2)). The first heuristic we present speeds up our algorithm by a constant factor by restricting alignments to a cone shape in alignment space. The second heuristic restricts the alignments considered to those near one returned by a DTW-like method. This heuristic adjusts the time complexity to O(n(3)). Importantly, neither heuristic results in a loss in accuracy.
Smith
Adam A
AA
Department of Computer Sciences, University of Wisconsin, Madison, Wisconsin 53706, USA. aasmith@cs.wisc.edu
Craven
Mark
M
D000465:Algorithms; D003198:Computer Simulation; D020869:Gene Expression Profiling / Q000379:methods*; D008954:Models, Biological; D040081:Protein Array Analysis / Q000379:methods*; D020543:Proteome / Q000378:metabolism*
D020543:Proteome