# Multiallelic Walsh transforms

Devin Greene  American University, 4400 Massachusetts Avenue, NW, Washington,
DC, United States, 20016

###### Abstract

A closed formula multiallelic Walsh (or Hadamard) transform is introduced.
Basic results are derived, and a statistical interpretation of some of the
resulting linear forms is discussed.

##  1 Introduction

The Walsh, or Hadamard matrix, is used in evolutionary biology to detect and
quantify epistasis, i.e. interactions, among the effects of alleles over
different loci. However, applications using the Walsh transform are restricted
to _biallelic_ systems: those where each locus has two alleles. Here we
develop two versions of the Walsh matrix which described any multilocus,
multiallele system.

Various authors have attempted to defined multiallelic analogs of the Walsh
transform: See, for instance, [FLMP+23], [MPST23]. In [FLMP+23], the authors
develop a recursive Walsh transform which is closely related to the one we
develop here. However, our approach uses closed formulas to describe the two
related versions of the transform. Furthermore, we emphasize the linear forms
which arise from these matrices, which generalize the notion of Walsh
coefficients introduced to evolutionary biology in [WLWH13].

##  2 Preliminaries

Consider a genotype with $n$ loci, numbered 1 through $n$. Assume that each
locus $i$ has $t_{i}\geq 1$ possible alleles. We label the alleles of a
particular locus $0,1,2,\ldots,t_{i}-1$. If we use the finite integer segment
notation, i.e.

$[\,a,b)=\\{a,a+1,\ldots,b-1\\},$

where $a$, $b$ are integers, then the set of alleles at the $i$th locus is
$[\,0,t_{i})$.

We denote a genotype $g$ as follows. Let $a_{i}$ be the allele at the $i$th
locus of $g$. Then

$g=a_{1}|a_{2}|\cdots|a_{n}$

Note that the set of genotypes is naturally equivalent to the Cartesian
product

$[\,0,t_{1})\times\cdots\times[\,0,t_{n})$

This property will be fundamental for our sum-taking manipulations in this
paper. For example, for any locus $i$, the summation

$\sum_{a_{1}|a_{2}|\cdots|a_{n}}$

can be replaced with

$\sum_{{a}_{1}|\cdots|{a}_{{i}-1}|{a}_{{i}+1}|\cdots|{a}_{n}}\sum_{a_{i}}$
(2.1)

Furthermore, if $f_{j,i}$ are terms in a product, where $f_{j,i}$ depends only
on the locus $i$ and allele $j$, then

$\sum_{a_{1}|a_{2}|\cdots|a_{n}}\prod_{i=1}^{n}f_{a_{i},i}$

can be rewritten as

$\sum_{{a}_{1}|\cdots|{a}_{{k}-1}|{a}_{{k}+1}|\cdots|{a}_{n}}\prod_{0\leq
i\neq k\leq n}f_{a_{i},i}\sum_{a_{k}}f_{a_{k},k}$ (2.2)

The replacements (2.1) and (2.2) will be used without comment for the
remainder of this paper.

We stress that the labelling of alleles should not be interpreted to imply any
ranking or ordinality among those in the same locus. We could have labelled
them with any set of symbols. However, for the sake of convenience in
mathematical notation, we use integers. Nevertheless, in this paper’s
development, the allele in each locus labeled “0” will play a special role as
a “base” or “anchor” point. Though we will not address it in this article, it
can be shown that the choice of an “anchor” allele at each locus does not in
any fundamental way treat such alleles as special or distinct from the others.

We define the set of _fitness landscapes_ to be the finite dimensional Hilbert
space $\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}{}$ with the standard component-
wise inner product, where the components are indexed by the set of genotypes.
The standard basis vector for genotype $a_{1}|a_{2}|\cdots|a_{n}{}$ is denoted
using square brackets, e.g. as $\;[a_{1}|a_{2}|\cdots|a_{n}{}]$.

##  3 Two dual multiallelic Walsh transforms

The Walsh, or Hadamard matrix, is a $2^{n}$ by $2^{n}$ matrix with rows and
columns indexed by bit strings of length $n$, whose $i_{1}\cdots
i_{n},j_{1}\cdots j_{n}$th matrix element can be defined by the formula

$(-1)^{i_{1}j_{1}+i_{2}j_{2}+\cdots+i_{n}j_{n}}$

The Walsh matrix has been used to measure interactions among loci in biallelic
systems. Here, we introduce two linear transformations which generalize to an
arbitrary number of alleles per locus.

Before presenting the definitions, we define two functions: the ${}\omega$
function and the ${}\mu$ function.

The ${}\omega$ function is defined on pairs of elements in a set with a unique
zero element as

$\omega_{x,y}=\begin{cases}1&\text{if $x\neq 0$ and $x=y$}\\\
0&\text{otherwise}\end{cases}$

The ${}\mu$ function is defined on pairs of elements in a similar type of set.

$\mu_{x,y}=\begin{cases}1&\text{if $x=0$ or $y=0$, otherwise}\\\ -1&\text{if
$x=y$}\\\ 0&\text{otherwise}\end{cases}$ (3.1)

We remark that both of these functions are symmetric with respect to their
arguments, i.e. $\omega_{{x},{y}}=\omega_{{y},{x}}$ and
$\mu_{{x},{y}}=\mu_{{y},{x}}$.

In the following definition, recall that $t_{1},\ldots,t_{n}$ are the number
of alleles at loci 1,2,…,$n$.

######  Definition 3.1.

