Vectorization of dynamic-time-warping computation using data reshaping

• US 20090150313A1
• Filed: 12/06/2007
• Published: 06/11/2009
• Est. Priority Date: 12/06/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Markman, Dmitry, Heilper, Andre
• Application Number:
  US11/923,675
• Publication Number:
  US 20090150313A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search

Abstract

A method for comparing data sequences includes accepting first and second data sequences of data elements. A distance matrix is computed. The matrix includes rows and columns of matrix elements, describing distances between the data elements of the first sequence and the data elements of the second data sequence. The distance matrix is reshaped by applying successive, incremental shifts to the rows or columns so as to produce a reshaped matrix. A best-score path through the reshaped matrix is calculated using vector operations, so as to quantify a similarity between the first and second data sequences. Due to vectorization, a significant increase in computation speed is achieved in both software and hardware implementations.

Claims

1-8. -8. (canceled)

9. Apparatus for comparing data sequences, comprising:

an input device, which is coupled to accept first and second data sequences comprising data elements; and

a processor, which is arranged to compute a distance matrix comprising rows and columns of matrix elements that describe distances between the data elements of the first sequence and the data elements of the second data sequence, to reshape the distance matrix by applying successive, incremental shifts to the rows or columns so as to produce a reshaped matrix, and to calculate a best-score path through the reshaped matrix using vector operations, so as to quantify a similarity between the first and second data sequences.

10. The apparatus according to claim 9, wherein the first and second data sequences comprise DNA chains, wherein the data elements represent types of DNA nucleotides, and wherein the processor is arranged to evaluate a match between the DNA chains.

11. The apparatus according to claim 9, wherein the processor is arranged to apply a Dynamic Time Warping (DTW) process so as to calculate the best-score path.

12. The apparatus according to claim 9, wherein the distance matrix possesses a reverse-diagonal data dependency, and wherein the processor is arranged to reshape the matrix so as to eliminate the reverse-diagonal data dependency.

13. The apparatus according to claim 9, wherein the processor is arranged to perform calculations on the rows or the columns of the reshaped matrix, wherein the calculations on the rows or the columns are respectively based, as a result of reshaping the distance matrix, on a prior calculation of only preceding rows or columns of the reshaped matrix.

14. The apparatus according to claim 9, wherein the processor comprises a vector-processor.

15. A computer software product for comparing data sequences, the product comprising a computer-readable medium, in which program instructions are stored, which instructions, when read by the computer, cause the computer to accept first and second data sequences comprising data elements, to compute a distance matrix comprising rows and columns of matrix elements that describe distances between the data elements of the first sequence and the data elements of the second data sequence, to reshape the distance matrix by applying successive, incremental shifts to the rows or columns so as to produce a reshaped matrix, to calculate a best-score path through the reshaped matrix using vector operations, so as to quantify a similarity between the first and second data sequences.

16. The product according to claim 15, wherein the first and second data sequences comprise DNA chains, wherein the data elements represent types of DNA nucleotides, and wherein the instructions cause the computer to evaluate a match between the DNA chains.

17. The product according to claim 15, wherein the instructions cause the computer to apply a Dynamic Time Warping (DTW) process so as to calculate the best-score path.

18. The product according to claim 15, wherein the distance matrix possesses a reverse-diagonal data dependency, and wherein the instructions cause the computer to reshape the distance matrix so as to eliminate the reverse-diagonal data dependency.

19. The product according to claim 15, wherein the instructions cause the computer to perform calculations on the rows or the columns of the reshaped matrix, wherein the calculations on the rows or the columns are respectively based, as a result of reshaping the distance matrix, on a prior calculation of only preceding rows or columns of the reshaped matrix.

20. The product according to claim 15, wherein the instructions cause the computer to apply a vector-processor in processing the data sequences.