1 Introduction↩︎

The primary challenge in making DNA data storage cost-effective is the high synthesis cost. A straightforward way to reduce this cost is by increasing the data density, measured in bits per symbol or per synthesis cycle. Standard encoding over \(\mathsf{A}, \mathsf{C}, \mathsf{G}, \mathsf{T}\) allows up to \(\log_2 4 = 2\) bits per symbol, but error-correction constraints often lower this limit—for example, to \(\log_2 3 \approx 1.58\) bits/symbol when restricting consecutive symbols from repeating [1], [2]. Introducing additional encoding symbols can improve capacity and further reduce costs.

Composite DNA symbols, introduced in [3], [4], exploit inherent redundancies in DNA synthesis and sequencing processes. Unlike standard symbols that represent a single nucleotide, a composite symbol encodes a controlled mixture of the four bases and is defined by a probability vector \({p_\mathsf{A}, p_\mathsf{C}, p_\mathsf{G}, p_\mathsf{T}}\), where each \(p_a\) denotes the relative abundance of nucleotide \(a\), subject to \(\sum p_a = 1\). For example, \({\mathsf{M}= (0.25, 0.25, 0.25, 0.25)}\) represents an equal mixture of all four nucleotides. In a sequence such as \(\mathsf{C}\mathsf{M}\mathsf{G}\), the resulting oligo pool includes all \(4\) possible combinations at the second position, like \(\mathsf{C}\mathsf{A}\mathsf{G}\), \(\mathsf{C}\mathsf{C}\mathsf{G}\), \(\mathsf{C}\mathsf{G}\mathsf{G}\), and \(\mathsf{C}\mathsf{T}\mathsf{G}\), with equal frequencies reflecting the underlying probabilities. During sequencing, sampling a subset of molecules from this pool enables estimation of the original base mixture.

An extension of the composite symbol model, referred to as combinatorial composite DNA, was proposed by Preuss et al. [5]. Their approach generalizes the concept of composite symbols from the nucleotide level to the shortmer level, where each symbol represents a mixture of short DNA sequences rather than individual bases. In [6], Zhang et al. investigated error-correcting codes adapted to the composite DNA model. Furthermore, several related models and their corresponding coding schemes have been explored in recent studies, including [7], [8].

It should be mentioned that the combinatorial composite DNA can be seen as a composite symbol with union distribution or in other words a subset of composite symbols.

The concept of rank modulation has been excessively studied for flash memory such as in [9]. Codes over permutations were shown in [10], [11].

In this paper we wish to combine the theories about composite DNA and rank modulation. A composite DNA is defined by its probability distribution but a rank modulation composite symbol is defined by the rank between its motifs. For example the symbols \((0.1,0.2,0.3,0.4)\) and \((0.05,0.25,0.3,0.4)\) are different composite symbols but are the same rank modulation composite symbol since the rank between the motifs is the same. Instead of considering all the probability distributions we are interested only in the rank of the symbols.

We define the channel that uses rank modulated composite symbols and find codes over this alphabet. This work studies two important aspects of the ranked composite model. The first problem is concerned with the capacity of the channel the receives a rank modulated composite symbol as an input and in every transmission sends one motif with respect to the symbol’s probability distribution. A related problem to this problem with the binomial channel was studied in [12]. Another work [13] studied a similar problem over regular composite symbols. In [14] the set of composite symbols was selected with respect to the decoding probability. Lastly, [15] studied the capacity of the channel with combinatorial composite symbols.

In the second problem, we first assume that the only errors in the symbol can be the rank between the motifs. Then, we bound the size of codes than can detect or correct rank errors and show a construction for such codes.