We define the linear transformations $W$ and $Z$ in
$\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}$ with respect to the standard basis as
follows.

$W\;[a_{1}|a_{2}|\cdots|a_{n}]=\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\prod_{i=1}^{n}\;(1-t_{i}\omega_{{a_{i}},{{b}_{i}}})\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$
(3.2)
$Z\;[a_{1}|a_{2}|\cdots|a_{n}]=\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\prod_{i=1}^{n}\;\mu_{{a_{i}},{{b}_{i}}}\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$
(3.3)

For convenience, we adopt the following superscript notation:

$\displaystyle{\;[{a_{1}|a_{2}|\cdots|a_{n}}]}^{\textbf{w}}$
$\displaystyle=W\;[a_{1}|a_{2}|\cdots|a_{n}]$
$\displaystyle{\;[{a_{1}|a_{2}|\cdots|a_{n}}]}^{\textbf{z}}$
$\displaystyle=Z\;[a_{1}|a_{2}|\cdots|a_{n}]$

######  Example 3.1.

To understand the motivation behind Definition 3.1, consider the vectors
${\;[2|0]}^{\textbf{w}}$ and ${\;[2|0]}^{\textbf{z}}$ in $\mathbb{C}^{3,3}$.
From (3.2) and (3.3) above,

$\displaystyle{\;[2|0]}^{\textbf{w}}$
$\displaystyle=\;[0|0]+\;[0|1]+\;[0|2]+\;[1|0]-2\;[2|0]$ (3.4)
$\displaystyle+\;[1|1]+\;[1|2]-2\;[2|1]-2\;[2|2]$
$\displaystyle{\;[2|0]}^{\textbf{z}}$
$\displaystyle=\;[0|0]+\;[0|1]+\;[0|2]-\;[2|0]-\;[2|1]-\;[2|2]$ (3.5)

If we take the inner product of a fitness landscape $v$ with each vector
above, we obtain the following linear forms.

$\left<{v},{{\;[2|0]}^{\textbf{w}}}\right>=v_{00}+v_{01}+v_{02}+v_{10}-2v_{20}+v_{11}+v_{12}-2v_{21}-2v_{22}$
(3.6)
$\left<{v},{{\;[2|0]}^{\textbf{z}}}\right>=v_{00}+v_{01}+v_{02}-v_{20}-v_{21}-v_{22}$
(3.7)

We can rewrite (3.6), up to a scalar multiple, as

$\frac{(v_{20}-\frac{v_{00}+v_{10}}{2})+(v_{21}-\frac{v_{01}+v_{11}}{2})+(v_{22}-\frac{v_{02}+v_{12}}{2})}{3}$

This is readily interpreted as being the average effect of replacing the
allele at the first locus with ‘2’ as compared to the average of the
alternatives.

Rewriting (3.7), we obtain, up a scalar multiple,

$\frac{(v_{20}-v_{00})+(v_{21}-v_{01})+(v_{22}-v_{02})}{3}$

which can be interpreted as the average effect of replacing ‘0’ in the first
locus with ‘2’.

######  Example 3.2.

The formulas (3.2) and (3.3) give the same vector at $\;[0|0|\ldots|0]$,
indeed

${\;[0|0|\ldots|0]}^{\textbf{w}}={\;[0|0|\ldots|0]}^{\textbf{z}}=\sum_{a_{1}|a_{2}|\cdots|a_{n}}\;[a_{1}|a_{2}|\cdots|a_{n}]$

Thus if $v$ is a fitness landscape in $\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}$,
then

