# Strong Trinucleotide Circular Codes

Authors: Christian J. Michel; Giuseppe Pirillo
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

Recently, we identified a hierarchy relation between trinucleotide comma-free codes and trinucleotide circular codes (see our previous works). Here, we extend our hierarchy with two new classes of codes, calledDLD and LDL codes, which are stronger than the comma-free codes. We also prove that no circular code with 20 trinucleotides is a DLD code and that a circular code with 20 trinucleotides is comma-free if and only if it is a LDL code. Finally, we point out the possible role of the symmetric group ∑4 in the mathematical study of trinucleotide circular codes.


---

## Body

## 1. Introduction

We continue our study of the combinatorial properties of trinucleotide circular codes. A trinucleotide is a word of three letters (triletter) on the genetic alphabet{A,C,G,T}. The set of 64 trinucleotides is a code in the sense of language theory, more precisely a uniform code but not a circular code (Remark 2.4 and [1, 2]). In order to have an intuitive meaning of these notions, codes are written on a straight line while circular codes are written on a circle, but, in both cases, unique decipherability is required. Circular codes are some particular subsets of the 64 trinucleotide set while comma-free codes are even more constrained subsets.In the past 50 years, comma-free codes and circular codes have been studied in theoretical biology, mainly to understand the structure and the origin of the genetic code as well as the reading frame (construction) of genes, for example [3–5]. Before the discovery of the genetic code, Crick et al. [3] proposed a (maximal) comma-free code of 20 trinucleotides for coding the 20 amino acids. In 1996, a (maximal) circular code X0 of 20 trinucleotides was identified statistically on two large and different gene populations, eukaryotes, and prokaryotes [6]. During the last years, circular codes are mathematical objects studied in discrete mathematics, theoretical computer science, and theoretical biology, for example [7–22]. In particular, in theory of codes, there are some unexpected common notions between variable length circular codes and trinucleotide circular codes [17, 19, 21, 22].Recently, we proposed a hierarchy relation between the trinucleotide comma-free codes and the trinucleotide circular codes (Proposition 3 in [23]). More precisely, all the trinucleotide codes in this hierarchy are circular, the strongest ones being comma-free. In this paper, we identify two new classes of trinucleotide circular codes which are stronger than the comma-free codes.We introduce here the following new notions. A setX of trinucleotides has the property DLD if for any trinucleotides t,t′∈X, no letter occurs both as a proper suffix of t and a proper prefix of t′. A set X of trinucleotides has the property LDL if for any trinucleotides t,t′∈X, no diletter occurs both as a proper suffix of t and a proper prefix of t′. These sets DLD and LDL are not only trinucleotides circular codes but they are also stronger than the comma-free codes (Propositions 3.4 and 3.5, and Remarks 3.6 and 3.7). We also prove that no circular code with 20 trinucleotides is a DLD code (Proposition 3.10) and that a circular code with 20 trinucleotides is comma-free if and only if it is a LDL code (Proposition 3.11).Therefore, our previous hierarchy (Proposition 3 in [23] recalled in Proposition 2.17 below) is extended with these new DLD and LDL classes of strong trinucleotides circular codes (Proposition 4.1).Finally, a curious relation with the symmetric groupΣ4 appears again. The tables given here and the other symmetric relations identified previously (e.g., Proposition 6 in [23]) suggest that the symmetric group Σ4 can play an important role in the mathematical study of these trinucleotide circular codes. However, we have no formal mathematical explanation so far.


## 2. Preliminaries