The rest of the paper is organized as follows. Section 2, introduces the rank modulated composite channel. Then we present the channel that is used for sequences over rank modulated symbols and the type of errors in this channel. Section 3 presents the second problem in the paper which asks for the bounds and constructions for codes than can detect or correct rank errors. In this section we show in Section 3.1 the construction of the code, in Section 3.2 its properties and its size. In Section 3.3 we show some unique codes that use rank symbols the use all the set of motifs and then generalise it for the case where only a subset of motifs is used in every symbol. Finally, we study the first problem, in Section 4 and calculate the channel capacity for several cases.

2 Definitions and Problem Statements↩︎

Let \(q\in \mathbb{N}\) we denote by \([q]=\{0,1,\dots,q-1\}\) the set of integers between \(0\) and \(q-1\).It is important to note that since this set represents a set of motifs, one can think of this set as a general set of size \(q\). Given the alphabet size \(q\), for example \(q=4\) for DNA, the per-symbol capacity is limited by the alphabet size. A recent approach to break this limitation, first studied in [5], used the so-called combinatorial composite symbols. The set of combinatorial composite symbols of size \(m\) is the set of all subsets of \([q]\) of size \(m\), i.e., \({\Sigma_{\boldsymbol{comb}}=\{A\subseteq[q] : |A|=m\}}.\) It holds that \({|\Sigma_{\boldsymbol{comb}}|=\binom{q}{m}}.\) A more general idea of this approach was first studied in [3], [4], with the name of composite symbols. Unlike combinatorial composite symbols that are defined using sets, the composite symbols set is defined as all the probability distributions over the set \([q]\), i.e., \({\Sigma_{\boldsymbol{comp}}=\{\boldsymbol{\gamma}\in \Delta_{q}\}},\) where \(\Delta_{q}\) is the \((q-1)\)-dimensional probability simplex, i.e., \({ \Delta_{q}=\left\{(p_1,p_2,\dots,p_q)\in \mathbb{N}^q\text{ : } \sum_{i=1}^{q}{p_i}=1\right\}. }\) The use of composite symbols was first introduced over DNA nucleotides \(\{A,C,G,T\}\). One can note that there are infinitely many composite symbols. According to this definition one can view a combinatorial composite symbol as a composite symbol with uniform distribution over a subset of the original alphabet.

In previous works [13], [14], the main goal was to study how to choose a subset of composite symbols to minimise the decoding failure error or to maximise the capacity of the channel that uses composite symbols. This approach coincides with the real use of composite symbols where only a limited number of symbols are used and their distribution is often limited to a finite set of probabilities. Finding error-correcting codes with composite symbols was studied in [7], [8].

In this paper we introduce a new approach that combines the benefits of these two approaches. Namely, we wish to benefit from the simplicity of combinatorial composite while increasing the number of composite symbols. Instead of considering all the probability distributions we are interested only in the ranking between the symbols of every composite symbol.

Combining the ideas of composite symbols and combinatorial composite symbols, we consider the following alphabet as the channel input. Fix two positive integers \(m \le q\). We denote by \(\mathcal{S}_{m,q}\) the partial permutations, which contains all ordered subsets of \([q]\) of size \(m\). It holds that \(|\mathcal{S}_{m,q}|=\frac{{q}!}{({q}-{m})!}.\) For \(m=q\) we denote by \(\mathcal{S}_{m}\) the set of all permutations of size \(m\)

In the context of DNA storage, the set \([q]\) is called the motifs. The value \(q\) denotes the number of motifs. The size of the ranked symbol is the number of the partial permutations.

Let \(\pi\in \mathcal{S}_{m,q}\) we denote by \(\xi(\pi)\) a vector than contains the motifs in \(\pi\) in increasing order of their motif value. Furthermore, we define \(\pi\downarrow\) to be the permutation \(\pi\) after renaming the motifs such that \(\xi(\pi)_i\) is renamed to \(i\). One can observe that \(\pi\downarrow\in \mathcal{S}_{m}\).

