Circular codes, symmetries and transformations

Circular codes, putative remnants of primeval comma-free codes, have gained considerable attention in the last years. In fact they represent a second kind of genetic code potentially involved in detecting and maintaining the normal reading frame in protein coding sequences. The discovering of an universal code across species suggested many theoretical and experimental questions. However, there is a key aspect that relates circular codes to symmetries and transformations that remains to a large extent unexplored. In this article we aim at addressing the issue by studying the symmetries and transformations that connect different circular codes. The main result is that the class of 216 \(C^3\) maximal self-complementary codes can be partitioned into 27 equivalence classes defined by a particular set of transformations. We show that such transformations can be put in a group theoretic framework with an intuitive geometric interpretation. More general mathematical results about symmetry transformations which are valid for any kind of circular codes are also presented. Our results pave the way to the study of the biological consequences of the mathematical structure behind circular codes and contribute to shed light on the evolutionary steps that led to the observed symmetries of present codes.

1. Of course, excluding the identity.

We would like to thank Alberto Danielli for useful discussions.

Authors and Affiliations

1. Faculty of Computer Sciences, Institute of Applied Mathematics, Mannheim University of Applied Sciences, 68163 , Mannheim, Germany

   Elena Fimmel & Lutz Strüngmann

2. Department of Statistical Sciences, University of Bologna, Bologna, Italy

   Simone Giannerini & Diego Luis Gonzalez

3. CNR-IMM, Sezione di Bologna, Via Gobetti 101, Bologna, Italy

   Diego Luis Gonzalez

Corresponding author

Correspondence to Simone Giannerini.

Appendix A: Proofs

1.1 Proof of Theorem 1

Proof

We will write for a codon \(x_i\in X\, x_i=B_1^i B_2^i B_3^i, B_j^i\in \mathcal {B}, j=1,2,3\).