Let𝒜 denote a finite alphabet, 𝒜* the free monoid over 𝒜 and 𝒜+ the free semigroup over 𝒜. The elements of 𝒜* are words and the empty word, denoted by ε, is the identity of 𝒜*. Given a subset X of 𝒜*, Xn is the set of the words over 𝒜 which are the products of n words from X, that is, Xn={x1x2⋯xn∣xi∈X}. If X is a (finite) set, then |X| denotes its cardinality and if u is a word, then |u| denotes its length. A word u is a factor of a word v if there exist two words u′ and u′′ such that v=u′uu′′. When u′=ε (resp. u′′=ε), u is a prefix (resp. suffix) of v. A proper factor (resp. proper prefix, proper suffix) u of v is a factor (resp. prefix, suffix) u of v such that |u|<|v|.There is a correspondence between the genetic and language-theoretic concepts. The letters (or nucleotides or bases) define the genetic alphabet𝒜4={A,C,G,T}. The set of nonempty words (resp. words) over 𝒜4 is denoted by 𝒜4+ (resp. 𝒜4*). The set of the 16 words of length 2 (or dinucleotides or diletters) is denoted by 𝒜42. The set of the 64 words of length 3 (or trinucleotides or triletters) is denoted by 𝒜43. The total order over the alphabet 𝒜4 is A<C<G<T. Consequently, 𝒜4+ is lexicographically ordered: given two words u,v∈𝒜4+, u is smaller than v in lexicographical order, written u<v, if and only if either u is a proper prefix of v or there exist x,y∈𝒜4, x<y, and r,s,t∈𝒜4* such that u=rxs and v=ryt.Definition 2.1.
Code: a subsetXof𝒜+ is a code over 𝒜 if for each x1,…,xn,x1′,…,xm′∈X,n,m≥1, the condition x1⋯xn=x1′⋯xm′ implies n=m and xi=xi′ for i=1,…,n.For anyk-letter alphabet, k≥1, and for any word length l, l≥1, 𝒜kl is a code. In particular, 𝒜43 is a code. More precisely, it is a uniform code [1]. Consequently, any nonempty subset of 𝒜43 is a code, called trinucleotide code in this paper.Definition 2.2.
Trinucleotide comma-free code: a trinucleotide codeX⊂𝒜43 is comma-free if for each y∈X and u,v∈𝒜4* such that uyv=x1⋯xn with x1,…,xn∈X,n≥1,it results that u,v∈X*.Several varieties of trinucleotide comma-free codes were described in [18].Definition 2.3.
Trinucleotide circular code: a trinucleotide codeX⊂𝒜43 is circular if for each x1,…,xn,x1′,…,xm′∈X,n,m≥1,p∈𝒜4*,s∈𝒜4+,the conditions sx2⋯xnp=x1′⋯xm′ and x1=ps imply n=m,p=ε and xi=xi′ for i=1,…,n.Remark 2.4.
𝒜43 is obviously not a circular code and even less a comma-free code. However, several subsets of 𝒜43 are trinucleotide circular codes (e.g., Propositions 2.12 and 2.13).Definition 2.5.
Maximal trinucleotide circular code: a trinucleotide circular codeX⊂𝒜43 is maximal if for each x∈𝒜43,x∉X,X∪{x} is not a trinucleotide circular code.Definition 2.6.
A trinucleotide circular code containing exactlyk elements is called a k-trinucleotide circular code.Remark 2.7.
A 20-trinucleotide circular code is(i)
maximal (in the sense that it cannot be contained in a trinucleotide circular code with more words);(ii)
maximum (in the sense that no trinucleotide circular code can contain more than 20 words).We now recall some definitions and previous results related to the trinucleotide circular code necklaces. In the sequel,l1,l2,…,ln are letters in 𝒜4, d1,d2,…,dn are diletters in 𝒜42, and n is an integer satisfying n≥2.Definition 2.8.
Letter Diletter Necklaces (LDN): we say that the ordered sequence l1,d1,l2,d2,…,dn-1,ln,dn is an nLDN for a subset X⊂𝒜43 if l1d1,l2d2,…,lndn∈X and d1l2,d2l3,…,dn-1ln∈X.Definition 2.9.
Letter Diletter Continued Necklaces (LDCN): we say that the ordered sequence l1,d1,l2,d2,…,dn-1,ln,dn,ln+1 is an (n+1)LDCN for a subset X⊂𝒜43 if l1d1,l2d2,…,lndn∈X and d1l2,d2l3,…,dn-1ln,dnln+1∈X.Definition 2.10.
Diletter Letter Necklaces (DLN): we say that the ordered sequence d1,l1,d2,l2,…,ln-1,dn,ln is an nDLN for a subset X⊂𝒜43 if d1l1,d2l2,…,dnln∈X and l1d2,l2d3,…,ln-1dn∈X.Definition 2.11.
Diletter Letter Continued Necklaces (DLCN): we say that the ordered sequence d1,l1,d2,l2,…,ln-1,dn,ln,dn+1 is an (n+1)DLCN for a subset X⊂𝒜43 if d1l1,d2l2,…,dnln∈X and l1d2,l2d3,…,ln-1dn,lndn+1∈X.Proposition 2.12 (see [17]).
LetX be a trinucleotide code. The following conditions are equivalent:(i)
X is a circular code;(ii)
X has no 5LDCN.Proposition 2.13 (see [18]).
LetX be a trinucleotide code. The following conditions are equivalent:(i)
X is a comma-free code.(ii)
X has no 2LDN and no 2DLN.Definition 2.14.
LetX be a trinucleotide code. For any integer n∈{2,3,4,5}, we say that X belongs to the class CnLDN if X has no nLDN and that X belongs to the class CnDLN if X has no nDLN. Similarly, for any integer n∈{3,4,5}, we say that X belongs to the class CnLDCN if X has no nLDCN and that X belongs to the class CnDLCN if X has no nDLCN.Notation 1.
For any integern∈{2,3,4,5}, In=CnLDN∩CnDLN and Un=CnLDN∪CnDLN. Similarly, for any integer n∈{3,4,5}, InC=CnLDCN∩CnDLCN and UnC=CnLDCN∪CnDLCN.Proposition 2.15 (see [23]).
The following chains of inclusions hold:(i)
C2LDN⊂C3LDCN⊂C3LDN⊂C4LDCN⊂C4LDN⊂C5LDCN⊂C5LDN;(ii)
C2DLN⊂C3DLCN⊂C3DLN⊂C4DLCN⊂C4DLN⊂C5DLCN⊂C5DLN;(iii)
C2LDN⊂C3DLCN⊂C3LDN⊂C4DLCN⊂C4LDN⊂C5DLCN⊂C5LDN;(iv)
C2DLN⊂C3LDCN⊂C3DLN⊂C4LDCN⊂C4DLN⊂C5LDCN⊂C5DLN;(v)
I2⊂I3C⊂I3⊂I4C⊂I4⊂I5C⊂I5;(vi)
U2⊂U3C⊂U3⊂U4C⊂U4⊂U5C⊂U5.Remark 2.16.
By Proposition2.13, the chain of inclusions of Proposition 2.15 (v) begins with I2 which is the class of comma-free codes.Proposition 2.17.
With 20-trinucleotide circular codes, the following chains of inclusions and equalities hold:(2.1)I2⊂U2=I3C⊂U3C=I3⊂U3=I4C⊂U4C=I4⊂U4=I5C⊂U5C=I5=U5.


## 3. Strong Trinucleotide Circular Codes