As we have shown in Example 1 for a ranked composite symbol we need to choose a probability distribution that generates the ranking of the symbols. In this work we assume that when using symbols of length \(m\) all the probability distributions are the same. For \(m\in \mathbb{N}\) we define the symbol inner distribution to be a fixed probability distribution denoted by \({\boldsymbol{\gamma}^{m}=(\gamma_1,\gamma_2,\dots,\gamma_{m})}\). One can note that for \(m=2\) it holds that \(\boldsymbol{\gamma}^{2}=(\gamma_1,\gamma_2)\) so we can refer to \(\boldsymbol{\gamma}^{2}\) as \(\gamma_1\).

In Example 2, \(\gamma^2 = (\gamma_1,1-\gamma_1)\) where \(\gamma_1\in [0,\frac{1}{2})\) can represent the symbol \(AC\) since the probability of \(A\) is less than \(B\)’s. Next the rank modulated composite channel is formally introduced. In [15], the authors studied the same channel only over combinatorial composite symbols. Our channel uses symbols of ranked motifs instead of sets of motifs.

Denote by \(\mathsf{cap}(q,m,R, \boldsymbol{\gamma})\) the capacity of the channel \(\boldsymbol{RMCC}(q,m,\boldsymbol{\gamma},R)\). Denote by \(\mathsf{cap}(q,m,R)\) the maximal capacity that can be achieved in the channel \(\boldsymbol{RMCC}(q,m,\boldsymbol{\gamma},R)\) for all possible choices of the symbol inner distribution \(\gamma\), i.e., \(\mathsf{cap}(q,m,R)=\max_{\boldsymbol{\gamma}}{\mathsf{cap}(q,m,R, \boldsymbol{\gamma})}.\) Lastly, let \(\Gamma(q,m,R)\) be the set of probability distributions \({\boldsymbol{\gamma}=(\gamma_1,\gamma_2,\dots,\gamma_m)}\) that maximises the channel’s capacity, i.e., \(\Gamma(q,m,R)=\arg\max_{\boldsymbol{\gamma}}{\mathsf{cap}(q,m,R, \boldsymbol{\gamma})}.\) The first problem we seek to explore under this study is described as follows.

For the next problem we wish to study error-correcting codes over the rank modulated composite channel. For that, we are interested in sequences over partial permutations. The length of the sequences is denoted by \(n\). Following Definition 1, we can assume that the output of the channel is also a sequence of partial permutations. Accordingly, one could consider the following errors,

1. Change in order, example: sending \(352\) and receiving \(235\).

2. Deletions, example: sending \(352\) and receiving \(52\).

3. Substitutions, for example sending \(352\) and receiving \(452\).

In this paper, we study sequences over partial permutations of the same constant size \(m\). Therefore, we can read until we have all the required motifs since \(m\) is known to the reader. We assume that motifs are sent with respect to \(\boldsymbol{\gamma}\) so there are no substitutions and we ignore errors during sequencing which change the motif value. Hence, we are left with the first type of errors that modify the ranking of the motifs, which is the main focus of this part of the paper. It is possible to note that this family of errors correspond to the Kendall’s \(\tau\)-metric, which is denoted by \(d_{\tau}(\cdot,\cdot)\).

It is said that \(u\in {\mathcal{S}_{m,q}}\) experienced \(t\) Kendall’s \(\tau\) errors from \(v\in{\mathcal{S}_{m,q}}\) if \(d_{\tau}(u,v)=t.\) Let \({\boldsymbol{u}},{\boldsymbol{v}}\in{\mathcal{S}_{m,q}}^{n}\) be two vectors of partial permutations. It is said that \({\boldsymbol{u}}\) experienced \((t,e)\)-Kendall’s \(\tau\) permutation errors, if for at most \(e\) indices, the partial permutation \(u_i\) experienced at most \(t\) Kendall’s \(\tau\) errors from \(v_i\).

