An improvement to the lower bound on the number of subsequences
-
摘要: 序列删除t个数后会产生不同的子序列,由于序列的结构未知,给计算这些子序列的数量带来了一个难题。为了研究子序列的数量,本文在前人的基础上,采用放缩法,研究了当序列前3个块互不相同时子序列的数量,改进了子序列数量的下界。Abstract: The sequence after deleting t symbols will get different subsequences. Due to the unknown structure of the sequence which is deleted, it poses a problem to calculate the number of these subsequences. So we study the number of subsequences when the first three runs of the sequence are different in this paper. On the basis of previous ones, we adopt the scaling method and give an improvement to the lower bound on the number of subsequences.
-
Keywords:
- subsequence /
- run /
- lower bound
-
0. 引言
删除信道是指信息传输过程中丢失码字符号,造成信息传输错误。为了使信息有效的传输,研究可以纠正这些错误的纠错码具有重要的意义。然而并不是任意的编码都是有效的,Shannon[1]表示纠错码码率不高于信道容量时,才能实现信息的有效传输。为实现有效的编码,这个领域一个传统的问题就是,估计从原始序列中删除固定数量的元素会产生多少个不同的子序列。如,估计序列$ X $删除$ t $个元素会产生多少个不同的序列,记为$ \left|{D}_{t}\left(X\right)\right|\mathrm{。} $由此可以估计纠错码最佳码本的边界,进而计算纠错码的码率,有助于评估具体结构代码是否能够有效纠错[2-9]。事实上,估计$ \left|{D}_{t}\right(X\left)\right| $的范围在DNA存储领域,序列重建等问题中也有应用。目前,DNA存储技术已经成为一种潜在可行的存储技术,与传统的存储介质相比,DNA有显著提高信息密度和持久性的可能,因而受到广泛的关注[10]。另外序列重建问题在信息存储、分子生物学、化学以及传感器网络等领域也有着重要的应用[11-12]。
下面介绍几个与删除相关的包括子序列、块、循环序列等的定义[13-15]。
令$ {\mathscr{F}}_{q}=\{0,1,2,\dots ,q-1\} $,其中$ q\ge 2 $,设序列$ X={x}_{1}{x}_{2}\cdots {x}_{n}\in {\mathscr{F}}_{q}^{n} $。
定义1(子序列) 对于序列$ X\in {\mathscr{F}}_{q}^{n} $,若存在$ {i}_{1}\le {i}_{2}\le \dots \le {i}_{n-t}\in \left[n\right] $,使得$ Y={x}_{{i}_{1}}{x}_{{i}_{2}}\cdots {x}_{{i}_{n-t}}(0\le t < n) $,即$ Y $为从$ X $中删除$ t $个数得到的序列,则称$ Y $是$ X $的子序列。将$ {D}_{t}\left(X\right) $定义为$ X $的长度为$ n-t $的子序列的集合,$ \left|{D}_{t}\right(X\left)\right| $表示集合$ {D}_{t}\left(X\right) $中元素的个数,$ \left|{D}_{t}^{\left(a\right)}\right(X\left)\right| $表示$ X $的以$ a\in {\mathscr{F}}_{\mathrm{q}} $为第1个元素的子序列的集合。
例如$ X=1224, $ $ t=2, $则$ Y=14 $是$ X $的子序列,$ {D}_{2}\left(X\right)=\{12, \mathrm{ }14, \mathrm{ }22, \mathrm{ }24\} $,$ {D}_{t}^{\left(2\right)}\left(X\right)=\{22, \mathrm{ }24\} $,$ \left|{D}_{2}\right(X\left)\right|=4 $。
定义2(块) 序列$ X\in {\mathscr{F}}_{q}^{n} $中每一个由连续相同的数组成的最大的集合称为块(run),记$ X $的块的个数为$ r\left(X\right) $,$ 1\le r\left(X\right)\le n $。
例如$ X=112220 $有$ 3 $个块,分别为$ 11, \mathrm{ }222, \mathrm{ }0 $。
定义3(循环序列) 设序列$ {C}_{n}={c}_{1}{c}_{2}\dots {c}_{n} $,对$ i\in \mathrm{ }\left[n\right] $,$ {c}_{i}\in {\mathscr{F}}_{q} $,若$ {c}_{i}=a $满足$ i-1\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}q\right) $,那么称序列$ {C}_{n} $为循环序列。记$ \left|{D}_{t}\right({C}_{n}\left)\right|={D}_{q}(n, t) $。
注:规定$ {D}_{q}(0, \mathrm{ }0)=1 $,当$ t > n $或$ t < 0 $时$ {D}_{q}(n, t)=0\mathrm{。} $
例如当$ q=3 $时,$ n=7 $,$ {C}_{7}=0120120 $。
从序列$ X $中删除$ t $个序列,$ \left|{D}_{t}\right(X\left)\right| $的大小依赖于$ X $的结构。事实上$ q $越大,$ X $的长度越长,删除$ t $个数后产生相同的子序列可能越多,$ \left|{D}_{t}\right(X\left)\right| $便越难计算。Levenshtein[16]于1966年给出当$ q=2 $时$ \left|{D}_{t}\right(X\left)\right| $的一个范围,后在文献[17]中将这个范围推广到$ q $的一般情况
$$ \left(\begin{array}{c}r\left(X\right)-t+1\\ t\end{array}\right)\le \left|{D}_{t}\right(X\left)\right|\le \left(\begin{array}{c}r\left(X\right)+t-1\\ t\end{array}\right) 。 $$ 1969年,Calabi和Hartnett[18]认为当$ X $取循环序列时$ \left|{D}_{t}\right(X\left)\right| $取得最大值,即对$ q\ge 2 $,$ \forall X\in {\mathscr{F}}_{q}^{n} $,
$$ \begin{array}{c}\mathrm{m}\mathrm{a}\mathrm{x}\left|{D}_{t}\right(X\left)\right|=\left|{D}_{t}\right({C}_{n}\left)\right|={D}_{q}(n, t)=\\ \sum\limits_{i=1}^{q}{D}_{q}\left(n-i, t-i+1\right)\mathrm{。}\end{array} $$ 随后,2000年,Hirschberg和Regnier[13]经过进一步分析,给出了一个更紧的界为
$$ \sum\limits_{i=0}^{t}\left(\begin{array}{c}r\left(X\right)-t\\ i\end{array}\right)\le \left|{D}_{t}\left(X\right)\right|\le \sum\limits_{i=0}^{t}\left(\begin{array}{c}n-t\\ i\end{array}\right){D}_{q-1}\left(t, t-i\right), $$ 其中上界为$ {D}_{q}(n, t) $,即
$$ {D}_{q}(n, t)=\sum\limits_{i=0}^{t}\left(\begin{array}{c}n-t\\ i\end{array}\right){D}_{q-1}\left(t, t-i\right), $$ 当$ q=2 $时,这个界化为
$$ \sum\limits_{i=0}^{t}\left(\begin{array}{c}r\left(X\right)-t\\ i\end{array}\right)\le \left|{D}_{t}\right(X\left)\right|\le \sum\limits_{i=0}^{t}\left(\begin{array}{c}n-t\\ i\end{array}\right)\mathrm{。} $$ 后来,Liron和Langberg[14]证明了$ q=2 $时更紧的情况。Mercier[19]给出了$ \left|{D}_{2}\right(X\left)\right| $,$ \left|{D}_{3}\right(X\left)\right| $,…,$ \left|{D}_{5}\right(X\left)\right| $的具体表达式,并推广到了一般的结论。
在此基础上,本文继续研究了估计序列$ X $删除几个数后产生不同序列的数量问题,拟通过讨论当$ X $前3个块的元素互不相同时$ \left|{D}_{t}\right(X\left)\right| $的下界,得到更紧的下界。
1. $ \left|{\mathit{D}}_{\mathit{t}}\right(\mathit{X}\left)\right| $的下界
1.1 预备知识
下面介绍一些已知的命题,包括$ {D}_{2}(n, t) $的递推公式与具体表达式,向X插入一个元素后$ \left|{D}_{t}\right(X\left)\right| $值的变化,以及任意序列X关于$ \left|{D}_{t}\right(X\left)\right| $的下界。
命题1[13] $ n\ge t\ge 2 $,
$$ {D}_{2}(n, t)={D}_{2}(n-1, t)+{D}_{2}\left(n-2, t-1\right)\mathrm{。} $$ (1) 证明 将集合$ {D}_{t}\left({C}_{n}\right) $划分为2个部分,一部分以0为第一个元素,另一部分以1为第1个元素,则
$$ \begin{array}{c}\left|{D}_{t}\right({C}_{n}\left)\right|=\left|{D}_{t}^{\left(0\right)}\right({C}_{n}\left)\right|+\left|{D}_{t}^{\left(1\right)}\right({C}_{n}\left)\right|=\\ \left|{D}_{t}\right({C}_{n-1}\left)\right|+\left|{D}_{t-1}\right({C}_{n-2}\left)\right|,\end{array} $$ 所以等式(1)成立。
命题2[13] 对$ 0\le t\le n $,
$$ {D}_{2}(n, t)=\sum\limits_{i=0}^{t}\left(\begin{array}{c}n-t\\ i\end{array}\right)\mathrm{。} $$ (2) 命题3[13] 对任意$ U, V\in {\mathscr{F}}_{q}^{m} $以及任意$ \sigma \in {\mathscr{F}}_{q} $,$ \left|{D}_{t}\right(UV\left)\right|\le \left|{D}_{t}\right(U\sigma V\left)\right| $。
证明 要证明此命题只需证明对$ \forall s\in {D}_{t}\left(UV\right) $存在单射$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right), $使得$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)\in {D}_{t}\left(U\sigma V\right) $。设$ s=uv $,其中$ u $是$ U $的子序列并且是$ s $的最长前缀,定义$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)=u\sigma v\mathrm{。} $
下面证明$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right) $为单射,即证当$ s=s' $时,$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)=\mathrm{M}\mathrm{a}\mathrm{p}\left(s'\right) $。
设$ s=uv $,$ s'=u'v'\in {D}_{t}\left(UV\right) $,$ u, u $' 都是$ U $的子序列并且分别为$ s $,$ s' $的最长前缀。分以下2种情况考虑:
情况一:当$ u=u' $时,$ v\ne v' $一定成立,则$ u\sigma v\ne u'\sigma v' $。
情况二:当$ u\ne u $' 时,利用反证法证明。假设$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)=\mathrm{M}\mathrm{a}\mathrm{p}\left(s'\right) $,即$ u\sigma v=u'\sigma v' $。不妨设$ \left|u\right| > \left|u'\right| $,令$ u=u'x $,$ v'=y'v $,$ x $非空,故$ u'x\sigma v=u'\sigma y'v $,所以$ x\sigma =\sigma y' $。因此可以将$ x $表示为$ x=\sigma w $,$ y $' 表示为$ y'=z'\sigma $。从而$ \sigma w\sigma =\sigma z'\sigma $,其中$ z $' 是非空的,否则$ s=s $'。可见,$ u=u'x=u'\sigma w $,$ s'=u'v'=u'y'v=u'z'\sigma v=u'w\sigma v $。因为$ u'z'=u'w $是$ u $的子序列,所以$ u'z' $也是$ U $的子序列,且$ u'z' $是$ s' $的前缀,这与$ u' $的最大性矛盾。所以$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)=\mathrm{M}\mathrm{a}\mathrm{p}\left(s'\right) $。综上所述$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right) $是单射,又因为$ \mathrm{M}\mathrm{a}\mathrm{p}\left(s\right)\in {D}_{t}\left(U\sigma V\right) $,所以式(2)成立。
推论1[13] $ X\in {\mathscr{F}}_{q}^{m} $,$ r\left(X\right)=n(n\le m) $,则存在$ Y\in {\mathscr{F}}_{q}^{n} $,$ r\left(Y\right)=n $,使得
$$ \left|{D}_{t}\right(Y\left)\right|\le \left|{D}_{t}\left(X\right)\right|\mathrm{。} $$ 证明 序列$ X $可通过序列$ Y $插入数字得到,重复应用命题3即可得结论正确。例如,$ X=11122332 $,令$ Y=1232 $,满足$ r\left(X\right)=r\left(Y\right) $且$ \left|{D}_{t}\right(Y\left)\right|\le \left|{D}_{t}\right(X\left)\right| $。
命题4[13] $ Y\in {\mathscr{F}}_{q}^{n} $,$ r\left(Y\right)=n $,则
$$ \left|{D}_{t}\right(Y\left)\right|\ge {D}_{2}(n, t) 。 $$ 证明 对$ n $和$ n-t $进行归纳假设,当$ n\le 2 $或$ n-t\le 2 $时,引理成立。令$ Y=abZ $,因为$ r\left(Y\right)=n $,所以$ a\ne b $,则
$$ \left|{D}_{t}\right(Y\left)\right|=\left|{D}_{t}^{\left(a\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(b\right)}\right(Y\left)\right|+\sum\limits_{\sigma \ne a, b}\left|{D}_{t}^{\left(\sigma \right)}\right(Y\left)\right|\ge $$ $$ \left|{D}_{t}^{\left(a\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(b\right)}\right(Y\left)\right|=\left|a{D}_{t}\right(bZ\left)\right|+\left|b{D}_{t-1}\right(Z\left)\right| \text{,} $$ 利用归纳假设和式(1)可得
$$ \left|{D}_{t}\right(Y\left)\right|\ge \left|{D}_{t}\right(bZ\left)\right|+\left|{D}_{t-1}\right(Z\left)\right|\ge {D}_{2}(n-1, t)+{D}_{2}(n-2, t-1)={D}_{2}(n, t) 。 $$ 由命题4和推论1可推出对任意X,$ \left|{D}_{t}\right(X\left)\right|\ge {D}_{2}\left(r\right(X), t) $,即为文献[13]中的下界。
1.2 主要结论
本文的主要目的是讨论当X的前3个块的元素互不相同时$ \left|{D}_{t}\right(X\left)\right| $的下界。根据以上命题,得到本文的主要结论:
定理1 $ Y\in {\mathscr{F}}_{q}^{n} $,$ q\ge 3 $,$ n\ge 3 $,$ r\left(Y\right)=n $且$ Y $前3个块的元素互不相同,则
$$ \left|{D}_{t}\right(Y\left)\right|\ge {D}_{2}(n, t)+{D}_{2}(n-3, t-2) 。 $$ 证明 令$ Y=abcZ $,$ a\ne b\ne c $,则
$$ \left|{D}_{t}\right(Y\left)\right|=\left|{D}_{t}^{\left(a\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(b\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(c\right)}\right(Y\left)\right|+\sum\limits_{\sigma \ne a, b, c}\left|{D}_{t}^{\left(\sigma \right)}\right(Y\left)\right|\ge \\ \left|{D}_{t}^{\left(a\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(b\right)}\right(Y\left)\right|+\left|{D}_{t}^{\left(c\right)}\right(Y\left)\right|= \\ \left|{D}_{t}\right(bcZ\left)\right|+\left|{D}_{t-1}\right(cZ\left)\right|+\left|{D}_{t-2}\right(Z\left)\right| \text{,} $$ 根据命题4可知对任意$ Z\in {\mathscr{F}}_{q}^{n-3} $都有$ \left|{D}_{t}\right(bcZ\left)\right|\ge {D}_{2}(n-1, t) $,$ \left|{D}_{t-1}\right(cZ\left)\right|\ge {D}_{2}(n-2, t-1) $,$ \left|{D}_{\mathrm{t}-2}\right(Z\left)\right|\ge {D}_{2}(n-3, t-2) $,所以
$$ \begin{array}{c}\left|{D}_{t}\right(Y\left)\right|\ge {D}_{2}(n-1, t)+{D}_{2}(n-2, t-1)+\\ {D}_{2}(n-3, t-2)=\end{array} $$ $$ {D}_{2}(n, t)+{D}_{2}(n-3, t-2) 。 $$ 定理2 $ X\in {\mathscr{F}}_{q}^{n} $,当$ q\ge 3 $,$ n\ge 3 $,且$ X $前3个块的元素互不相同时,
$$ \left|{D}_{t}\right(X\left)\right|\ge \sum\limits_{i=0}^{t}\left(\begin{array}{c}r\left(X\right)-t\\ i\end{array}\right)+\sum\limits_{i=0}^{t-2}\left(\begin{array}{c}r\left(X\right)-t-1\\ i\end{array}\right)\mathrm{。} $$ (3) 证明 通过式(1),推论1和定理1可推得对任意$ X $存在长度为$ r\left(X\right) $且$ r\left(Y\right)=r\left(X\right) $的序列$ Y $使得
$$ \begin{array}{c}\left|{D}_{t}\right(X\left)\right|\ge \left|{D}_{t}\right(Y\left)\right|\ge \\ {D}_{2}\left(r\right(X), t)+{D}_{2}\left(r\right(X)-3, t-2)=\end{array} $$ $$ \sum\limits_{i=0}^{t}\left(\begin{array}{c}r\left(X\right)-t\\ i\end{array}\right)+\sum\limits_{i=0}^{t-2}\left(\begin{array}{c}r\left(X\right)-t-1\\ i\end{array}\right)\mathrm{。} $$ 所以不等式(3)成立。
对比定理2中$ \left|{D}_{t}\right(X\left)\right| $的下界与Hirschberg和Regnier[13]的下界,因为
$$ \sum\limits_{i=0}^{t-2}\left(\begin{array}{c}r\left(X\right)-t-1\\ i\end{array}\right)\ge 0 \text{,} $$ 所以当$ q\ge 3 $时定理2的下界比文献[13]中的下界更紧。
2. 结束语
本文研究了估计序列$ X $删除$ t $个数后产生不同序列的数量问题,得到了当X的前3个块的元素互不相同时$ \left|{D}_{t}\right(X\left)\right| $的一个下界。事实上,未来在寻找$ \left|{D}_{t}\right(X\left)\right| $的简单表达式或更紧的界方面,还需要做出很多研究。
-
[1] SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423. doi: 10.1002/j.1538-7305.1948.tb01338.x [2] KULKARNI A, KIYAVASH N. Nonasymptotic upper bounds for deletion correcting codes[J]. IEEE Transactions on Information Theory, 2013, 59(8): 5115-5130. doi: 10.1109/TIT.2013.2257917 [3] ABROSHAN M. Codes for synchronization in channels and sources with edits[D]. Los Angeles: University of Cambridge, 2019. [4] SWART T G, FERREIRA H C. A note on double insertion/deletion correcting codes[J]. IEEE Transactions on Information Theory, 2003, 49(1): 269-273. doi: 10.1109/TIT.2002.806155 [5] MERCIER H, BHARGAVA V K, TAROKH V. A survey of error-correcting codes for channels with symbol synchronization errors[J]. IEEE Communications Surveys & Tutorials, 2010, 12(1): 87-96. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5415865 [6] CULLINA D, KIYAVASH N. An improvement to Levenshtein's upper bound on the cardinality of deletion correcting codes[J]. IEEE Transactions on Information Theory, 2014, 60(7): 3862-3870. doi: 10.1109/TIT.2014.2317698 [7] LEVENSHTEIN V I. Efficient reconstruction of sequences[J]. IEEE Transactions on Information Theory, 2001, 47(1): 2-22. doi: 10.1109/18.904499 [8] SALA F, GABRYS R, SCHOENY C, et al. Exact reconstruction from insertions in synchronization codes[J]. IEEE Transactions on Information Theory, 2017, 63(4): 2428-2445. doi: 10.1109/TIT.2017.2649493 [9] CULLINA D, KIYAVASH N, KULKARNI A A. Restricted composition deletion correcting codes[J]. IEEE Transactions on Information Theory, 2016, 62(9): 4819-4832. doi: 10.1109/TIT.2016.2544348 [10] LENZ A, LIU Y, RASHTCHIAN C, et al. Coding for efficient DNA synthesis[J/OL]. (2020-06-28)[2022-03-01]. DOI: 10.1109/ISIT44484.2020.9174272. [11] LEVENSHTEIN V I. Efficient reconstruction of sequences from their subsequences or supersequences[J]. Journal of Combinatorial Theory, Series A, 2001, 93(2): 310-332. doi: 10.1006/jcta.2000.3081 [12] GABRYS R, YAAKOBI E. Sequence reconstruction over the deletion channel[J]. IEEE Transactions on Information Theory, 2018, 64(4): 2924-2931. doi: 10.1109/TIT.2018.2800044 [13] HIRSCHBERG D S, REGNIER M. Tight bounds on the number of string subsequences[J]. Journal of Discrete Algorithms, 2000, 1(1): 123-132. http://www.researchgate.net/publication/242436168_Tight_Bounds_on_the_Number_of_String_Subsequences_DANIEL_S [14] LIRON Y, LANBGERG M. A characterization of the number of subsequences obtained via the deletion channel[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2300-2312. doi: 10.1109/TIT.2015.2413958 [15] FLAXMAN A, HARROW A W, SORKIN G B. Strings with maximally many distinct subsequences and substrings[J]. The Electronic Journal of Combinatorics, 2004, 11(1): R8. doi: 10.37236/1761 [16] LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions, and reversals[J]. Doklady Akademii Nauk Sssr, 1965, 163: 845-848. [17] LEVENSHTEIN V I. Perfect codes in the metric of deletions and insertions[J]. Diskretnaya Matematika, 1991, 3(1): 3-20. [18] CALABI L, HARTNETT W E. Some general results of coding theory with applications to the study of codes for the correction of synchronization errors[J]. Information and Control, 1969, 15(3): 235-249. doi: 10.1016/S0019-9958(69)90442-2 [19] MERCIER H, KHABBAZIAN M, BHARGAVA V K. On the number of subsequences when deleting symbols from a string[J]. IEEE Transactions on Information Theory, 2008, 54(7): 3279-3285. doi: 10.1109/TIT.2008.924730 [20] HIRSCHBERG D S, REGNIER M. Bounds on the number of string subsequences [J]. Journal of Discrete Algorithms, 1999, 1(1): 115-122.