$\displaystyle\frac{1}{t_{1}\cdots
t_{n}}\left<{v},{{\;[0|0|\ldots|0]}^{\textbf{w}}}\right>$
$\displaystyle=\frac{1}{t_{1}\cdots
t_{n}}\left<{v},{{\;[0|0|\ldots|0]}^{\textbf{z}}}\right>$
$\displaystyle=\text{the average over all of $v$'s components}$

The following theorem constitutes the main result of this article.

######  Theorem 3.1.

.

  1. 1.

$W$ and $Z$ are self-adjoint.

  2. 2.

$W$ and $Z$ are scaled inverses of each other. Explicitly

$ZW=WZ=t_{1}\cdots t_{n}I$ (3.8)

  3. 3.

$W^{2}$ and $Z^{2}$ are positive definite and block diagonal with matching
block subspaces. Explicitly

$(W^{2})_{a_{1}|a_{2}|\cdots|a_{n},{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\\\
=\prod_{i=1}^{n}t_{i}\left(\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(t_{i}\delta_{a_{i},b_{i}}-1)\right)\hfil$
(3.9)

and

$(Z^{2})_{a_{1}|a_{2}|\cdots|a_{n},{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\\\
=\prod_{i=1}^{n}\left(t_{i}\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(1+\delta_{a_{i},b_{i}})\right)\hfil$
(3.10)

###### Proof.

We start with the matrix representations of $W$ and $Z$ with respect to the
standard basis. (Strictly speaking, since Definition 3.1 is a vector
definition, we should distinguish between left acting matrices and right
acting matrices. However, since $\omega{}$ and $\mu{}$ are symmetric on their
arguments, the distinction is irrelevant, and all the more so when we have
shown that the matrices are self-adjoint.)

$(W)_{a_{1}|a_{2}|\cdots|a_{n},\,{b}_{1}|{b}_{2}|\cdots|{b}_{n}}=\prod_{i=1}^{n}\;(1-t_{i}\omega_{{a_{i}},{{b}_{i}}})$
$(Z)_{a_{1}|a_{2}|\cdots|a_{n},\,{b}_{1}|{b}_{2}|\cdots|{b}_{n}}=\prod_{i=1}^{n}\;\mu_{{a_{i}},{{b}_{i}}}$

Part 1 then follows immediately from the symmetry of $\omega{}$ and $\mu{}$ as
was just alluded to.

We use induction for Part 2. The case $n=0$ is trivial. Assume validity at
$n$, and consider the matrix element of the product of $W$ and $Z$ at $n+1$:

$\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n+1}}\prod_{i=1}^{n+1}\;(1-t_{i}\omega_{{{a}_{i}},{{c}_{i}}})\prod_{i=1}^{n+1}\;\mu_{{{c}_{i}},{{b}_{i}}}$
(3.11)

We write (3.11) as

$\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n}}\prod_{i=1}^{n}(1-t_{i}\omega_{{a_{i}},{c_{i}}})\mu_{{c_{i}},{b_{i}}}\sum_{c_{n+1}}(1-t_{n+1}\omega_{{a_{n+1}},{c_{n+1}}})\mu_{{c_{n+1}},{b_{n+1}}}\\\
$

For the remainder of this part of the proof, the focus will be on the sum

$\sum_{c_{n+1}}(1-t_{n+1}\omega_{{a_{n+1}},{c_{n+1}}})\mu_{{c_{n+1}},{b_{n+1}}}$
(3.12)

Case: $a_{n+1}=b_{n+1}=0$. In this case $\omega_{{a_{n+1}},{c_{n+1}}}=0$ and
$\mu_{{c_{n+1}},{b_{n+1}}}=1$ for all $c_{n+1}$. Thus each summand in (3.12)
is 1, and so the total sum is $t_{n+1}$. The desired result follows by
induction.

Case: $a_{n+1}=b_{n+1}\neq 0$. When $c_{n+1}=0$,
$\omega_{{a_{n+1}},{c_{n+1}}}=0$ and $\mu_{{c_{n+1}},{b_{n+1}}}=1$, in which
case the summand is 1. When $c_{n+1}=a_{n+1}=b_{n+1}$,
$\omega_{{a_{n+1}},{c_{n+1}}}=1$ and $\mu_{{c_{n+1}},{b_{n+1}}}=-1$, thus the
summand is $t_{n+1}-1$. For other values of $c_{n+1}$,
$\mu_{{c_{n+1}},{b_{n+1}}}=0$, thus the summand is 0. It follows that the sum
(3.12) is $t_{n+1}$. The result follows by induction.

Case: $a_{n+1}\neq b_{n+1}=0$. In this case $\mu_{{c_{n+1}},{b_{n+1}}}=1$ for
all $c_{n+1}$, and so the sum (3.12) can be expressed as
$\sum_{c_{n+1}}(1-t_{n+1}\omega_{{a_{n+1}},{c_{n+1}}})$. If $c_{n+1}\neq
a_{n+1}$, then $\omega_{{c_{n+1}},{a_{n+1}}}=0$, in which case the summand is
1. If $c_{n+1}=a_{n+1}$, then $\omega_{{c_{n+1}},{a_{n+1}}}=1$, and the
summand is $1-t_{n+1}$. The total sum is then 0, as it should be since
${a}_{1}|{a}_{2}|\cdots|{a}_{n+1}\neq{b}_{1}|{b}_{2}|\cdots|{b}_{n+1}$

Case: $b_{n+1}\neq a_{n+1}=0$. In this case $\omega_{{c_{n+1}},{a_{n+1}}}=0$
for all $c_{n+1}$, so (3.12) can be expressed as
$\sum_{c_{n+1}=0}^{t_{n+1}-1}\mu_{{c_{n+1}},{b_{n+1}}}$.
$\mu_{{c_{n+1}},{b_{n+1}}}=1$ when $c_{n+1}=0$, and
$\mu_{{c_{n+1}},{b_{n+1}}}=-1$ when $c_{n+1}=b_{n+1}$. Otherwise,
$\mu_{{c_{n+1}},{b_{n+1}}}=0$. Thus the sum (3.12) is 0, as it should be since
${a}_{1}|{a}_{2}|\cdots|{a}_{n+1}\neq{b}_{1}|{b}_{2}|\cdots|{b}_{n+1}$

Case: $a_{n+1}\neq b_{n+1}$, and $a_{n+1},b_{n+1}\neq 0$. In this case when
$c_{n+1}=0$, $\omega_{{a_{n+1}},{c_{n+1}}}=0$ and
$\mu_{{c_{n+1}},{b_{n+1}}}=1$ thus the summand is 1. When $c_{n+1}=a_{n+1}$
then $\omega_{{a_{n+1}},{c_{n+1}}}=1$ and $\mu_{{c_{n+1}},{b_{n+1}}}=0$, thus
the summand is 0. When $c_{n+1}=b_{n+1}$ then $\omega_{{a_{n+1}},{c_{n+1}}}=0$
and $\mu_{{c_{n+1}},{b_{n+1}}}=-1$ thus the summand is $-1$. Thus the sum
(3.12) totals to 0, as it should since
${a}_{1}|{a}_{2}|\cdots|{a}_{n+1}\neq{b}_{1}|{b}_{2}|\cdots|{b}_{n+1}$

This completes the proof for Part 2.

For Part 3, $W^{2}$ is positive definite since $W$ is invertible, and
$WW^{*}=W^{2}$. Similarly for $Z^{2}$. The claim respecting block diagonality
follows from the formulas (3.9) and (3.10), which we now prove by induction on
$n$. For both $Z$ and $W$, the case where $n=0$ is trivial. Assume validity at
$n$, and consider a matrix element of $W$ at $n+1$:

$(W^{2})_{{a}_{1}|{a}_{2}|\cdots|{a}_{n+1},{b}_{1}|{b}_{2}|\cdots|{b}_{n+1}}\\\
=\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n+1}}\prod_{i=1}^{n+1}(1-t_{i}\omega_{{a_{i}},{c_{i}}})(1-t_{i}\omega_{{c_{i}},{b_{i}}})\hfil\\\
=\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n}}\prod_{i=1}^{n}(1-t_{i}\omega_{{a_{i}},{c_{i}}})(1-t_{i}\omega_{{c_{i}},{b_{i}}})\hfil\\\
\times\sum_{c_{n+1}}(1-t_{n+1}\omega_{{a_{n+1}},{c_{n+1}}})(1-t_{n+1}\omega_{{c_{n+1}},{a_{n+1}}})\hfil$
(3.13)