We say that a code over \(\mathcal{S}^{n}_{m,q}\) is a \((t,e)\)-error detecting code if it can detect any \((t,e)\)-Kendall’s \(\tau\) permutation errors. Similarly, a code over \(\mathcal{S}^{n}_{m,q}\) is a \((t,e)\)-error correcting code if it can correct any \((t,e)\)-Kendall’s \(\tau\) permutation errors. Lastly, we denote by \(\mathsf{A}_{\boldsymbol{det}}(n,q,m,t,e), \mathsf{A}_{\boldsymbol{cor}}(n,q,m,t,e)\), the largest length-\(n\) \((t,e)\)-error detecting, correcting code, respectively. Codes that correct these types of errors will be referred as Kendall Permutation Codes.

First we study Problem 2. In the following section we present a general construction for such codes.

3 Constructions of Kendall Permutation Codes↩︎

3.1 Constructions of Kendall Permutation Codes↩︎

In this subsection we present a construction of Kendall Permutation Codes over partial permutations. The idea behind this construction is based on the work of tensor product codes using two linear codes [16], however, in our case the set of permutations does not constitute a linear space and thus cannot be easily used with the tensor product framework. We will first construct codes for permutations, i.e., \(m=q\), and then extend for partial permutations (\(m>q\)) in the final subsection.

First we define a crucial building block for our code. Let \(q,m\in\mathbb{N}\). We already defined \({\mathcal{S}_{m,q}}\) to be all the partial permutations over \([q]\) of size \(m\). Let \(A\subseteq {\mathcal{S}_{m,q}}\) be a subset of partial permutations. We denote by \(d_\boldsymbol{min}(A)\) the minimum Kendall’s \(\tau\) distance between any two partial permutations in \(A\), i.e., \({ d_\boldsymbol{min}(A)=\min_{a\neq a'\in A}{d_{\tau}(a,a')}. }\) A family of sets \({\mathcal{R}=A_0,A_1,\dots,A_{\ell-1}\subseteq{\mathcal{S}_{m,q}}}\) is called a partial partition of size \(\ell\) of \({\mathcal{S}_{m,q}}\) if for every \(i\neq j\) it holds that \(A_i\cap A_j=\phi.\) For \(q=m\) we also say that it is a partial partition of \(\mathcal{S}_{m}\).From now on in this paper the notation of \(\mathcal{R}\) represents a general partial partition \(A_0,A_1,\dots,A_{\ell-1}\subseteq{\mathcal{S}_{m,q}}\) of size \(\ell\) of \({\mathcal{S}_{m,q}}\). A partial partition \(\mathcal{R}\) is called a partition if \(\cup_{i}{A_i}={\mathcal{S}_{m,q}}.\) The minimum Kendall’s \(\tau\) distance of a partition \(\mathcal{R}\) is defined by \({d_\boldsymbol{min}(\mathcal{R})=\min_{i}{d_\boldsymbol{min}(A_i)}}.\) For every vector of partial permutations \({\boldsymbol{c}}\in{\mathcal{S}^{n}_{m,q}}\) we denote by \(\Lambda(s)\) the vector of indicators of the partial partition \(\mathcal{R}\), i.e., in index \(i\) we have the value \(j\) if \({\boldsymbol{s}}_i\in A_j\). If the permutation is not in any set we denote it by “\(?\)”. We omit the partial partition \(\mathcal{R}\) from the notation of \(\Lambda\) as it will clear from the context.

Now we are ready to present our construction that follows the ideas of tensor product codes [16].

A code that is constructed by Construction 1 will bereferred to as tensor permutation code.

3.2 Properties and Size of Tensor Permutation Codes↩︎

In the following theorems we go over the properties that the tensor permutation codes inherit from their inner and outer codes. Let \(\mathcal{R}\) be an inner code with minimum Kendall’s \(\tau\) distance \(d_{\boldsymbol{in}}\). Let \(\mathcal{C}^\boldsymbol{outer}\) be an outer code over \([\ell]\) of length \(n\) with minimum Hamming distance \(d_{\boldsymbol{out}}\). First we begin with two simple observations.

