Fast multisegment alignments for temporal expression profilesAdam A. Smith*, Mark Craven Departments of Computer Sciences and Biostatistics & Medical Informatics, University of Wisconsin, Madison, Wisconsin 53706, USA. aasmith@cs.wisc.edu Proc LSS Comput Syst Bioinform Conf. August, 2008. Vol. 7, p. 315-326. Full-Text PDF *To whom correspondence should be addressed. |
![]() |
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. |
|
[ CSB2008 Conference Home Page ] .... [ CSB2008 Online Proceedings ] .... [ Life Sciences Society Home Page ] |