We introduce new definitions which impose very strong conditions on the words of a subset of𝒜43. These word subsets, strongly constrained, are indeed new circular codes which are stronger than the trinucleotide comma-free codes according to the following propositions.Definition 3.1.
A subsetX of 𝒜43 has the DLD property if, for any l1,l2,l3,l1′,l2′,l3′∈𝒜4, the conditions l1l2l3∈X and l1′l2′l3′∈X imply l1≠l3′.No letter of𝒜4 can occur in the first position of a trinucleotide of X when it is also in the last position of another trinucleotide of X.Definition 3.2.
A subsetX of 𝒜43 has the LDL property if, for any l1,l1′∈𝒜4, d1,d1′∈𝒜42, the conditions l1d1∈X and d1′l1′∈X imply d1≠d1′.No diletter of𝒜42 can occur as a prefix of a trinucleotide of X when it is also a suffix of another trinucleotide of X.Remark 3.3.
The trinucleotide code{ACG,GTA} is not a DLD-strong trinucleotide circular code but it is a LDL-strong trinucleotide circular code. The trinucleotide code {ACG,CGT} is not a LDL-strong trinucleotide circular code but it is a DLD-strong trinucleotide circular code.Therefore, the class ofDLD-strong trinucleotide circular codes is different from the class of LDL-strong trinucleotide circular codes. However, both are very particular cases of comma-free codes according to the following propositions.Proposition 3.4.
ADLD-strong trinucleotide circular code over 𝒜4 is comma-free.Proof.
Suppose thatX is a DLD-strong trinucleotide circular code and, by way of contradiction, that it is not comma-free. Then, there exist two trinucleotides xyz,x′y′z′∈X such that either yzx′ or zx′y′ are in X. In the first case, x′ is a prefix of x′y′z′ and a suffix of yzx′ while in the second case, z is a prefix of zx′y′ and a suffix of xyz. In both cases, X is not a DLD-strong circular code. This is a contradiction.Proposition 3.5.
ALDL-strong trinucleotide circular code over 𝒜4 is comma-free.Proof.
Suppose thatX is a LDL-strong trinucleotide circular code and, by way of contradiction, that it is not comma-free. Then, there exist two trinucleotides xyz,x′y′z′∈X such that either yzx′ or zx′y′ are in X. In the first case, yz is a prefix of yzx′ and a suffix of xyz while in the second case, x′y′ is a prefix of x′y′z′ and a suffix of zx′y′. In both cases, X is not a LDL-strong circular code. This is a contradiction.Remark 3.6.
There are trinucleotide comma-free codes which are notDLD-strong trinucleotide circular codes. Example: {ACA}.Remark 3.7.
There are trinucleotide comma-free codes which are notLDL-strong trinucleotide circular codes. Example: {ACG,CGT}.The two following propositions are obvious.Proposition 3.8.
For any lettersx,y,z∈𝒜4, a trinucleotide singleton xyz∈𝒜43 is a DLD-strong trinucleotide circular code over 𝒜4 if and only if x≠z.Proposition 3.9.
For any lettersx,y,z∈𝒜4, a trinucleotide singleton xyz∈𝒜43 is a LDL-strong trinucleotide circular code over 𝒜4 if and only if at least two of its letters are different.Remark3.3 showed that DLD-strong and LDL-strong trinucleotide circular codes are different classes. The following propositions give more information about their difference.Proposition 3.10.
No 20-trinucleotide circular code can be aDLD-strong trinucleotide circular code.Proof.
Suppose, by way of contradiction, that a 20-trinucleotide circular codeX is also a DLD-strong trinucleotide circular code. Let P (resp. S) be the set containing the letters l1 (resp. l3) of the trinucleotides l1l2l3 of X. We have P∩S=∅ (otherwise, X has not the DLD property), |P|>1 (otherwise, X has at most 16 elements) and |S|>1 (otherwise, X has at most 16 elements). Using Pigeon Hole Principle, it follows that 𝒜4 has two disjoint subsets, say {a,b} and {c,d}, such that P={a,b} and S={c,d}. Consequently, X has at most the following elements: aAc,aCc,aGc,aTc,aAd,aCd,aGd,aTd,bAc,bCc,bGc,bTc,bAd,bCd,bGd,bTd, so we have again at most 16 elements. This is a contradiction.Proposition 3.11.
A 20-trinucleotide circular code is comma-free if and only if it is aLDL-strong trinucleotide circular code.Proof.
If. By Proposition 3.5, any LDL-strong trinucleotide circular code X is also comma-free.
Only if. Suppose that X is comma-free and, by way of contradiction, that it is not a LDL-strong trinucleotide circular code. Then, there exist two letters a,b∈𝒜4 and a diletter d1∈𝒜42 such that ad1,d1b∈X. As X cannot contain two elements in the same conjugation class, the condition a≠b holds. So, 𝒜4-{a,b} contains exactly two elements, say c and d.
X being a comma-free code, X must contain exactly one trinucleotide in each of the 20 conjugation classes. By considering the conjugation class {aac,aca,caa}, only aac can belong to X. Indeed, {aca,ad1,d1b} and {caa,ad1,d1b} are not comma-free codes as the concatenations aca.d1b and caa.d1b lead to ad1 in contradiction with Definition 2.2. With the conjugation class {bbc,bcb,cbb}, only cbb can belong to X. Indeed, {bbc,ad1,d1b} and {bcb,ad1,d1b} are not comma-free codes as the concatenations ad1.bbc and ad1.bcb lead to d1b in contradiction with Definition 2.2. Similarly, aad and dbb must belong to X. Moreover, with the conjugation class {acb,cba,bac}, only acb can belong to X.
Now, we have:(i)
acd∉X (otherwise {aac,acd,dbb} is not a comma-free code);(ii)
cda∉X (otherwise {cda,acb,cbb} is not a comma-free code);(iii)
dac∉X (otherwise {aad,dac,acb} is not a comma-free code).So, no element in the conjugation class {acd,cda,dac} belongs to X. This is a contradiction.