We focus on the term

$\sum_{c_{n+1}}(1-t_{n+1}\omega_{{a_{n+1}},{c_{n+1}}})(1-t_{n+1}\omega_{{c_{n+1}},{b_{n+1}}})$
(3.14)

By induction, in each case that follows, it suffices to show that (3.14) is
equivalent to the expression

$t_{n+1}\left(\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(t_{n+1}\delta_{a_{i},b_{i}}-1)\right)$
(3.15)

Case: $a_{i}=b_{i}=0$. In this case (3.14) is $t_{n+1}$, as is (3.15).

Case: $a_{i}=b_{i}\neq 0$. In this case (3.14) is

$(1-t_{n+1})^{2}+t_{n+1}-1=(t_{n+1}-1)t_{n+1}$

as is (3.15)

Case: $a_{i}\neq b_{i}=0$ or $b_{i}\neq a_{i}=0$. In this case (3.14) is

$(1-t_{n+1})+(t_{n+1}-1)=0$

as is (3.15)

Case: $a_{i}\neq b_{i}$, $a_{i},b_{i}\neq 0$. In this case (3.14) is

$2(1-t_{n+1})+(t_{n+1}-2)=-t_{n+1}$

as is (3.15)

Now consider the matrix element of $Z$ at $n+1$

$(Z^{2})_{{a}_{1}|{a}_{2}|\cdots|{a}_{n+1},{b}_{1}|{b}_{2}|\cdots|{b}_{n+1}}\\\
=\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n+1}}\prod_{i=1}^{n+1}\mu_{{a_{i}},{c_{i}}}\mu_{{c_{i}},{b_{i}}}\hfil\\\
=\sum_{{c}_{1}|{c}_{2}|\cdots|{c}_{n}}\prod_{i=1}^{n}\mu_{{a_{i}},{c_{i}}}\mu_{{c_{i}},{b_{i}}}\hfil\\\
\times\sum_{c_{n+1}}\mu_{{a_{n+1}},{c_{n+1}}}\mu_{{c_{n+1}},{a_{n+1}}}\hfil$
(3.16)

Similarly to how we handled $W$, we focus on the term

$\sum_{c_{n+1}}\mu_{{a_{n+1}},{c_{n+1}}}\mu_{{c_{n+1}},{a_{n+1}}}$ (3.17)

and show by induction that each case has (3.17) equal to

$t_{i}\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(1+\delta_{a_{i},b_{i}})$
(3.18)

Case: $a_{i}=b_{i}=0$. In this case (3.17) is $t_{n+1}$, as is (3.18).

Case: $a_{i}=b_{i}\neq 0$. In this case (3.17) is 2, as is (3.18).

Case: $a_{i}\neq b_{i}=0$ or $b_{i}\neq a_{i}=0$. In this case (3.17) is 0, as
is (3.18).

Case: $a_{i}\neq b_{i}$, $a_{i},b_{i}\neq 0$. In this case (3.17) is 1, as is
(3.18).

∎

For the remainder of this paper, we will identify $W$ and $Z$ with their
matrix representations on the standard basis.

######  Corollary 3.1.

The sets

$\\{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}\\}_{a_{1}|a_{2}|\cdots|a_{n}}\\\
$

and

$\\{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}\\}_{a_{1}|a_{2}|\cdots|a_{n}}$

are bases for $\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}$. Furthermore, if $v$ is
a fitness landscape, and the coefficients in the first basis are
$c_{a_{1}|a_{2}|\cdots|a_{n}}$, i.e.

$v=\sum_{a_{1}|a_{2}|\cdots|a_{n}}c_{a_{1}|a_{2}|\cdots|a_{n}}{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}},$

then

$c_{a_{1}|a_{2}|\cdots|a_{n}}=\frac{1}{t_{1}\cdots
t_{n}}\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}Z_{a_{1}|a_{2}|\cdots|a_{n},{b}_{1}|{b}_{2}|\cdots|{b}_{n}}v_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}$

If $s_{a_{1}|a_{2}|\cdots|a_{n}}$ are the coefficients in the second basis,
i.e.

$v=\sum_{a_{1}|a_{2}|\cdots|a_{n}}s_{a_{1}|a_{2}|\cdots|a_{n}}{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}$

then

$s_{a_{1}|a_{2}|\cdots|a_{n}}=\frac{1}{t_{1}\cdots
t_{n}}\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}W_{a_{1}|a_{2}|\cdots|a_{n},{b}_{1}|{b}_{2}|\cdots|{b}_{n}}v_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}$