1. 1.

   Let us show first that \(\overleftarrow{{X}}\) is a trinucleotide circular code. The reverse codon to \(x_i\) has the form \(\overleftarrow{{x_i}}=B_3^iB_2^iB_1^i\). Assume that \(\overleftarrow{{X}}\) is not circular and the word

   $$\begin{aligned} w=\overleftarrow{{x_1}}\cdots \overleftarrow{{x_k}}=B_3^1B_2^1B_1^1\cdots B_3^kB_2^kB_1^k,\quad x_i\in X \end{aligned}$$

   has at least two decompositions into the words from \(\overleftarrow{{X}}\) written on a circle. Without lost of generality let us assume that the second decomposition occurs with a shift by 1. That means that for all \(1\le i< k\)

   $$\begin{aligned} B_2^iB_1^iB_3^{i+1}\in \overleftarrow{{X}}\quad \text{ and }\quad B_2^kB_1^kB_3^{1}\in \overleftarrow{{X}}. \end{aligned}$$

   That means that for all \(1\le i < k\)

   $$\begin{aligned} B_3^{i+1}B_1^iB_2^i\in X\quad \text{ and }\quad B_3^1 B_1^k B_2^{k}\in X. \end{aligned}$$

   So the word

   $$\begin{aligned} w'=x_kx_{k-1}\cdots x_1=B_1^k B_2^k B_3^k B_1^{k-1} B_2^{k-1} B_3^{k-1}\cdots B_1^1 B_2^1 B_3^1 \end{aligned}$$

   has at least two decompositions into the words from \(X\) with a shift by 2. Similar arguments work when the second decomposition was obtained by shift of \(2\) positions. Let us show now with a counter-example that the remaining four permutations of the bases \(\alpha \in S_3\setminus \{id, \overleftarrow{{ }}\}\) do not guarantee the circularity of \(\alpha (X)\): Let us denote the permutations

   $$\begin{aligned} p_1=(21)(3),\quad p_2=(1)(32),\quad \alpha _1=(213),\quad \alpha _2=(312) \end{aligned}$$

   and consider for example \(X=\{TAA,ATT \}\). \(X\) and \(Y:=\alpha _1(X)=\{AAT,TTA \}\) are both circular. But \(\alpha _2(X)=\alpha _1(Y)=p_1(X)=p_2(Y)=\{ATA,TAT \}\) is not circular since the word \(w=ATATAT \) has two decompositions into the words of \(X\) on a circle: \(w=ATA,TAT \) and \(w'= TAT,ATA \).

2. 2.

   Assume that \(\pi (X)\) is not circular and the word

   $$\begin{aligned} w=\pi (x_1)\cdots \pi (x_k)=\pi (B_1^1)\pi (B_2^1)\pi (B_3^1)\cdots \pi (B_1^k)\pi (B_2^k)\pi (B_3^k),\quad x_i\in X \end{aligned}$$

   has at least two decompositions into the words from \(\pi (X)\) written on a circle. Without lost of generality let us assume that the second decomposition occurs with a shift by 1. That means that for all \(1\le i < k\)

   $$\begin{aligned} \pi (B_2^{i})\pi (B_3^i)\pi (B_1^{i+1})\in \pi (X)\quad \text{ and }\quad \pi (B_2^k)\pi (B_3^k)\pi (B_1^{1})\in \pi (X). \end{aligned}$$

   It implies that for all \(1\le i < k\)

   $$\begin{aligned} B_2^{i}B_3^iB_1^{i+1}\in X\quad \text{ and }\quad B_2^kB_3^kB_1^{1}\in X. \end{aligned}$$

   In this case the word \(w'=\pi ^{-1}(w)\) has at least two decompositions into the words from \(X\) on a circle. This is a contradiction to the circularity of \(X\). Similar arguments work when the second decomposition was obtained by shift of \(2\) positions. For all \(\alpha \in S_3\) and \(\pi \in S_{\mathcal {B}}\) the property

   $$\begin{aligned} \alpha (\pi (X))=\pi (\alpha (X)) \end{aligned}$$

   is true. By the definition of a \(C^3\)-code \(X_1:=\alpha _1(X)\) and \(X_2:=\alpha _2(X)\) are trinucleotide circular codes. The arguments above show that \(\pi (X), \pi (X_1)=\alpha _1 (\pi (X))\) and \(\pi (X_2)=\alpha _2 (\pi (X))\) are circular codes. That means that \(\pi (X)\) is a \(C^3\)-code.

1.2 Proof of Theorem 2

Proof

According to the theorem above \(\pi (X)\) is circular. We prove that \(\pi (X)\) is self-complementary:

because of the self-complementarity of \(X\), the property \(\pi \circ c=c\circ \pi \) and the fact that for all \(\alpha \in S_3\) and \(\pi \in S_{\mathcal {B}}\) the property

is true.

Let us list all \(\pi \in S_{\mathcal {B}}\) satisfying \(\pi \circ c=c\circ \pi \): It is easy to prove that such maps build a subgroup of \((S_{\mathcal {B}},\circ )\). Consequently, the number of such maps must be a factor of 24. The following 8 bijective transformations have this property and build a subgroup of \((S_{\mathcal {B}},\circ )\) (easy to check):

To show that we found all \(\pi \in S_{\mathcal {B}}\) satisfying \(\pi \circ c=c\circ \pi \) and to exclude the cases of 24 or 12 elements let us add that for example for

and it cannot be that we have twelve such maps since 8 is not a factor of 12.

Each \(\pi \in S_{\mathcal {B}}\) preserves according the theorem above the circularity of \(X\). Let us show now with a counterexample that it is not the case with the self-complementarity if \(\pi \in S_{\mathcal {B}}\setminus L\) does not commute with \(c\): Consider for example the circular self-complementary code \(X:= \{CTG, CAG \}\). For

In each case we get a non-self-complementary code.

1.3 Proof of Theorem 3

Proof

Let \(\pi \) be any permutation of the set of vertices of the cuboid and take a self-complementary code \(X\). Let \(x \in X\). Then the anticodon \(\overleftarrow{{c(\pi (x))}}\) of the image of \(x\) under \(\pi \) must be contained in \(\pi (X)\), hence is of the form \(\pi (x')\) for some \(x'\in X\). Now choose a self-complementary code \(Y\) with \(X\cap Y=\{x,\overleftarrow{{c(x)}} \}\). Then again \(\overleftarrow{{c(\pi (x))}}\) must be in \(\pi (Y)\) but by assumption this can only be the case if \(\overleftarrow{{c(\pi (x))}}=\pi (\overleftarrow{{c(x)}})\), hence \(\pi \) commutes with forming the anticodon.

Last but not least assume that a permutation \(\pi \) of the set of vertices of the cuboid commutes with forming the anticodon, hence preserves self-complementarity, but is not an automorphism. It is easy to see that \(\pi \) must preserve degrees of vertices since it commutes with \({{\mathrm{ref}}}\). Thus \(\pi \) implies a permutation on the middle square which therefore has to be an automorphism of the middle square because it is assumed to commute with \({{\mathrm{rot_{180}}}}\). Again commuting with \({{\mathrm{ref}}}\) shows that also the outer squares must either be invariant or be reflected onto each other followed by an automorphism of the square.

Reprints and permissions