Next, we analyse the size of tensor permutation codes. The main difference between the analysis of different codes will be its inner code, i.e., the partial partition of the set of partial permutations. Let \({\boldsymbol{v}}\) be a vector over \([\ell]\) of length \(n\). Denote by \(\#i({\boldsymbol{v}})\) the number of occurrences of \(i\) in \({\boldsymbol{v}}\). The following theorem provides the size of a general tensor permutation code and a tensor permutation code over a partition such that all the sets are of the same size.

3.3 Special Constructions↩︎

In this subsection we will show several partitions of \(\mathcal{S}_{m}\). At the end we will show the relationship between tensor permutation codes over permutations and over partial permutations. We use the same notations as in [17] for some properties of permutations. We denote by\(\text{id}=(12\dots m)\) the identity permutation. We say that a permutation \(\pi\in \mathcal{S}_{m}\) has Kendall’s \(\tau\) weight \(k\) if it holds that \(d_{\tau}({\text{id}},\pi)=k.\) We denote by \(I_m(k)\) the set of all permutations of Kendall’s \(\tau\) weight exactly \(k\). First we find a partition with minimum Kendall’s \(\tau\) distance \(2\). Let \(\mathcal{R}_{\text{Parity}}=A_0,A_1\) be the partition of all the permutations according to their Kendall’s \(\tau\) weight parity. One can note that \(A_0\cap A_1=\phi.\) It is well known that the partition \(\mathcal{R}_{\text{Parity}}=A_0,A_1\) has minimum Kendall’s \(\tau\) distance \(2\) and the sets are of equal sizes. We denote by \(A_q(n,d)\) the size of a largest code over \([q]\) of size \(n\) with minimum Hamming distance \(d\). Let \(\mathcal{C}^\boldsymbol{outer}_{\text{bin}}\) be a largest binary of size \(n\) with minimum Hamming distance \(d_{\boldsymbol{out}}\).

Lastly, the next theorem connects between tensor permutation codes over permutations and partial permutations.

4 The Rank Modulated Composite Channel’s Capacity↩︎

Note that in the rank modulated composite channel \(\boldsymbol{RMCC}(q,m,\boldsymbol{\gamma},R)\) the input consists of \({\frac{q!}{(q-m)!}}\) partial permutations, while the probability distribution of each partial permutation is \(\boldsymbol{\gamma}\). In order to compute the channel’s capacity one should also consider the probability distribution over the partial permutations, i.e., all possible channel inputs. Since the channel is symmetric and the only difference between the partial permutations is their motifs’ values, the first claim states that the capacity achieving input distribution (CAID) to the channel is the uniform distribution over all the partial permutations.

Next, one can note that using the central limit theorem, when the coverage depth increases one can distinguish between the different partial permutations for every \(\boldsymbol{\gamma}\) such that all the \(m\) motifs have positive probabilities. Hence, the capacity approaches the logarithm of the input size.

The following theorem calculates the capacity and the probability distribution \(\boldsymbol{\gamma}\) for several special cases.

The last theorem shows that for partial permutation of size \(2\), if the alphabet size is large enough, then the best probability distribution \(\boldsymbol{\gamma}\) is uniform over the two motifs. Since we normally use alphabets of size \(4\) for DNA, the use of partial permutations can still be useful, for example with \(q=4\), i.e. DNA and partial permutations of size \(m=2\) with coverage depth \(R=2\) it holds that \(\Gamma(q=4,m=2,R=3)=(0.2,0.8)\). Furthermore it holds that \(\mathsf{cap}\left(q,m=2,R=2,\left(0.2, 0.8\right)\right)=2.67>2.5=\mathsf{cap}\left(q,m=2,R=2,\left(\frac{1}{2},\frac{1}{2}\right)\right)\). Hence, partial permutations improved the capacity over the case of combinatorial composite symbols.

Acknowledgments↩︎

The collaboration and discussions of this paper were originated in Dagstuhl Seminar 24511 [18].

References↩︎