###### Proof.

This follows immediately from Theorem 3.1 and basis changing methods in linear
algebra. ∎

######  Definition 3.2.

The _degree_ of a genotype $a_{1}|a_{2}|\cdots|a_{n}$ is the number of non-
zero alleles, i.e.

${\rm deg}(a_{1}|a_{2}|\cdots|a_{n})=\\#\\{i|a_{i}\neq 0\\}$

######  Corollary 3.2.

Let $a_{1}|a_{2}|\cdots|a_{n}$ and ${b}_{1}|{b}_{2}|\cdots|{b}_{n}$ be two
genotypes with different degrees. Then

$\left<{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}},{{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}^{\textbf{w}}}\right>=0$

and

$\left<{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}},{{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}^{\textbf{z}}}\right>=0$

###### Proof.

If $a_{1}|a_{2}|\cdots|a_{n}$ and ${b}_{1}|{b}_{2}|\cdots|{b}_{n}$ have
different degree, then there must a locus $i$ such that one of $a_{i},b_{i}$
is zero the the other non-zero. Then, by (3.9) and (3.10),

$\left<{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}},{{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}^{\textbf{w}}}\right>\\\
=\left<{W^{2}\;[a_{1}|a_{2}|\cdots|a_{n}]},{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}\right>\hfil\\\
=\prod_{i=1}^{n}t_{i}\left(\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(t_{i}\delta_{a_{i},b_{i}}-1)\right)=0\hfil$

and

$\left<{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}},{{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}^{\textbf{z}}}\right>\\\
=\left<{Z^{2}\;[a_{1}|a_{2}|\cdots|a_{n}]},{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}\right>\hfil\\\
=\prod_{i=1}^{n}\left(t_{i}\delta_{a_{i},0}\delta_{b_{i},0}+(1-\delta_{a_{i},0})(1-\delta_{b_{i},0})(1+\delta_{a_{i},b_{i}})\right)=0\hfil$

∎

######  Corollary 3.3.

Define the following subspaces:

$S_{i,z}={\rm span}(\\{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}|{\rm
deg}(a_{1}|a_{2}|\cdots|a_{n})=i\\})$

and

$S_{i,m}={\rm span}(\\{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}|{\rm
deg}(a_{1}|a_{2}|\cdots|a_{n})=i\\})$

Then

  1. 1.

$S_{i,z}=S_{i,m}$ for each $i$, and we will denote the common subspace
$S_{i}$, and

  2. 2.

$\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}=S_{0}\oplus S_{1}\oplus\cdots\oplus
S_{n}$ is an orthogonal decomposition.

###### Proof.

That

$\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}=\bigoplus_{i=1}^{n}S_{i,z}=\bigoplus_{i=1}^{n}S_{i,m}$

follows immediately from Corollary 3.2.

Let $a_{1}|a_{2}|\cdots|a_{n}$ and ${b}_{1}|{b}_{2}|\cdots|{b}_{n}$ be two
genotypes of different degree. Taking inner products, we have

$\displaystyle\left<{Z\;[a_{1}|a_{2}|\cdots|a_{n}]},{W\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}\right>$
$\displaystyle=\left<{WZ\;[a_{1}|a_{2}|\cdots|a_{n}]},{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}\right>$
$\displaystyle=t_{1}\cdots
t_{n}\left<{\;[a_{1}|a_{2}|\cdots|a_{n}]},{\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}\right>=0$

This shows that $S_{i,m}=S_{i,z}$ for each $i$, completing the proof. ∎

######  Remark 3.1.

In the presentation of the bases derived from $W$ and $Z$ (i.e. the columns of
their matrices when written in the standard basis), we have avoided any
discussion of the appropriate scaling of these vectors or that of the
coefficients corresponding to them, preferring to express these vectors in
integral form. The magnitude of any vector in the $W$\- or $Z$-basis can be
computed directly or by using one of the formulas (3.9) or (3.10).

It is worth keeping in mind that unlike the biallelic Walsh matrix, the
columns of $W$ (or the columns of $Z$) are not all mutually orthogonal.

##  4 Additive fitness landscapes

######  Definition 4.1.

A fitness landscape $v\in\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}$ is said to be
_additive_ if for every allele $a_{i}$ at locus $i$ there exists an _additive
effect_ $\phi_{v}(a_{i},i)$ such that for all genotypes
$a_{1}|a_{2}|\cdots|a_{n}$,

$v_{a_{1}|a_{2}|\cdots|a_{n}}=\sum_{i=1}^{n}\phi_{v}(a_{i},i)$

######  Theorem 4.1.

Using the notation from Corollary 3.3, we have the following equivalence:

$\text{The set of additive fitness landscape{}s}=S_{0}\oplus S_{1}$ (4.1)

###### Proof.

$\subseteq$: We use the term _unit element for allele $c_{k}$ at locus $k$_ to
denote the additive fitness landscape $u$ with the property

$\phi_{u}(b_{j},j)=\delta_{(c_{k},k),(b_{j},j)}$

for any allele $b_{j}$ and locus $j$. It should be clear from Definition 4.1
that

${\rm span}(\text{unit elements})=\text{set of additive fitness landscape{}s}$

Let $u\in\mathbb{C}^{t_{1},t_{2},\ldots,t_{n}}$ be the unit element
corresponding to the allele-locus pair $(c_{k},k)$, and let
$a_{1}|a_{2}|\cdots|a_{n}$ be a genotype with degree $\geq 2$. Then there must
be a locus $m\neq k$ where $a_{m}\neq 0$.

