# Melodic Similarity and Applications Using Biologically-Inspired Techniques
## 4 Multiple Sequence Alignment Quality for Melodic Sequences
### Multiple Sequence Alignment Algorithms and Settings  
From the numerous MSA algorithms, we selected three based on many factors including simplicity, popularity or quality of results on several bioinformatic benchmarks. One of the simplest approaches to MSA, named \"star\" alignment, aims at employing only pairwise alignments for building the final  
Figure 1: The \(15\) unaligned sequences of the tune family “Daar ging een heer”. Colours correspond to motif labels. White colour indicates no motif label. MSA. The idea is to first find the most \"central\" among the sequences, pairwise align it to each one of the rest and then combine the pairwise alignments into a single MSA. This method does not necessarily attempt to optimize the objective function (see Section 2.2) and as such is rarely used. In our case, star alignment can act as a naive baseline for the more sophisticated algorithms to be compared against. Progressive Alignment (PA) [69] is one of the most popular and intuitive approaches, and it comprises three fundamental steps. At first, all pairwise alignments between sequences are computed to determine the similarity between each pair. At the second step, a similarity tree (guide tree) is constructed using a hierarchical clustering method, which in biological sequences is sometimes used to attempt to identify evolutionary relationships between taxa. Finally, working from the leaves of the tree to the root, one aligns alignments, until reaching the root of the tree, where a single MSA is built. The drawback of PA, is that incorrect gaps (especially those at early stages) are retained throughout the process since the moment they are first inserted (the \"once a gap, always a gap\" rule). Iterative refinement methods [70; 71] aim to tackle this problem by iteratively removing each sequence and realigning it with a profile created from the MSA of the rest, until an objective function has been maximized. Our experiments use the PA-based T-Coffee software (Tree-based consistency objective function for alignment evaluation) [72]. T-Coffee aims to tackle the problem by making better use of information in the early stages. It uses an objective function (called COFFEE [73]) that first builds a library of all optimal pairwise alignments and secondly, scores a multiple sequence alignment by measuring its consistency with the library: how many of the aligned pairs in the MSA appear in the library. Locating very similar short and shared sub-regions between large sequences has been in important task in bioinformatics. Such segments can efficiently reduce MSA runtimes and as a consequence, MSA solutions that incorporate some of form of segmentation, such as Dialign[74] and Mafft [75], have found successful application. Mafft in particular, is a progressive alignment method at its core, but incorporates the Fast Fourier Transform (FFT) for biological sequences. In addition, Mafft allows the usage of the iterative refinement method. For non-biological sequences, Mafft offers a \"text\" alignment option that excludes biological and chemically-inspired heuristics from its pipeline. In such a case, segmenting the sequences becomes a by-product of Mafft's objective function that incorporates both a WSOP and a COFFEE-like scoring. According to Mafft's website (mafft.cbrc.jp/alignment/software), \"the use of the WSOP score has the merit that a pattern of gaps can be incorporated into the objective function\". Mafft offers three different strategies for the initial pairwise alignment, that behave differently with regard to the structure of the sequences. Local alignment with affine gap costs localpair is appropriate for unaligned sequences centred around a conserved region. The genafpair strategy uses local alignment with generalized affine gap costs [76] and is appropriate for sequences with several conserved sub-sequences in long unalignable regions. Global alignment with affine gap costs globalpair is appropriate for throughout alignable sequences.