# Melodic Similarity and Applications Using Biologically-Inspired Techniques
## 2 Methods and Tools
### Pairwise Alignment
On the other hand, the local alignment framework, first optimized by [PERSON] and [PERSON] [31], aims to find the highest scoring alignments of partial sequences by tracking back from \(\max(D(i,j))\) instead of \(D(n,m)\), and by forcing all \(D(i,j)\) to be non-negative. Local alignment allows for the identification of substrings (patterns) of high similarity. When affine gaps are not considered, meaningful, high-quality alignments are solely dependent on the knowledge captured by the substitution matrix used [30]: optimal alignments with good scoring matrices will assign high scores to pairs of related sequences, while giving a low alignment score to unrelated sequences. More formally, given the two sequences \(X,Y\) their alignment score \(c(A)\) should represent the relative likelihood that the two sequences are related as opposed to being unrelated (aligned by chance). This is typically modelled by a ratio, denoted as odds ratio:\[\frac{P(X,Y|M)}{P(X,Y|R)} \tag{4}\]  
where \(M\) is a probabilistic model of related sequences and \(R\) is a model generating unrelated sequences. If \(q_{a}\) is the frequency of a symbol \(a\), and both \(X\) and \(Y\) have the same distribution under \(R\), then for the random alignment case aligned pairs happen independently, which translates to:  
\[P(X,Y|R)=P(X|R)P(Y|R)=\prod_{i}q_{x_{i}}\prod_{j}q_{y_{j}} \tag{5}\]  
For the matching case, where aligned pairs happen with a joint probability \(p\), the probability for the alignment is:  
\[P(X,Y|M)=\prod_{i}p_{x_{i}y_{i}} \tag{6}\]  
In order to get an additive scoring system, it is standard practice to get the logarithm of Equation (3), which after substitution becomes:  
\[log\frac{P(X,Y|M)}{P(X,Y|R)}=\sum_{i}log\Big{(}\frac{p_{x_{i}y_{i}}}{q_{x_{i}} q_{y_{i}}}\Big{)} \tag{7}\]  
A substitution matrix can be considered nothing more than a matrix arrangement of the \(log(p_{x_{i}y_{i}}/q_{x_{i}}q_{y_{i}})\) values (scores) of all possible pairwise symbol combinations. Sequence alignment via dynamic programming and its time-series counterpart, Dynamic Time Warping (DTW), have been fundamental tools for many MIR tasks since first being applied in a melody retrieval task by [PERSON] and [PERSON] [32]. Alignment, despite being considered an ill-posed problem for strongly deviating versions of a musical piece [33], has proven to be very useful for identification or classification tasks where strong similarities are present [1; 34] and high scoring alignment has been shown to correlate well with human judgements [35; 36]. It has been used for cover song detection [37], pattern mining [38], extensively for query-by-humming [14; 39] and in other MIR tasks. Interestingly, DTW has been extended to align items that cannot be naturally represented as single sequences, such as polyphonic music [40] or audio [41; 42]. Consequently, alignment has been also key to finding correspondences among related music items of not the same format (typically called music synchronization): it has been used for score following, the task of aligning different music representations such as audio and score or MIDI (Musical Instrument Digital Interface) [41; 43]. Describing alignment's numerous MIR applications exceeds the scope of this study. However, a complete overview of DTW in music up until 2007 can be found in the work of [PERSON] [44].