Archived TOC:

• Cross comparison
  • Contour analysis
  • Needleman-Wunsch algorithm implementation
  • SVG highlighting for note differences
• Old pictures for nostalgia

---

Contour analysis: index mapping and highlighting

Contour == melodic interval

• The NeumeComponent (either AQ or SQ) array is extracted to construct a numerical array, via the function location_septenary_mapping() in analysis/analysis.js.

  • For Aquitanian notation: this numerical array is extracted from the @loc attribute.
  • For Square notation: each value of the numerical array is calculated using the formula 7 * octave + pname, with @pname starts at 0 for value c and increment to 6 for value b following the C major scale. Due to the similarity of the formula and the base-7 numerical system, the function is named septenary() in NeumeComponentSQ class.

• The contour arrays are then constructed from the numerical arrays via mapLocToContour(location_septenary_array).

  • The n-th element of the contour array is the melodic interval between the n-th and the (n+1)-th element of the numerical array.
  • In other words, the n-th element of contour array is calculated as location_septenary_array[n + 1] - location_septenary_array[n].
  • This is also kept in mind for the later highlighting functionality.

• Needleman-Wunsch algorithm is used to find the alignment between the two contour arrays. It follows 2 steps:

  • Matrix construction (matrix_nw)
  • Alignment (align_nw)
  • The output arrays of the algorithm is two arrays of alignment with gaps. Two extra arrays is outputted to hold the indecies of the gaps in each alignment array.

• To highlight the mismatches:

  • Look for differences between the two alignment arrays (alignmentA[i] !== alignmentB[i]). Note that these values are melodic intervals.
  • Highlight the corresponding NeumeComponent of index i and i+1 in the two NeumeComponent arrays.
  • gapOffset is necessary to align the index of the NeumeComponent arrays with the index of the alignment arrays due to the addition of gaps.

• To highlight the gaps and gap fillers:

  • Look for the gaps in the alignment arrays.
  • On the gap filler side:
    • Highlight the corresponding NeumeComponent of indecies [i-1, i, i+1, i+2] in the two NeumeComponent arrays.
    • The filler contour is of index i and i+1 in the contour array from the index alignment above.
  • On the gap side:
    • Highlight the corresponding NeumeComponent of indecies [i-1, i, i+1] in the two NeumeComponent arrays.

Description

• To perform analysis on the similarities of chants, we attempted to apply algorithms from bioinformatics in sequence alignment. Here, we successfully implemented Needleman-Wunsch and Smith-Waterman algorithm.
• To run the algorithm test files, run the following command: (assume the developer is in root directory of the repository)

npm test

• To run a single test files, run the script with node, deno, bunx (or any other JavaScript runtime of choice) with the file name. For example:

deno run src/analysis/test-algorithm.js

Needleman-Wunsch algorithm

Implementation

• Needleman-Wunsch algorithm for global alignment:
  • Parsing MEI files into a list of NeumeComponents
  • Extract @loc attribute of Aquitanian neumes, and septenary values from @pname and @oct of Square notation neumes.
  • Construct two arrays of contour (melodic intervals) based on the extracted values.
  • Construct a matrix of scores based on the two arrays.
  • Retrace the matrix to find the optimal path (Alignment step)
    • Append the contour value, gaps, and mismatch to the result array.
  • Align the resulting contour values using its index to obtain the @xml:id of the neumes.
    • Account for the gaps and mismatch in between the two resulting contour arrays and the NeumeComponent arrays.
  • Highlight notes in the MEI files based on the @xml:id obtained, including:
    • Mismatches
    • Gaps

Testings

• To verify the algorithm, we use the following examples:

nw_test01()

Input list A: [2, 5, 7, 9, 3, 1, 2, 4] 
Input list B: [2, 3, 5, 7, 9, 5, 2, 1, 4]
Match score: 1
Mismatch score: -1
Gap score: -2

• Expected matrix (using https://github.com/drdrsh/Needleman-Wunsch):

Smith–Waterman algorithm

Implementation

• Smith–Waterman algorithm for local alignment:
  • To be developed

Testings

sw_test01()

Input list A: [2, 5, 7, 9, 3, 1, 2, 4]
Input list B: [2, 3, 5, 7, 9, 5, 2, 1, 4]

---

For nostalgia purposes only :)