# Melodic Similarity and Applications Using Biologically-Inspired Techniques
## 2 Methods and Tools
### Pairwise Alignment  
An intuitive method for DNA or protein sequence comparison is the Levenshtein (or Edit) distance, which computes the minimal number of one-symbol substitutions, insertions and deletions to transform one sequence into the other. Such operations can be naturally mapped to the biological \begin{table}
\begin{tabular}{c c} \hline \hline
**Music** & **Bioinformatics** \\ \hline Melodies, chord progressions & DNA, proteins \\ Oral transmission, cover songs & Evolution \\ Variations, covers & Homologues \\ Tune family, clique & Homology, family \\ Cover song identification, melody retrieval & Homologue detection \\ Stability & Conservation \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Shared concepts and terms between music and bioinformatics. process of mutation. Given a cost for each operation, the weighted Levenshtein distance can be computed using dynamic programming. The major drawback of the Levenshtein distance is that it captures the divergence of the two sequences rather than their relatedness or, the important to this paper, similarity. In addition, it does not allow for identifying conserved regions between the sequences, since it is a purely mathematical distance function. As such, computing the similarity of two DNA or protein sequences is typically performed using alignment, the converse to Edit distance. During alignment, gaps '-' that represent symbols that were deleted from the sequences via the process of evolution [28], are introduced in the sequences, until they have the same length and the amount of \"relatedness\" between symbols at corresponding positions is maximized. More formally, consider two sequences over an alphabet of symbols \(\mathcal{A}\), \(X:=x_{1},x_{2},..,x_{n}\) and \(Y:=y_{1},y_{2},..,y_{m}\) with all \(x_{i},y_{i}\in\mathcal{A}\). An alignment \(A\) of \(X\) and \(Y\), consists of two sequences \(X^{\prime}\) and \(Y^{\prime}\) over \(\{-\}\cup\mathcal{A}\), such that \(|X^{\prime}|=|Y^{\prime}|=L\), where if we remove all '-' from \(X^{\prime}\), \(Y^{\prime}\) we are left with \(X\) and \(Y\) respectively. The number of possible alignments \(A\) for a pair of sequences is exponential in \(n\) and \(m\), so an optimal alignment should be selected given a scoring function that typically derives from a model of \"relatedness\" between the symbols of \(\mathcal{A}\), where the goal is to put similar symbols at the same position. The most typical such scoring function is the alignment score:  
\[c(A)=\sum_{p=1}^{L}v(x_{p}^{\prime},y_{p}^{\prime}) \tag{1}\]  
where \(v:\mathcal{A}\times\mathcal{A}\rightarrow\mathbb{R}\). The scoring function \(v\) is typically encoded as an \(|\mathcal{A}|\times|\mathcal{A}|\) matrix called the substitution matrix. Most pairwise alignment methods use a Dynamic Programming (DP) method, credited to [PERSON] and [PERSON] [29], which computes the optimal (highest scoring) alignment by filling a cost matrix \(D\) recursively:  
\[D(i,j)=max\left\{ \begin{array}{l}D(i-1,j-1)+v(x_{i},y_{j})\\ D(i-1,j)-\gamma\\ D(i,j-1)-\gamma\end{array} \right. \tag{2}\]  
where \(\gamma\) is the gap penalty for aligning a symbol to a gap. An extension uses an affine gap penalty based on the assumption that the occurrence of consecutive deletions/insertions is more probable than the occurrence of the same amount of isolated mutations [28]: for a gap of length \(z\), the gap penalty would be:  
\[\gamma(z)=-d-(z-1)e \tag{3}\]  
where \(d\) and \(e\) are the gap open and gap extension penalties respectively. To optimize an alignment that uses an affine gap penalty requires a slightly more complex DP algorithm [30]. In the simple non-affine gap case, the score of the optimal alignment is stored in \(D(n,m)\), while the alignment itself can be obtained by backtracking from \(D(n,m)\) to \(D(0,0)\). The Needleman and Wunsch approach is a global alignment method, since it aims to find the best score among alignments of full-length sequences.