We compute the coefficient of $u$ at
${\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]}^{\textbf{w}}$ using Corollary 3.1 and
ignoring the factor $1/t_{i}\cdots t_{n}$.

$\displaystyle\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}$ $\displaystyle
Z_{a_{1}|a_{2}|\cdots|a_{n},{b}_{1}|{b}_{2}|\cdots|{b}_{n}}u_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}$
$\displaystyle=\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n},b_{k}=c_{k}}\prod_{i=1}^{n}\mu_{{a_{i}},{b_{i}}}$
$\displaystyle=\sum_{{b}_{1}|\cdots|{b}_{{m}-1}|{b}_{{m}+1}|\cdots|{b}_{n},b_{k}=c_{k}}\prod_{i\neq
m}\mu_{{a_{i}},{b_{i}}}\sum_{b_{m}}\mu_{{a_{m}},{b_{m}}}$ (Since $m\neq k$)
$\displaystyle=0$ (Since $a_{m}\neq 0$)

Thus the coefficients of $u$ in the basis
$\\{{\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}\\}_{a_{1}|a_{2}|\cdots|a_{n}}$
are non-zero only for basis elements with degree $\leq 1$, proving the
inclusion.

$\supseteq$: From Corollary 3.3, $S_{0}$ is spanned by
${\;[0|\cdots|0]}^{\textbf{z}}$, and from (3.3),

${\;[0|\cdots|0]}^{\textbf{z}}=\sum_{a_{1}|a_{2}|\cdots|a_{n}}\;[a_{1}|a_{2}|\cdots|a_{n}].$

This is clearly the additive fitness landscape with effect $1/n$ for all
alleles.

From Corollary 3.3, $S_{1}$ is spanned by vectors which have the
form${\;[0|\cdots|a_{j}|\cdots|0]}^{\textbf{z}}$, where $a_{j}\neq 0$. From
(3.3), we have

$\displaystyle[0|\cdots|$ $\displaystyle a_{j}|\cdots|0]^{\bf z}$
$\displaystyle=\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\mu_{{a_{j}},{b_{j}}}\mu_{{0},{b_{j}}}^{n-1}\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$
$\displaystyle=\sum_{{b}_{1}|{b}_{2}|\cdots|{b}_{n}}\mu_{{a_{j}},{b_{j}}}\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$
(Since $\mu_{{0},{b_{j}}}=1$)
$\displaystyle=\sum_{b_{1}|\cdots|b_{j-1}|0|b_{j+1}|\cdots|b_{n}}\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$
$\displaystyle\hskip
20.00003pt-\sum_{b_{1}|\cdots|b_{j-1}|a_{j}|b_{j+1}|\cdots|b_{n}}\;[{b}_{1}|{b}_{2}|\cdots|{b}_{n}]$

This is an additive fitness landscape with effect $1/n$ for all alleles at
loci $\neq j$, effect $1/n$ for the 0 allele at locus $j$, effect $(1-2n)/n$
for allele $a_{j}$ at loci $j$, and $(1-n)/n$ at all other alleles at locus
$j$.

This completes the proof. ∎

##  5 Further examples

In this final section, we continue in the spirit of Examples 3.1 and 3.2 and
interpret basis vectors in the form
${\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{w}}$ or
${\;[a_{1}|a_{2}|\cdots|a_{n}]}^{\textbf{z}}$ as linear forms and give an
interpretation in the language of interacting effects.

Consider the case with two loci where each has three alleles. The following
are the corresponding matrices for $W$ and $Z$.

$W=\blockarray{rrrrrrrrrr}&0|00|10|21|02|01|11|22|12|2\\\
\block{r(rrrrrrrrr)}0|0111111111\\\ 0|11-2111-21-21\\\ 0|211-2111-21-2\\\
1|0111-21-2-211\\\ 2|01111-211-2-2\\\ 1|11-21-214-2-21\\\ 1|211-2-21-241-2\\\
2|11-211-2-214-2\\\ 2|211-21-21-2-24\\\ $ (5.1)

$Z=\blockarray{rrrrrrrrrr}&0|00|10|21|02|01|11|22|12|2\\\
\block{r(rrrrrrrrr)}0|0111111111\\\ 0|11-1011-10-10\\\ 0|210-1110-10-1\\\
1|0111-10-1-100\\\ 2|01110-100-1-1\\\ 1|11-10-101000\\\ 1|210-1-100100\\\
2|11-100-10010\\\ 2|210-10-10001\\\ $ (5.2)

The block diagonality in Theorem 3.1, including the orthogonal decomposition
with respect to degree asserted in Corollary 3.3 is seen when we compute
$W^{2}$ and $Z^{2}$.

$W^{2}=\blockarray{rrrrrrrrrr}&0|00|10|21|02|01|11|22|12|2\\\
\block{r(rrrrrrrrr)}0|0900000000\\\ 0|1018-9000000\\\ 0|20-918000000\\\
1|000018-90000\\\ 2|0000-9180000\\\ 1|10000036-18-189\\\ 1|200000-18369-18\\\
2|100000-18936-18\\\ 2|2000009-18-1836\\\ $

$Z^{2}=\blockarray{rrrrrrrrrr}&0|00|10|21|02|01|11|22|12|2\\\
\block{r(rrrrrrrrr)}0|0900000000\\\ 0|1063000000\\\ 0|2036000000\\\
1|0000630000\\\ 2|0000360000\\\ 1|1000004221\\\ 1|2000002412\\\
2|1000002142\\\ 2|2000001224\\\ $

