Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article
Research output: Contribution to Journal/Magazine › Journal article
}
TY - JOUR
T1 - Dynamic Programming Algorithms Applied to Musical Counterpoint in Process Composition
T2 - An Example Using Henri Pousseur’s Scambi
AU - Cochrane, Louis J.
AU - Gatherer, Derek
PY - 2020/6/30
Y1 - 2020/6/30
N2 - The Needleman-Wunsch process is a classic tool in bioinformatics, being a dynamic programming algorithm that performs a pairwise alignment of two input biological sequences, either protein or nucleic acid. A distance matrix between the tokens used in the sequences is also required as input. The distance matrix is used to generate a positional pairwise similarity matrix between the input sequences, which is in turn used to generate a dynamic programming matrix. The best path through the dynamic programming matrix is navigated using a traceback procedure that maximises similarity, inserting gaps as necessary. Needleman-Wunsch can align both nucleic acids or proteins, which use alphabets of size 4 and 20 tokens respectively. It can also be applied to any other kind of sequence where distance matrices can be specified. Here, we apply it to chains of Pousseur’s Scambi electronic music fragments, of which there are 32, and which Pousseur categorised by their sonic properties, thus permitting the consecutive construction of distance, similarity and dynamic programming matrices. Traceback through the dynamic programming matrix thus produces contrapuntal duet compositions in which two Scambi chains are played in the maximally euphonious manner, providing also an illustration of the principles of biological sequence alignment in sound.
AB - The Needleman-Wunsch process is a classic tool in bioinformatics, being a dynamic programming algorithm that performs a pairwise alignment of two input biological sequences, either protein or nucleic acid. A distance matrix between the tokens used in the sequences is also required as input. The distance matrix is used to generate a positional pairwise similarity matrix between the input sequences, which is in turn used to generate a dynamic programming matrix. The best path through the dynamic programming matrix is navigated using a traceback procedure that maximises similarity, inserting gaps as necessary. Needleman-Wunsch can align both nucleic acids or proteins, which use alphabets of size 4 and 20 tokens respectively. It can also be applied to any other kind of sequence where distance matrices can be specified. Here, we apply it to chains of Pousseur’s Scambi electronic music fragments, of which there are 32, and which Pousseur categorised by their sonic properties, thus permitting the consecutive construction of distance, similarity and dynamic programming matrices. Traceback through the dynamic programming matrix thus produces contrapuntal duet compositions in which two Scambi chains are played in the maximally euphonious manner, providing also an illustration of the principles of biological sequence alignment in sound.
KW - global alignment
KW - Needleman-Wunsch algorithm
KW - dynamic programming
KW - process composition
KW - counterpoint
KW - music
KW - Scambi
KW - Bio-Art
KW - Bio-Music
U2 - 10.20944/preprints202006.0359.v1
DO - 10.20944/preprints202006.0359.v1
M3 - Journal article
JO - Preprints
JF - Preprints
SN - 2310-287X
ER -