## 4. Extended Hierarchy

The previous hierarchy of trinucleotide circular codes [23] is now extended with these new DLD and LDL codes. By Proposition 3.10, the set of DLD-strong 20-trinucleotide circular codes is empty. Moreover, by Proposition 3.11, the set of LDL-strong 20-trinucleotide circular codes coincide with the set of trinucleotide comma-free codes (set I2). With the notations In and Un (Notation 1), the hierarchy of the above recalled Proposition 2.17 is extended with these new strong trinucleotide circular codes as follows.Proposition 4.1.
With the 20-trinucleotide circular codes, the following chains of inclusions and equalities hold:(4.1)∅=LDL∩DLD⊂LDL∪DLD=LDL=I2⊂U2=I3C⊂U3C=I3⊂U3=I4C⊂U4C=I4⊂U4=I5C⊂U5C=I5=U5.


## 5. Coding of Trinucleotide Circular Codes with the Symmetric GroupΣn

We use the symmetric groupΣn (e.g., [24]) to develop a coding of trinucleotide circular codes.Apermutation of a set X is a bijection σ from X into itself. Given a positive integer n, [n] denotes the set {0,1,…,n-1}. As [n] has a natural total order 0<1<⋯<n-1, a permutation σ of [n] is the word σ(0)σ(1)⋯σ(n-1) giving the successive images of the elements of [n]. Analogously, {a[n]} denotes any totally ordered set {a0,a1,…,an-1}, a0<a1<⋯<an-1, of n elements. Also as a consequence of the total order, a permutation σ of {a[n]} is the word aσ(0)aσ(1)…aσ(n-1) and by abuse of language, σ can also be considered as a permutation of [n]. The symmetric group Σn denotes all the permutations of {a[n]}.Recall that|X| denotes the number of elements of a set X. Recall that if w=w(0)w(1)⋯w(k-1) is a word of length k on the alphabet 𝒜, then Alph(w)={w(0),w(1),…,w(k-1)}. So, Alph(w) is the set of the letters of 𝒜 having at least one occurrence in w.A permutation of{a[n]} can be represented by a word of length n-1. Clearly, the prefix of length n-1 of the word aσ(0)…aσ(n-1) uniquely determines σ. There are also four other cases to represent the elements of Σn by words of length n-1: i<j and σ(i)<σ(j); i<j and σ(i)>σ(j); i>j and σ(i)<σ(j); i>j and σ(i)>σ(j). We begin with the case i<j and σ(i)>σ(j).For a givenh∈[n-1], {a[h]} denotes the subset of [n-1] containing its first h elements a0,…,ah-1. For a given i∈[n] and for a permutation σ of {a[n]}, the set riσ is defined as follows: riσ={a[σ(i)]}∩Alph(aσ(i+1)⋯aσ(n-1)) contains the elements of {a[σ(i)]}={a0,…,aσ(i)-1} having one occurrence in aσ(i+1)⋯aσ(n-1), the suffix of length n-i-1 of aσ(0)⋯aσ(n-1). Consequently, |riσ| counts the number of elements j of [n] such that i<j and aσ(i)>aσ(j). In other words, |riσ| counts the number of elements ak of {a[n]} such that ak<aσ(i) and ak is on the right of aσ(i) in the word aσ(0)⋯aσ(n-1). Put r(i)=|riσ| and let the code of σ be the word r(0)r(1)⋯r(n-1) denoted by r(σ).For a given permutationσ, r(0) is the number of the letters of aσ(0)⋯aσ(n-1) that are strictly smaller than aσ(0) or equivalently, the number of the elements of the alphabet {a[n]} that are strictly smaller than the leftmost letter aσ(0), and by the choice of the alphabet, this number is exactly σ(0) and belongs to [n-0]=[n]. Then, r(1) is the number of the letters of aσ(0)⋯aσ(n-1) that are strictly smaller than aσ(1) and on the right of aσ(1) or equivalently, the number of the elements of the alphabet {a[n]}-{σ(0)} that are strictly smaller than aσ(1) and this number belongs to [n-1]. And so on until r(n-2) which is the number of the letters of aσ(0)⋯aσ(n-1) that are strictly smaller than aσ(n-2) and on the right of aσ(n-2) or equivalently, the number of the elements of the two-letter alphabet {a[n]}-{σ(0),…,σ(n-3)}={σ(n-2),σ(n-1)} that are strictly smaller than aσ(n-2) and this number belongs to [n-(n-2)]=[2], that is, with only values 0 or 1. Finally, r(n-1) is the number of the letters of aσ(0)⋯aσ(n-1) that are strictly smaller than aσ(n-1) and on the right of aσ(n-1) or equivalently, the number of the elements of the one-letter alphabet {a[n]}-{σ(0),…,σ(n-2)}={σ(n-1)} that are strictly smaller than aσ(n-1) and this number belongs to [n-(n-1)]=[1], that is, with value equal to 0. Thus, r(0)∈[n],r(1)∈[n-1],…,r(i)∈[n-i] and r(0)r(1)⋯r(n-1) belongs to a set of cardinality n! which is exactly the cardinality of Σn.Clearly, ifσ and τ are two different permutations of {a[n]}, then r(σ)≠r(τ). Indeed, let k be the maximum integer such that aσ(k)=aτ(k). Without loss of generality, suppose that aσ(k+1)<aτ(k+1). As Alph(aσ(k+1)⋯aσ(n-1))=Alph(aτ(k+1)⋯aτ(n-1)), then |rk+1σ|<|rk+1τ|. So, r(σ) is different from r(τ).Example 5.1.
The code of the permutationσ=a4a6a2a1a3a0a5 of {a[7]} is r(σ)=452110.The correspondenceρ:σ→r(σ) is an injective map between two finite sets of same cardinality (n!). So ρ is a bijection and to each r(σ) corresponds a unique σ. The following algorithm allows the permutation σ from the code r(σ) to be retrieved.Algorithm 1 (principle).
Initialisationaσ(0)=ar(0); only one element, say aα, in {a[n]}-{aσ(0)} can verify r(1)=|{aζ∈{a[n]}-{aσ(0)}∣aα>aζ}|, so aσ(1)=aα; only one element, say aβ, in {a[n]}-{aσ(0),aσ(1)} can verify r(2)=|{aζ∈{a[n]}-{aσ(0),aσ(1)}∣aβ>aζ}|, so aσ(2)=aβ; repeat this procedure until all the elements {aσ(0),…,aσ(n-2)} are found; finally aσ(n-1) is the unique value in {a[n]}-{aσ(0),…,aσ(n-2)}.Remark 5.2.
In general,r(i+1)⋯r(n-1) is the code of the permutation aσ(i+1)⋯aσ(n-1) on the totally ordered alphabet {aσ(i+1),…,aσ(n-1)}.Example 5.3.
Consider the previous example with the permutationσ of {a[7]} having the code r(σ)=452110. As r(0)=4, then aσ(0)=a4; aσ(1)=a6 as {a0,a1,a2,a3,a5,a6} contains r(1)=5 elements strictly smaller; aσ(2)=a2 as {a0,a1,a2,a3,a5} contains r(2)=2 elements strictly smaller; aσ(3)=a1 as {a0,a1,a3,a5} contains r(3)=1 element strictly smaller; aσ(4)=a3 as {a0,a3,a5} contains r(4)=1 element strictly smaller; aσ(5)=a0 as {a0,a5} contains r(5)=0 element strictly smaller; finally, aσ(6)=a5 as {a[7]}-{aσ(0),aσ(1),aσ(2),aσ(3),aσ(4),aσ(5)}={a[7]}-{a4,a6,a2,a1,a3,a0}={a5}. So, the permutation σ is a4a6a2a1a3a0a5.For a given permutationσ, we can also define the sets liσ={a[σ(i)]}∩Alph(aσ(0)⋯aσ(i)-1), Riσ=({a[n]}-{a[σ(i)+1]})∩Alph(aσ(i+1)⋯aσ(n-1)) and Liσ=({a[n]}-{a[σ(i)+1]})∩Alph(aσ(0)⋯aσ(n-1)). The set liσ consists of the elements of {a[σ(i)]}={aσ(0),…,aσ(i)-1} that have one occurrence in the prefix of length i of aσ(0)⋯aσ(n-1). Its cardinality |liσ| counts the number of elements j of [n] such that j<i and σ(j)<σ(i) or, in other words, |liσ| counts the number of elements ak of {a[n]} such that ak<aσ(i) and ak is on the left of aσ(i) in aσ(0)⋯aσ(n-1). Similarly, the set Riσ consists of the elements of {a[n]}-{a[σ(i)+1]}={aσ(i)+1,…,an-1} that have one occurrence in aσ(i+1)⋯aσ(n-1), the suffix of length n-i-1 of aσ(0)⋯aσ(n-1). Its cardinality |Riσ| counts the number of elements j of [n] such that j>i and σ(j)>σ(i) or, in other words, |Riσ| counts the number of elements ak of {a[n]} such that ak>aσ(i) and ak is on the right of aσ(i) in aσ(0)⋯aσ(n-1). Finally, the set Liσ consists of the elements of {a[n]}-{a[σ(i)+1]}={aσ(i)+1,…,an-1} that have one occurrence in the prefix of length i of aσ(0)⋯aσ(n-1). Its cardinality |Liσ| counts the number of elements j of [n] such that j<i and σ(j)>σ(i) or, in other words, |Liσ| counts the number of elements ak of {a[n]} such that ak>aσ(i) and ak is on the left of aσ(i) in aσ(0)⋯aσ(n-1).There are trivial relations(5.1)liσ+Liσ=i,riσ+Riσ=n-i-1,riσ+liσ=σ(i),Riσ+Liσ=n-σ(i)-1.For a given permutation,liσ, Riσ, and Liσ allow the construction of three other codes, namely, l(0)l(1)⋯l(n-1), R(0)R(1)⋯R(n-1) and L(0)L(1)⋯L(n-1), which have similar properties to the code r(0)r(1)⋯r(n-1). These relations can retrieve more efficiently the permutation σ from the code r(σ). For the interesting case n=4 of this paper, an efficient algorithm is given.Algorithm 2 (principle).
Initialisationaσ(0)=ar(0); Consider {σ(1),σ(2),σ(3)} and let {σ(1),σ(2),σ(3)}={α,β,γ} with α<β<γ.
Ifr(1)=2, then aσ(1)=aγ and, if r(2)=1, then aσ(2)aσ(3)=aβaα or, if r(2)=0, then aσ(2)aσ(3)=aαaβ.
Ifr(1)=1, then aσ(1)=aβ and, if r(2)=1, then aσ(2)aσ(3)=aγaα or, if r(2)=0, then aσ(2)aσ(3)=aαaγ.
Ifr(1)=0, then aσ(1)=aα and, if r(2)=1, then aσ(2)aσ(3)=aγaβ or, if r(2)=0, then aσ(2)aσ(3)=aβaγ.
The numberr(1)r(2) is the code of the permutation aσ(α)aσ(β)aσ(γ) on {aα,aβ,aγ}.Example 5.4.
Consider the permutationσ of {a[4]} having 111 as its code. Clearly, aσ(0)=a1. Then, the considered set {σ(1),σ(2),σ(3)}={α,β,γ} is {a0,a2,a3}. As r(1)=1, then aσ(1)=aβ=a2 and as r(2)=1, then aσ(2)aσ(3)=aγaα=a3a0. So, the permutation σ is a1a2a3a0.Finally, the code of a permutationσ(A)σ(C)σ(G)σ(T) on the genetic alphabet 𝒜4 (A<C<G<T) can easily be computed by putting A=a0, C=a1, G=a2 and T=a3. Similarly, for the totally ordered alphabet {a,b,c,d} (a<b<c<d) in Section 5, the code of a permutation is obtained by putting a=a0, b=a1, c=a2 and d=a3.