We saw in Examples 3.1 and 3.2 how some of the basis vectors generated by $W$
and $Z$ gave rise to zeroth and first order linear forms. Having all the
vectors in column form in (3.4) and (3.5) allows us to compute, for any
fitness landscape $v$,

$\left<{v},{{\;[1|1]}^{\textbf{w}}}\right>=v_{00}-2v_{01}+v_{02}-2v_{10}+v_{20}+4v_{11}-2v_{12}-2v_{21}+v_{22}$
(5.3)

and

$\left<{v},{{\;[1|1]}^{\textbf{z}}}\right>=v_{00}-v_{01}-v_{10}+v_{11}$ (5.4)

If we compare these forms to the analogous form arising from the biallelic
Walsh transform, i.e.

$u_{00}-u_{01}-u_{10}+u_{11}$

we see that (5.4) is essentially the same.

The form (5.3) is a little trickier to interpret. We can start with the
difference between $v_{11}$ and the average of its alternatives which differ
at both loci:

$v_{11}-\frac{1}{4}(v_{00}+v_{02}+v_{20}+v_{22})$ (5.5)

The averaged first order effects of replacing an allele with allele 1 in a
single locus (cf. Example 3.1) are given by

$\displaystyle**\rightarrow*1:$
$\displaystyle\quad\frac{1}{3}(v_{01}+v_{11}+v_{21})-\frac{1}{6}(v_{00}+v_{02}+v_{10}+v_{20}+v_{12}+v_{22})$
(5.6) $\displaystyle**\rightarrow 1*:$
$\displaystyle\quad\frac{1}{3}(v_{10}+v_{11}+v_{12})-\frac{1}{6}(v_{00}+v_{01}+v_{02}+v_{20}+v_{21}+v_{22})$
(5.7)

If we want the “pure” second order effect of substituting ‘11’ for one of
‘00’, ‘02’, ‘20’, or ‘22’, we should subtract (5.6) and (5.7) from (5.5). When
we do so, we obtain one twelfth of (5.3), a useful interpretation of that
form.

## References

  * [FLMP+23] Andre J Faure, Ben Lehner, Verónica Miró Pina, Claudia Serrano Colome, and Donate Weghorn.  An extension of the walsh-hadamard transform to calculate and model epistasis in genetic landscapes of arbitrary shape and complexity.  bioRxiv, pages 2023–03, 2023.
  * [MPST23] Brian PH Metzger, Yeonwoo Park, Tyler N Starr, and Joseph W Thornton.  Epistasis facilitates functional evolution in an ancient transcription factor.  bioRxiv, pages 2023–04, 2023.
  * [WLWH13] Daniel M Weinreich, Yinghong Lan, C Scott Wylie, and Robert B. Heckendorn.  Should evolutionary geneticists worry about higher-order epistasis?  Current Opinion in Genetics & Development, 23(6):700–707, 2013\.  Genetics of system biology.


# Tracking Short-Term Temporal Linguistic Dynamics to Characterize Candidate
Therapeutics for COVID-19 in the CORD-19 Corpus

James Powell<EMAIL_ADDRESS>0000-0002-3517-7485 Los Alamos National
LaboratoryP.O. Box 1663Los AlamosNew MexicoUSA87545 and  Kari Sentz
<EMAIL_ADDRESS>Los Alamos National LaboratoryP.O. Box 1663Los AlamosNew
MexicoUSA87545

###### Abstract.

Scientific literature tends to grow as a function of funding and interest in a
given field. Mining such literature can reveal trends that may not be
immediately apparent. The CORD-19 corpus represents a growing corpus of
scientific literature associated with COVID-19. We examined the intersection
of a set of candidate therapeutics identified in a drug-repurposing study with
temporal instances of the CORD-19 corpus to determine if it was possible to
find and measure changes associated with them over time. We propose that the
techniques we used could form the basis of a tool to pre-screen new candidate
therapeutics early in the research process.

††conference: SenSys 2020: 18th ACM Conference on Embedded Networked Sensor
Systems; November 16-19, 2020; Yokohama, Japan

##  1\. Introduction

Diachronic word analysis is Natural Language Processing (NLP) technique for
characterizing the evolution of words over time. Often used for historical
linguistic studies, it can also be applied to scientific literature (Tshitoyan
et al., 2019) and can reveal early evidence of scientific discoveries before
they become widely known.

Drug-repurposing studies aim to identify existing drugs that might be useful
in treating other diseases. The availability of large amounts of data about
drugs and infectious agents such as viruses has enabled such studies to be
performed in-silico. In early 2020, a number of repurposing studies were
undertaken to identify potential treatments for COVID-19.

The CORD-19 corpus (Wang et al., 2020) was established in March 2020 as a
repository for research related to SARS-COV-2 and other coronaviruses. It
aggregates content from PubMed, bioRxiv, medRxiv, and other sources, and it is
updated with new publications on a regular basis. Figure 1 illustrates the
growth of CORD-19 through mid-2020.

Figure 1. Weekly growth of the CORD-19 corpus

Using CORD-19, we conducted a diachronic survey of candidate therapeutics
identified in one of the more exhaustive drug re-purposing studies conducted
to date for COVID-19, undertaken in February 2020 at Oak Ridge National
Laboratory. This study, detailed in (Smith and Smith, 2020), analyzed drugs in
the SWEETLEAD database for potential antiviral properties. The study produced
a dataset identifying over 9,000 existing approved drugs and supplements as
potential candidate therapeutics for COVID-19. Most importantly for our
purposes, this dataset included commonly used drug or supplement names for
each candidate.

