多重拼接系统的接受及计算复杂度分析：沙特国王大学学报

沙特国王大学学报接受多种拼接系统JoséRamonSanchezCousoa，1，FernandoArroyoa，VictorMitranaa，10，AndreiPaBazunb，c，2，MihaelaPab，daDepartamento de Sistemas Informaticos，Escuela Técnica Superior de Ingeniería de Sistemas Informaticos，Universidad Politécnica de Madrid，Calle Alan Turing s/n（Carretera de Valencia Km 7），28031 Madrid，Spainb国家生物科学研究与发展研究所，296 Independentei Bd。布加勒斯特，罗马尼亚c布加勒斯特大学数学和计算机科学系，Str. Academiei 14，010014，布加勒斯特，罗马尼亚d布加勒斯特大学工商管理学院，Bld. Regina Elisabeta 4-12，030167，布加勒斯特，罗马尼亚阿提奇莱因福奥文章历史记录：2021年12月5日收到2022年3月6日修订2022年3月9日接受2022年3月31日在线提供保留字：DNA计算分子计算剪接多重剪接接受多重拼接系统A B S T R A C T本文介绍了一种基于多重拼接的接收拼接系统，这种拼接方式在接收系统中是从未考虑过的。这种类型的拼接不同于通常的操作，因为可以将几个（不一定是不同的）规则同时应用于同一个字符串。我们首先考虑接受多个剪接系统，其中剪接位点的数量是预定义的常数。我们证明了这个模型是计算上完整的，如果常数是2，通过模拟2标签系统。此外，我们证明了模拟是时间复杂度保持的，并讨论了我们的建设给出的接受拼接系统的计算复杂度。然后，我们考虑接受多个剪接系统的网站的数量有一个上限或一个下限。这些系统的计算能力也进行了研究。最后，我们讨论了一些开放的问题。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍Head（1987）介绍了一种（生成）剪接系统，它是基于限制性酶和连接酶诱导的DNA链重组的分子计算的理论模型。直观地说，剪接的工作原理如下：给定两条DNA链，每条DNA链在某些限制性内切酶的作用下被切成两部分，然后其中一条的第一部分与另一条的第二部分连接在一起。这一过程如图所示。1.一、通过将这个过程形式化为字符串重写操作，可以定义计算系统剪接规则将限制性内切酶形式化，规定了这一过程可以发生的顺序。生成拼接系统从一组初始字符串开始，然后重复应用一组拼接规则来生成更多的字符串，从而生成语言。这台计算机-*通讯作者。电子邮件地址：jcouso@upm.es（J.R.S.库索），费尔南多.阿罗约@ upm.es（F。阿罗约），维克托·米特拉纳@ upm.es（V。Mitrana），andreipaun@gmail.com（A.Paun）。1这项工作得到了马德里社区在Convenio Plurianual下与马德里理工大学合作的部分支持，这是马德里大学卓越课程的一部分。2由罗 马尼亚研 究和创 新部资助 的国家核 心计划 部分支持 的研究 ，项目 编号25N/11.02.2019，BIODIVERS 9270103。Head（1987）提出了一种新的模型，并在大量的文献中作了进一步的研究。致力于拼接操作和拼接系统的文献非常多。 我们在这里只提到几本书，其中包含专门讨论这一主题的 章 节 （Head等人，1997年;PaBauzun等人，1998;Jonoska等人，2004; Head，2011; Head，2012）与生成拼接系统不同，接受拼接系统仅以一个初始字符串和有限的公理集开始，并且如上所述的迭代拼接被发起。当获得指定集合中的字符串时，整个过程停止。当系统停止时，接受输入字符串。Mitranaet al. （2010年），而不同的变种已在卡斯特利亚诺斯研究等人（2011），Arroyo et al.（2013），Mitrana et al.（2021年）等。绝大多数的拼接系统，以及所有接受拼接系统考虑到目前为止，假设只有一个规则可以作用于字符串。如果多个规则适用于一个字符串，那么这些规则被赋予该字符串的不同副本，以避免多个规则的同时应用，并且为了使这种也就是说，如果两个规则，比如说r1和r2，可以应用于字符串w，我们认为r1应用于w的一个副本，r2应用于另一个副本，在拼接步骤之后，语言包含两个应用程序的结果字符串。据我们所知，只有极少数论文提出了一种操作，https://doi.org/10.1016/j.jksuci.2022.03.0091319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comJosé Ramon Sanchez Couso，F.阿罗约河谷Mitrana等人沙特国王大学学报2911¼ð Þ ðÞðÞFig. 1.拼接操作。(or 相 同 的 规 则 ） 可 以 作 用 于 同 一 串 的 不 同 位 置 （ Freund andWachtler，1996; Pixton，2000; Ilie and Mitrana，2003;Mitrana，1997）。到目前为止，文献中定义的所有接受拼接系统（参见上面的引用）都认为在任何时刻只有一个规则适用于字符在本文中，我们研究接受拼接系统中，一个以上的规则不能同时作用于同一串的假设虽然乍一看可能很奇怪，但这种如果一个分子含有几个这样的序列，在必要的酶存在下，该分子实际上将在几个这样的序列上被不同或可能相同类型的酶切割。随后的重组可以发生在所有这些点。我们在这里介绍的更具体地说，在我们这里介绍的系统中，我们允许多个（不一定是不同的）规则应用于给定的字符串。应该注意的是，这些规则是独立应用的，只取决于字符串本身，而不取决于哪些其他规则应用于字符串的其他部分。这将我们的定义与其他方法区分开来，其他方法考虑了类似拼 接 操 作 的 同 时 应 用 ， 如 （ Mitrana ， 1997 ） 在 Ilie 和 Mitrana（2003）以及Pixton（2000）中进一步考虑的，其中研究了将几个规则应用于字符串的相关概念，这些规则导致具有标记末端的字符串可以根据标记重新组合。我们的建议可以被视为扩展剪接操作的计算能力的自然方式，其与文献中迄今为止报道的其他方式一起进行;对于几种这样的尝试，读者可以参考（Head等人，1997和PaBauzun等人， 199 8）。在迄今为止报道的提高计算能力的策略多重性，但同样，一些字符串可能具有任意大数量的多重性，对规则应用的不同控制类似于在受管制的重写区域中使用的控制，等等。与其他提出增加剪接操作计算能力的方法的工作不同，这项工作的主要目标不是引入一个新的剪接模型，该模型具有通过或多或少的人工约束实现的更大的计算能力，而是考虑可能的生物现象的模型，即图2所示。显然，在引入模型之后，研究其计算能力是很自然的。我们在这里考虑三种可能性定义多个拼接。具体来说，我们允许正好k个规则，最多k个规则，至少k个规则，不一定是不同的，同时应用于字符串。我们称之为k行动，6k -， P-K-剪接，很好我们研究了接受者的计算能力系统具有用于不同k值的这种多重拼接。具体来说，我们表明，接受2-多个剪接系统是计算上完整的模拟一个著名的计算上完整的模型，即2-标签系统。我们证明了我们的模拟是时间复杂度保持的，即模拟的接受拼接系统和模拟的2-tag系统具有相同的时间复杂度。并对接收拼接系统的结构复杂性进行了评估。这一结果立即被扩展到接受P2P-多个剪接系统。对另一方面，接受6k-多个拼接系统能够接受所有的正规语言和非正规语言，即使是K1 .一、在本说明的最后，我们就今后工作的一些可能方向进行了简短的讨论。2. 基本定义和符号字母表是一个有限的、非空的符号集。来自字母表V的任何有限（可能是空的）符号序列被称为José Ramon Sanchez Couso，F.阿罗约河谷Mitrana等人沙特国王大学学报29122►‘2000年2月¼ ðÞ¼ ð Þ 2HH1/4fg¼ ¼ ¼ ðÞ2n字母表V上的拼接规则是一个4元组u1;u2;u3;u4，使得u1;u2;u3;u42Vω。通过剪接位点或施用位点，连接酶：x;y 2LHHH电子邮件图二. 多重拼接操作。V上的字符串。V上所有字符串的集合记为Vω，空串记为k。字符串x的长度 用 jxj 表 示 。 一 个 字 符 串 x 是 w;x;w2Vω 的 子 串 ，如果 对 于 某 个u;v2Vω，w的所有子字符串的集合由Sub_w_n表示，而对于字符串的集合L;Sub_L_n表示cleavage？x;R？ ？fx1u1ri;riu2x2jx？x1u1u2x2;x1;x22Vω;[001 pdf 1st-31files] riu1;u2;u3;u4 2R g[fx1u3ri;riu4x2jx 1/4 x1u3u4x2;x1;x22Vω;ri1;u2;u3;u4 2R g;重新梳理x;y;Rfw ABw jw A2cleavagex;R;在L.集合S的基数记为kSk。121广义时序机（generalized sequential machine，简称gsm）是一个结构M<$Q;V;U;d;q0;F<$Q，其中Q是有限状态集，V和U分别是输入和输出字母表，q0Q是初始状态，F<$Q是最终状态集。 转换映射d是从Q×V到Q×Uω的函数。定义M中的一个跃迁如下所示：xqay把一个字符串x2Vω转换成一个字符串y用T M x表示的U ω由q0x定义ωys;sF和ω是的自反和传递闭包。显然，如果L是一个LAN-V ω上的量规;T MLSx2LT Mx。Bw22cleavagebrowny;R;A;B2fri;rij16i6ngg[fw1ABw2jw1A2裂解酶;Bw22cleavagepixix;Rb;A;B2fri;rij16i6ngg;连接酶pixix;y; Rb;fw1w2jw1ABw22recombpixix;y;Rb;和AB2frriri;riririj16i6nggg：一个拼接方案是一对V;R，其中V是字母表，R是V上的一组拼接规则。对于拼接方案h V;R和V上的语言L，我们定义[一个如上所述的拼接规则到某个字符串w，我们指的是一个子字符串w的u1u2或u3u4。对于拼接规则ru1;u2;u3;u4和xVω，我们定义了以下操作，这些操作实际上将通常的单个拼接操作分解为三个基本操作。我们更喜欢这些def-因为它们将进一步用于多个拼接操作的更直观和更不复杂的定义 我们还使用了这些操作的名称，这些操作的灵感来自图1中描述的阶段。1.一、[001p d f1 s t -31files]cleavagex;rfx1u1r;ru2x2jxx1u1u2x2;x1;x22Vωg[fx1u3r;ru4x2jx¼x1u3u4x2;x1;x22Vωg;重新梳理x;y;rfw1ABw2jw1A2裂缝;Bw22cleavagechambery;rn;A;B2fr;rgg[fw1ABw2jw1A2cleavagechambery;rn;给定拼接方案h和语言L，拼接语言rωh <$L <$定义如下。r0升/升;[rhhrωhLri L：iP0如果拼接方案从上下文中很清楚，我们省略下标。剪接系统或H系统是一种结构Hh;A h;其中h<$V;R<$是拼接方案，A<$Vω是有限初始Bw22cleavagex;r;A;B2fr;rgg;Ligasex;y;rfw1w2jw1ABw22recombx;y;randdAB2fr;rrgg：例1. 设x为abbcbbcbba;y为cbbcbaa，r为bb;cb;cb;b。然后，cleavag ex;rfabbr;rcbbcbba;abbcbb br;rcbba;abbcbr;rbcbba;abbcbbcbr;rbag;cleavagebenchmark;rbcbbr;rbcba;cbbr;rcbag：recom bbbcb;abbr rcba;abbcb br r bcba;abbcb r rbcba;abbcb r rbcba;abbcb rrbcba;abbcb r r bcba;abbcbbcb r rbcbag[fcbr rcbbcbb a; cb rr cbb a; cb r r bcbb a;cbr rbcbb a;cb r r bcbb a;cbr r bcb a;cbbrrcbbcbba;cbbrrcbba;cbb rbcbba;cbrrbag;连接酶：abbbcba;abbcbbcba;abbcbbcba;cbcbbcba;cbcbba;cbbbcbba;cbba g：如果Rr1; r2;. ; rn是一组拼接规则，我们将上述映射的定义扩展如下：语言由H生成的拼接语言定义为LHrωhA 。 这 是 已 知 的 ， 例 如 ， CulikandHarju （ 1989 ） 、 CulikandHarju（1991）和Pixton（1996）认为，这些拼接系统只生成正则语言。为了增加计算能力，为了提高这些系统的可靠性，提出了多种使用拼接的控制，参见，例如，第11章在PaPagunetal. （1998年）。我们现在介绍接受剪接系统的定义和术语，如下（Mitrana etal.， 2021年）。接受拼接系统是一个6元组C/V;h;;>;A;H;其中，V是输入字母表，h ^U; R^U是U上的拼接方案，VU，符号<; >U V被称为结束标记，而A Uω是公理的有限集合。最后，H是U叫做停止字符串。设C/V;h;; >;A;H是如上所述的接受拼接系统，并且w是V ω中的字符串;我们定义以下迭代式：rhLJosé Ramon Sanchez Couso，F.阿罗约河谷Mitrana等人沙特国王大学学报2913ð Þ2ðÞS¼ ðÞ¼fj gfjg¼ ðÞ[G.F.G.2格奥尔基文·F·格奥尔基文KK不同于定义拼接语言的拼接上面的rωLs1C;wwrhA[fw> g;si1C;wsiC;w[rhsiC;w[A;iP0：C在输入字符串w上的计算是集合序列A. A. B.C. D. C. C. D. C. D. D. C.只要存在kP1，计算就停止其中M是使V中的所有符号不变的gsm，但是当它在每对AB上如下工作时：● 如果AB2fririjri2Xg [fririjri2Xg，则删除AB。● 它在所有其他情况下都阻止了计算对于前面的定义，我们可以类似地将连接酶的定义扩展为t2f6kjkP1g[fPkjkP1g。使得Si=C;W=H-ε。我们说弦w2Vω是不实施例abbcbcbbcbcbba建议x y如果C在w上停止，则C接受。C接受的语言，表示为由LC，是C接受的所有字符串的集合。我们现在修正一些术语和符号来讨论多重拼接。设h^V;R^是一个拼接方案。因一连串令人WVω，一个集合X<$R，一个n个整数kP1，我们定义cle avag ekw;X作为是所有字符串w1x1Zi 1;Zi 1x01w2x2Zi 2;Zi 2x02w3x3Zi 3;.. . ;Zikx0kwk1使得w1/4w1x1x01w2x2x02.. . xkx0kwk1，对于所有j; 1 6 j 6 k; r i j 2X和2，r1r1r1r122f;fr1; r2given. 因此，abbcbcbbcbbba2连接酶2连接fx;yg;fr1;r2。设 t2kP1f6k;k;Pkg; 一个 接受 t- 多重 拼接系统 是一个 结构 Ct; V;U<;>; A; R; H，其中所有参数V; U<;>; A; R; H与接受拼接系统的参数具有相同的含义.我们现在定义：/1β-C;wβ-连接酶tβ-A[fw>g;Rβ];/i连接1连接C;w连接/i连接C;w连接[连接]/i连接C;w连接[A;R];i连接1：输 入 串 w 被 接 受 t- 多 重 拼 接 系 统 接 受 ， 如 果 存 在 qP1 使 得/q∈C;w∈H-1。兰-Zijrij;如果rij #x0j$yj#y0jri;ifri<$y#y0$xj#x0：由接受K-多重拼接系统接受的规格用LC表示，它是定义的所有可接受字符串的集合j jjj j这一定义如图所示。 二、当X R时，集合X被省略。我们通过考虑字符串的集合E来代替w来扩展这个定义，并定义cleavageE;X;[cleavagew;X：w2E此外，对于集合6kkP1和PkkP1中的规范，可以以如下方式扩展裂解的定义：以上给定一个如上所述的可接受的多重拼接系统C和一个被C接受的字符串w，我们定义测度：时间eCwminfqj/qC;w\H时间eCn最 大值xf时间eCw最小值;w被Cg接受：我们现在定义几个概念复杂性度量，接 受 多 个 拼 接 系 统 。 给 定 一 个 可 接 受 的 k- 多 重 剪 接 系 统Ck;V;U;>;A;R;H，我们定义以下度量：间隙PkE;XJPKK轴向倾角kAk;公理的个数;洛杉矶国际机场maxfjxj：x2Ag;最长公理;规则说明kRk;拼接规则的数量;cleavage6kE;XcleavagejE;X：第1页我们现在定义重组。对于一组字符串E，一组拼接规则X，和kP1，我们定义重新梳理kE;X¼fw1A1B1w2A2B2. w k A k B k w k1jw1A 1;Bk wk 12cleavagekE;X;Bi wi1Ai12cleavagekE;X;16i6k- 1g：现在我们回到例1，为了阐明最后的定义，将其加以扩展实施例2.设x<$$>abbcbbcbba;y<$$> cbbcbaa;r1<$$>bbb;cb;cb;b<$，且r2<$$> bbb;cb;a;b<$。然后，200 0 年 2月1日; 20000年2月1ar2;r2bbcbbcbr1;r1ba;abbr1;r1cbbcbr1;r1baa;abbcbr1;r1bcbr1;r1bag;cleavagedamage;fr1;r2grafted;cleavage（n）fx;y g; fr1;r2 gg;cleavage2x; fr1;r2 grab：现在，recom2fx;yg; fr1;r2gram包含集合cleavage x;y;r1;r2中正好三个字符串的串联，条件是的第一字符串并不开始与一符号fr1;r2;r1;r2g，第三个不以这样的符号结束。L规则最大值fju1u2u3u4j：最长拼接规则;停止停车kHk;停机串的数量;LHalt超声波清洗机maxfjxj：x2Hg;最长的停止字符串：3. 接受k-多重拼接系统的计算能力在本节中，我们研究了在接受多个剪接系统时，将每个字符串中剪接位点的数量限制在给定常数的影响。给定一个接受1-表示多剪接系统C<$V; U;<;>; A; R; H<$，关系式/i<$C; w<$s i<$C; w<$显然对每个iP 1和w都成立Vω。为了证明下一个结果，我们需要回顾定义一个计算完整的模型，一个2标签系统。该模型有几个等价的定义，参见，例如，（Rogozhin，1996; Minsky，1962; Post，1943）。我们倾向于使用以下定义。一个2标签系统是一对T1/4V;g，其中V是包含特殊符号g和g的字母表是映射从Vn fgg到V nf g，使得满足以下条件：● jg <$a<$jP1且如果jg <$a<$jP2，则g不出现在g<$a<$j中;● 1.类似地，我们可以扩展重组t∈E;X∈E的定义t2 f6 kjk P 1 g[fP kjk P 1 g.一个2标签系统定义了一个映射 在字符串的集合上，现在，对于一组字符串E，一组拼接规则X和kP1，我们设置：连接酶kE;X T Mrecomb kE;X E;长度至少2 inV删除两个符号，字符串的开头，并追加一个仅依赖于删除的第一个符号的字符串。具体地说，lTw是如下产生的字符串（¼José Ramon Sanchez Couso，F.阿罗约河谷Mitrana等人沙特国王大学学报29142ð Þ不¼ ð ð ÞÞð ÞðÞðÞ¼ ðÞ2ðÞ附加，前提是a是w的第一个符号。如上所述的2-标记系统对初始字符串w的计算是通过迭代地应用以w开始的运算T而产生的字符串序列。如果在某些迭代中产生了一个停止字符串，即长度为1的字符串或包含g的字符串，则上述计算在w上停止如Rogozhin（1996）所示，这样的2-标记系统在计算上是完备的，因为给定递归可重写语言L，存在2-标记系统T，使得w L当且仅当T在w上停顿。对于一个给定的2-标签系统T，我们定义其时间复杂度为函数TimeTn，它由T在长度为n的输入上停止所需的最大步数定义。定理3. 每一种递归可编译语言都可以被一个接受2-multiple拼接系统所接受。证据设T/V/V;g/V是一个双标记系统。我们构建了一个可接受的2-多重剪接系统C#-[1] Vn fgg;U;;>;A;R;H#-[1]，如下所示：U/V[f;>;#g[f#aja2V n fg gg;A¼f#a#gg;R¼fab;c;<;#aja;b;c2Vnfggg[fab;>;<;#aja;b2Vnfggg[fk;>;#;ga>ja2Vg[fa;g;$;#ja2Vg [f<;g;$;#;g;>;#;$g;H¼fxjx2Vω; jxj 6 1 g[f$g$g：我们证明了对于任意的弦w2Vω，如果2/i<$C;w<$，对于某个x2V ω ，则2/i<$1<$C;w<$。 让我们假设x^ab y，因此2/iC;w。另外，我想我会的。有两种可能性将2个拼接规则应用于：规则r1/2<;#an，假设y1/2k被应用，产生两个字符串，其中t是r或r0。第二条规则可以被巧妙地应用于是pk;>;#;ga>使得最终获得以下三个字符串：<关 于：同样的两条规则可以同时应用于公理<#a#ga>生成三个字符串： ：应用recomb2后，我们得到2ligase2f>;#a#ga>g;R;这证明了我们的说法注意，字符串ab#a#>也在这个2-拼接步骤中获得。<此外，它遵循归纳，这些字符串是唯一可以在2-应用于IiiC的拼接步骤;因此，属于推论4. 设L是一个被2-标记系统T接受的递归可重写语言。然后，L被接受2-多重拼接系统C接受，使得时间Cn2 O时间Tn。证据语句紧接着前面的构造，为了模拟T的每一步移动;C精确地制作了操作cleavage、recomb和ligase的单个序列。另一方面，为了完成计算，C再次应用这样的序列。H从前面的结构中很容易得出的另一个结论是：备注5.设T/V/V;g/V是一个双标记系统。接受2-多重拼接系统C在定理3的证明中构造的用于模拟T的V0;U<;A;R;H满足以下：Ax-C-V，LAx最大值：2Vn fggg，规则CkVk-13 kVk- 12 2kVk 2，L规则Ck5maxfjgaj：a2Vn f g ggg，停止C kVk1，3.可以看出，除了规则C之外，所有的测度都与V和g的测度具有相同的增长顺序。我们不知道是否可以改进结构，从而减少这种措施仔细看看定理3的证明，定理6. 每一种递归可编译的语言都可以被一个可接受的P2P多重拼接系统所接受.一个更精确的表征类语言接受接受k-多个拼接系统与kP3仍有待解决。4. 接受k-多重拼接系统的计算能力至于接受6k多重剪接系统的计算能力，我们声明：定理7. 每一种正规语言都可以被一个接受的106k-多拼接系统，对于任何k P 1。证据设M<$^Q;V;d;q0;F是一个确定的有限自动机。我们构建体一个接受106kΩ-multiple剪接系统C<$V;U;; >;A;R;H<$，使得w2Vω被M接受当且仅当它被C接受。C的参数定义为：如下所示：U¼V[Q[f#g;A¼fq# jq 2Q g;to/k<$C;w<$，对于任意kP 1，其中lk<$w<$表示k迭代R阿Q阿Vqa b qa a bV qQ不应用T到W。<1;2<只要一个字符串; x在拼接步骤中获得V ω，在下 一拼接步骤中 ，将其切割成三个 部分：< xrs;rsgrq;rq$>，其中s是规则a;g;$;#的标签，前提是x<- k并且a是x的最后一个符号，或者是规则; g ; $ ; #的标签，前提是x ¼ k，而q是规则g ; > ; # ; $的标签。 另一方面，公理也被分成三部分：rs，rs，rq 和rq 。 通过对i进行重组，我们得到属于H的字符串g，因此C的计算停止，证明完成。 Hfqa;>;dq;a;#ja2V;q2Qg;H¼fq> jq 2F g：最初，输入字符串w>通过拼接步骤转换为q0w>。<<归纳地，如果qax>是在某个步骤中获得的字符串，则在下一个拼接步骤中，它被变换为dq;ax>。<<此外，所有的副产品字符串不能干扰任何进一步的拼接步骤。值得一提的是，虽然允许同时应用多个拼接规则，但实际上这是不可能的。José Ramon Sanchez Couso，F.阿罗约河谷Mitrana等人沙特国王大学学报2915SðÞ由此得出，W被M接受当且仅当q>;q2F，在C中从W>获得，W>是H中的字符串，因此C中的计算停止并且输入字符串w被接受。<

下载后可阅读完整内容，剩余1页未读，立即下载