## 6. Role of the Symmetric GroupΣ4

We puta=A, b=C, c=G and d=T and identify the elements of the symmetric group Σ4 over {a,b,c,d} (a<b<c<d) with the 24 permutations of the word abcd. We denote the permutations by their codes (Table 1(c)).Table 1
(a) The first column contains the permutationsσ of the symmetric group Σ2 on the alphabet {a[2]}={a0,a1} and the second column contains their codes r(σ). (b) The first column contains the permutations σ of the symmetric group Σ3 on the alphabet {a[3]}={a0,a1,a2} and the second column their codes r(σ). (c) The first column contains the permutations σ of the symmetric group Σ4 on the alphabet {a[4]}={a0,a1,a2,a3} and the second column contains their codes r(σ). This table easily allows to determine the codes for permutations on any other totally ordered four-letter alphabet, in particular the alphabet [4]={0,1,2,3} (0<1<2<3), the genetic alphabet 𝒜4 (A<C<G<T) and the alphabet {a,b,c,d} (a<b<c<d). For example, 211 is the code for 2130 on the alphabet [4], for GCTA on the alphabet 𝒜4 and for cbda on the alphabet {a,b,c,d}.
(a)PermutationσCoder(σ)a0a10a1a01(b)PermutationσCoder(σ)a0a1a200a0a2a101a1a0a210a1a2a011a2a0a120a2a1a021(c)PermutationσCoder(σ)a0a1a2a3000a0a1a3a2001a0a2a1a3010a0a2a3a1011a0a3a1a2020a0a3a2a1021a1a0a2a3100a1a0a3a2101a1a2a0a3110a1a2a3a0111a1a3a0a2120a1a3a2a0121a2a0a1a3200a2a0a3a1201a2a1a0a3210a2a1a3a0211a2a3a0a1220a2a3a1a0221a3a0a1a2300a3a0a2a1301a3a1a0a2310a3a1a2a0311a3a2a0a1320a3a2a1a0321We wish to point out that a computer calculus confirms that the 20-trinucleotide comma-free codes are exactly theLDL-strong 20-trinucleotide circular codes. These codes are partitioned into 28 classes: C1,C2,…,C28. There are four classes containing six codes each (Table 2(a)), 16 classes containing 12 codes each (Table 2(b)), and eight classes containing 24 codes each (Table 2(c)). For each class, we give explicitely the list (in lexicographical order) of trinucleotides: the first (in lexicographical order) LDL-strong 20-trinucleotide circular code X (pattern of the class) and the codes of the permutations of Σ4 (Table 1(c)) on X giving the other LDL-strong 20-trinucleotide circular codes of the class. The classes are lexicographically ordered according to the patterns of classes.Table 2
(a) The four classes having each sixLDL-strong 20-trinucleotide circular codes. Each class is described by its pattern and the five codes of the permutations of the symmetric group Σ4 on the pattern allow the other five LDL-strong 20-trinucleotide circular codes of the class to be deduced. (b) The 16 classes having each 12 LDL-strong 20-trinucleotide circular codes. Each class is described by its pattern and the 11 codes of the permutations of the symmetric group Σ4 on the pattern allow the other 11 LDL-strong 20-trinucleotide circular codes of the class to be deduced. (c) The eight classes having each 24 LDL-strong 20-trinucleotide circular codes. In this case, each class is only described by its pattern as the other 23 LDL-strong 20-trinucleotide circular codes are obtained with the 23 permutations of the symmetric group Σ4.
(a)C1:aab,aac,aad,bab,bac,bad,bbc,bda,bdb,bdc,cab,cac,cad,ccb,cda,cdb,cdc,dda,ddb,ddcCodes ofC1:211,220,221,301,320C2:aab,aac,aad,bab,bac,bad,bca,bcb,bcd,bdd,cca,ccb,ccd,dab,dac,dad,dbb,dca,dcb,dcdCodes ofC2:201,221,311,320,321C3:aab,aca,acb,acc,ada,adb,add,bba,bca,bcb,bcc,bda,bdb,bdd,cda,cdb,cdd,dca,dcb,dccCodes ofC3:120,121,310,311,321C4:aba,abb,abc,acc,ada,adc,add,bda,bdc,bdd,caa,cba,cbb,cbc,cda,cdc,cdd,dba,dbb,dbcCodes ofC4:201,221,311,320,321(b)C5:aab,aac,aad,bab,bac,bad,bbc,bbd,cab,cac,cad,cbc,cbd,ccd,dab,dac,dad,dbc,dbd,ddcCodes ofC5:020,021,101,120,121,300,301,310,311,320,321C6:aab,aac,aad,bab,bac,bad,bbc,bbd,cab,cac,cad,cbc,cbd,cdb,cdc,dab,dac,dad,ddb,ddcCodes ofC6:011,020,201,220,221,300,301,310,311,320,321C7:aab,aac,aad,bab,bac,bad,bbc,bbd,cab,cac,cad,cbc,cbd,cdd,dab,dac,dad,dbc,dbd,dccCodes ofC7:020,021,101,120,121,300,301,310,311,320,321C8:aab,aac,aad,bab,bac,bad,bbc,bda,bdb,bdc,cab,cac,cad,cbc,cda,cdb,cdc,dda,ddb,ddcCodes ofC8:111,120,121,211,220,221,300,301,310,320,321C9:aab,aac,aad,bab,bac,bad,bbc,bdb,bdc,bdd,cab,cac,cad,ccb,cdb,cdc,cdd,dab,dac,dadCodes ofC9:011,021,200,201,210,211,220,221,301,320,321C10:aab,aac,aad,bab,bac,bad,bca,bcb,bcd,bdb,bdd,cca,ccb,ccd,dab,dac,dad,dca,dcb,dcdCodes ofC10:110,111,121,200,201,211,220,221,311,320,321C11:aab,aac,aad,bab,bac,bad,bcb,bcc,bcd,bdd,cab,cac,cad,dab,dac,dad,dbb,dcb,dcc,dcdCodes ofC11:011,020,201,220,221,300,301,310,311,320,321C12:aab,aac,aad,bab,bac,bad,bcb,bcc,bdb,bdd,cab,cac,cad,cdb,cdd,dab,dac,dad,dcb,dccCodes ofC12:020,021,101,120,121,300,301,310,311,320,321C13:aab,aac,ada,adb,adc,add,bab,bac,bbc,bda,bdb,bdc,bdd,cab,cac,ccb,cda,cdb,cdc,cddCodes ofC13:011,021,200,201,210,211,220,221,301,320,321C14:aab,aac,ada,adb,adc,add,bab,bac,bca,bcb,bda,bdb,bdc,bdd,cca,ccb,cda,cdb,cdc,cddCodes ofC14:110,111,121,200,201,211,220,221,311,320,321C15:aab,aac,ada,adb,adc,add,bab,bac,bcc,bda,bdb,bdc,bdd,cab,cac,cbb,cda,cdb,cdc,cddCodes ofC15:011,021,200,201,210,211,220,221,301,320,321C16:aab,aca,acb,acc,acd,ada,adb,add,bba,bca,bcb,bcc,bcd,bda,bdb,bdd,dca,dcb,dcc,dcdCodes ofC16:101,110,111,120,121,210,211,221,310,311,321C17:aab,aca,acb,acc,ada,adb,add,bab,bca,bcb,bcc,bda,bdb,bdd,cda,cdb,cdd,dca,dcb,dccCodes ofC17:020,021,101,120,121,300,301,310,311,320,321C18:aba,abb,abc,abd,aca,acc,acd,add,cba,cbb,cbc,cbd,daa,dba,dbb,dbc,dbd,dca,dcc,dcdCodes ofC18:111,120,121,211,220,221,300,301,310,320,321C19:aba,abb,abc,abd,aca,acc,ada,add,cba,cbb,cbc,cbd,cda,cdd,dba,dbb,dbc,dbd,dca,dccCodes ofC19:020,021,101,120,121,300,301,310,311,320,321C20:aba,abb,abc,aca,acc,ada,adc,add,bda,bdc,bdd,cba,cbb,cbc,cda,cdc,cdd,dba,dbb,dbcCodes ofC20:011,020,201,220,221,300,301,310,311,320,321(c)C21:aab,aac,aad,bab,bac,bad,bbc,bbd,cab,cac,cad,cbc,cbd,ccd,dab,dac,dad,dbc,dbd,dcdC22:aab,aac,aad,bab,bac,bad,bbc,bbd,cab,cac,cad,cbc,cbd,cdc,cdd,dab,dac,dad,dbc,dbdC23:aab,aac,aad,bab,bac,bad,bbc,bdb,bdc,bdd,cab,cac,cad,cbc,cdb,cdc,cdd,dab,dac,dadC24:aab,aac,aad,bab,bac,bad,bcb,bcc,bcd,bdb,bdd,cab,cac,cad,dab,dac,dad,dcb,dcc,dcdC25:aab,aac,ada,adb,adc,add,bab,bac,bbc,bda,bdb,bdc,bdd,cab,cac,cbc,cda,cdb,cdc,cddC26:aab,aac,ada,adb,adc,add,bab,bac,bcb,bcc,bda,bdb,bdc,bdd,cab,cac,cda,cdb,cdc,cddC27:aab,aca,acb,acc,acd,ada,adb,add,bab,bca,bcb,bcc,bcd,bda,bdb,bdd,dca,dcb,dcc,dcdC28:aba,abb,abc,abd,aca,acc,acd,ada,add,cba,cbb,cbc,cbd,dba,dbb,dbc,dbd,dca,dcc,dcdTable 3
The prefixes and suffixes of the pattern of the 28 classes ofLDL-strong 20-trinucleotide circular codes (Tables 2(a)–2(c)). For each pattern X, the subset L1 (resp. L3) of {a,b,c,d} consists of the letters l1 (resp. l3) that appear at least once in prefix (resp. suffix) position of the trinucleotides of X. Similarly, the subset D1 (resp. D2) of {a,b,c,d}2 consists of the diletters d1 (resp. d2) that appear at least once in prefix (resp. suffix) position of the trinucleotides of X.
CodesL1L3D1D2C1a,b,c,da,b,c,daa,ba,bb,bd,ca,cc,cd,ddab,ac,ad,bc,cb,da,db,dcC2a,b,c,da,b,c,daa,ba,bc,bd,cc,da,db,dcab,ac,ad,bb,ca,cb,cd,ddC3a,b,c,da,b,c,daa,ac,ad,bb,bc,bd,cd,dcab,ba,ca,cb,cc,da,db,ddC4a,b,c,da,b,c,dab,ac,ad,bd,ca,cb,cd,dbaa,ba,bb,bc,cc,da,dc,ddC5a,b,c,db,c,daa,ba,bb,ca,cb,cc,da,db,ddab,ac,ad,bc,bd,cd,dcC6a,b,c,db,c,daa,ba,bb,ca,cb,cd,da,ddab,ac,ad,bc,bd,db,dcC7a,b,c,db,c,daa,ba,bb,ca,cb,cd,da,db,dcab,ac,ad,bc,bd,cc,ddC8a,b,c,da,b,c,daa,ba,bb,bd,ca,cb,cd,ddab,ac,ad,bc,da,db,dcC9a,b,c,db,c,daa,ba,bb,bd,ca,cc,cd,daab,ac,ad,bc,cb,db,dc,ddC10a,b,c,da,b,c,daa,ba,bc,bd,cc,da,dcab,ac,ad,ca,cb,cd,db,ddC11a,b,c,db,c,daa,ba,bc,bd,ca,da,db,dcab,ac,ad,bb,cb,cc,cd,ddC12a,b,c,db,c,daa,ba,bc,bd,ca,cd,da,dcab,ac,ad,cb,cc,db,ddC13a,b,ca,b,c,daa,ad,ba,bb,bd,ca,cc,cdab,ac,bc,cb,da,db,dc,ddC14a,b,ca,b,c,daa,ad,ba,bc,bd,cc,cdab,ac,ca,cb,da,db,dc,ddC15a,b,ca,b,c,daa,ad,ba,bc,bd,ca,cb,cdab,ac,bb,cc,da,db,dc,ddC16a,b,da,b,c,daa,ac,ad,bb,bc,bd,dcab,ba,ca,cb,cc,cd,da,db,ddC17a,b,c,da,b,c,daa,ac,ad,ba,bc,bd,cd,dcab,ca,cb,cc,da,db,ddC18a,c,da,b,c,dab,ac,ad,cb,da,db,dcaa,ba,bb,bc,bd,ca,cc,cd,ddC19a,c,da,b,c,dab,ac,ad,cb,cd,db,dcba,bb,bc,bd,ca,cc,da,ddC20a,b,c,da,b,c,dab,ac,ad,bd,cb,cd,dbba,bb,bc,ca,cc,da,dc,ddC21a,b,c,db,c,daa,ba,bb,ca,cb,cc,da,db,dcab,ac,ad,bc,bd,cdC22a,b,c,db,c,daa,ba,bb,ca,cb,cd,da,dbab,ac,ad,bc,bd,dc,ddC23a,b,c,db,c,daa,ba,bb,bd,ca,cb,cd,daab,ac,ad,bc,db,dc,ddC24a,b,c,db,c,daa,ba,bc,bd,ca,da,dcab,ac,ad,cb,cc,cd,db,ddC25a,b,ca,b,c,daa,ad,ba,bb,bd,ca,cb,cdab,ac,bc,da,db,dc,ddC26a,b,ca,b,c,daa,ad,ba,bc,bd,ca,cdab,ac,cb,cc,da,db,dc,ddC27a,b,da,b,c,daa,ac,ad,ba,bc,bd,dcab,ca,cb,cc,cd,da,db,ddC28a,c,da,b,c,dab,ac,ad,cb,db,dcba,bb,bc,bd,ca,cc,cd,da,ddMoreover, a computer calculus describes the properties of prefixes and suffixes for the 28 classes ofLDL-strong 20-trinucleotide circular codes X. The set L1 is formed by the letters l1 in the first position of the trinucleotides of X and the set L3, by the letters l3 in the last position of the trinucleotides of X. The set D1 is formed by the diletters d1 in prefix position of the trinucleotides of X and the set D2, by the diletters d2 in suffix position of the trinucleotides of X. Eight classes have both four letters in L1 and L2 (C1–C4, C8, C10, C17, C20). Ten classes have four letters in L1 and three letters in L2 (C5–C7, C9, C11, C12, C21–C24). Reciprocally, ten classes have four letters in L2 and three letters in L1 (C13–C16, C18, C19, C25–C28). Three classes have nine diletters in D1 (C5, C7, C21) and similarly, three classes have nine diletters in D2 (C16, C18, C28). Only the class C28 has six diletters in D1 and nine diletters in D2 and similarly, only the class C21 has six diletters in D2 and nine diletters in D1. All the sets D1∩D2 are obviously empty.These tables and the other symmetric relations identified before (e.g., Proposition 6 of [23]) suggest that the symmetric group Σ4 can have a very important role in the study of these trinucleotide circular codes.



---

*Source: 659567-2011-08-25.xml*