Our survey considered the following questions:

  * •

How many candidate therapeutics appear in CORD-19?

  * •

Do references to the candidates change over time?

##  2\. Materials and Methods

Using temporal snapshots of CORD-19 spanning March 13 to June 30, we computed
frequency and semantic representations for each candidate therapeutic found in
the corpus. For each temporal instance, we computed TF/IDF (Term
Frequency/Inverse Document Frequency) score for each candidate, a common
metric to evaluate the relative importance of terms in a corpus.

Figure 2. TF/IDF and cosine embedding distances

To perform semantic analysis, we first computed diachronic word embeddings for
each temporal instance of the corpus. These embeddings were aligned with one
another to ensure that terms from each temporal instance were comparable. The
technique we used is based on TWEC [3]. It uses a negative sampling
optimization of softmax to maximize the probability that a set of words
surrounding word $w_{k}$ are representative of its context in time ($C^{t}$),
when multiplied by the mean of atemporal word embedding vectors from $u$ (the
compass) for the same set of context words around $w_{k}$.

$\mathnormal{\max_{\mathbf{C}^{t}}\log
P({w_{k}}|\gamma({w_{k}}))=\sigma(\vec{u}_{k}\cdot\vec{c}{\,{}^{t}_{\gamma(w_{k})}})}$

Since the TWEC embedding model did not account for phrases, we incoporated an
additional step to indentify them. Phrases (including drug names) were then
specially encoded to allow them to be treated like words. Figure 2 shows
TF/IDF verses the mean embedding distance to the compass for candidate
therapeutics.

Because diachronic embedding instances were aligned with one another, we were
able to isolate a given candidate and visualize its semantic trajectory over
time (Figure 3). As the trajectory is based on nearest neighbors at a given
time, subtle changes in semantic associations become apparent (Stewart et al.,
2017).

Figure 3. Semantic trajectory of ’acetazolamide’ (rank -2.4). Nodes along the
path represent the candidate embedding vector and its two closest terms at
time $t$

Semantic trajectory of ’acetazolamide’ (rank -2.4). Nodes along the path
represent the candidate embedding vector and its two closest terms at time $t$

##  3\. Results and Analysis

We detected 14% (1267) of the candidate therapeutics in CORD-19 at 3/13,
increasing to 26% (2361) by 6/30. For candidates detected in multiple adjacent
temporal instances of the corpus, we were able measure their changes over
time. We found that many candidates exhibited increases in frequency, and
stable or strengthening semantic associations. However, given the nature of
this corpus, we suspected some would exhibit other kinds of change over time.

We found that some candidate therapeutics exhibited different patterns of
semantic associations. Using heatmap visualizations as described in (Xu and
Crestani, 2017), we can illustrate two additional recurring patterns of
behavior. Some candidates exhibited weakening semantic associations over time
(Figure 4), while others exhibited an abrupt persistent shift to a different
pattern (Figure 5). Additionally, we found that these changes were not
strongly correlated with changes to a target’s frequency scores.

Figure 4. Example of weakening semantic associations for the candidate
therapeutic ivermectin
Figure 5. Example of disrupted semantic associations for the candidate
therapeutic acetazolamide

##  4\. Conclusion

Our diachronic survey of candidate therapeutics for COVID-19 in the CORD-19
corpus found that some exhibited weakening or abrupt changes of semantic
associations. We speculate that this could be related to the publication of
new research that positively or negatively affected consideration of a
candidate therapeutic as a treatment for COVID-19. Future work will
investigate how to detect and quantify these patterns, and to determine if
there are any correlations between a target’s rank and magnitude of change.

## References

  * (1)
  * Smith and Smith (2020) Micholas Smith and Jeremy C. Smith. 2020.  Repurposing Therapeutics for Covid-19.  https://doi.org/10.26434/chemrxiv.11871402.v3
  * Stewart et al. (2017) Ian Stewart, Dustin Arendt, Eric Bell, and Svitlana Volkova. 2017.  Measuring, predicting and visualizing short-term change in word representation and usage in vkontakte social network.  _arXiv preprint arXiv:1703.07012_ (2017).
  * Tshitoyan et al. (2019) Vahe Tshitoyan, John Dagdelen, Leigh Weston, Alexander Dunn, Ziqin Rong, Olga Kononova, Kristin A. Persson, Gerbrand Ceder, and Anubhav Jain. 2019.  Unsupervised word embeddings capture latent knowledge from materials science literature.  _Nature_ 571 (july 2019), 95–98.  https://doi.org/10.1038/s41586-019-1335-8
  * Wang et al. (2020) Lucy Lu Wang, Kyle Lo, Yoganand Chandrasekhar, Russell Reas, Jiangjiang Yang, Darrin Eide, Kathryn Funk, Rodney Kinney, Ziyang Liu, William Merrill, et al. 2020\.  CORD-19: The Covid-19 Open Research Dataset.  arXiv:2004.10706v2
  * Xu and Crestani (2017) Zaikun Xu and Fabio Crestani. 2017.  Temporal Semantic Analysis and Visualization of Words. In _Proceedings of the 8th Italian Information Retrieval Workshop, Lugano, Switzerland, June 05-07, 2017_ _(CEUR Workshop Proceedings)_ , Vol. 1911. CEUR-WS.org, 52–62.  http://ceur-ws.org/Vol-1911/9.pdf