Patent Document ID: 7788279
Application ID: 11558366

Base Claim:
1. A method of aligning elements in a query sequence and to elements in a target sequence, wherein the elements represent pitches with durations of an audio sequence, the method including: representing potential element-to-element partial alignments between query and target sequences derived from audio sequences in an m-by-n cell data structure, such that cell (i,j) represents potential alignment of query element i with target element j; forward propagating pitches and durations from cells included in partial alignments, for scoring purposes, into cells chosen to have a deleted element; processing the cells in the data structure in an order that processes a particular cell after antecedent cells have been processed and scored; choosing, cell-by-cell, whether element pair (i,j) of the query and target sequences should belong to a partial alignment or whether one element in the element pair (i,j) should be deleted, including considering at least potential transitions to (i,j) from antecedent cell (i−1,j−1), representing potential inclusion of the element pair (i,j) in the partial alignment, from antecedent cell (i−1,j), representing potential deletion of an element from the query sequence, and from antecedent cell (i,j−1), representing potential deletion of an element from the target sequence; scoring cumulative scores of the potential transitions, wherein scoring a cumulative score of the potential inclusion of the element pair (i,j) in the partial alignment includes adding a match score to a cumulative score of the previously scored cell (i−1,j−1), wherein calculating the match score includes using the pitches or propagated pitches of cell (i−1,j−1) and the pitches of cell (i,j) to calculate query pitch and target pitch differences, respectively, and using the durations or propagated durations of cell (i−1,j−1) the durations of cell (i,j) to calculate query duration and target duration ratios, respectively, then comparing the query and target pitch differences and comparing the query and target duration ratios to determine the match score; scoring cumulative scores of the potential deletions from the query or target sequence includes subtracting a deletion penalty from the previously scored antecedent cell, either cell (i−1,j) for deletion of element i from the query sequence or cell (i,j−1) for deletion of element j from the target sequence; selecting among the cumulative scores of the potential transitions and recording at least one selected transition and the cumulative score of the selected transition; and backtracking through the cumulative scores and the selected transitions, beginning with one or more high scores at one end of the query or target sequences to an opposite end and determining a total alignment, taking into account deletions, between the elements of the query and target sequences, and reporting for further processing at least the total alignment between the elements of the query and target sequences.

---

Claim 7:
7. The method of claim 1 , further including representing the pitches as notes within octaves, such that a notes in different octaves can have a pitch difference of zero.