LL-PMS 8：快速解决种植模体搜索问题的链表实现技术

沙特国王大学学报LL-PMS 8：一种快速解决种植模体搜索问题的方法穆罕默德哈桑a，b，1，阿布萨利赫穆萨米亚a，2，马里兰州。Moazzem Hossaina，3，Md.Sabir Hossainb，4a孟加拉国Saidpur孟加拉国陆军科技大学计算机科学与工程系b孟加拉国Chattogram吉大港工程技术大学计算机科学与工程系阿提奇莱因福奥文章历史记录：收到2020年2020年11月7日修订2020年11月12日接受2020年11月21日网上发售保留字：Planted Motif Search（PMS）‘剪枝条件动态规划生成邻域A B S T R A C T在其他基序发现算法中，种植基序搜索（PMS）或（'，d）基序搜索算法被认为是下一代基序发现算法。这里，n个字符串和两个整数'和d被提供作为PMS中的输入。 它给出了在每个输入字符串中长度为M的所有序列的输出，其中每个出现在最多d个点处从Min变化。 本文提出了一种新的算法，为（'，d）模体发现问题中，我们发现所有的字符串的长度'，似乎在每个字符串的一组字符串与最多d不匹配已经。经过适当的调查PMS问题，它已被证明，这是一个NP难精确算法。通常，在最坏的情况下，所有已知的PMS精确算法在一些基本参数上都需要指数时间在本文中，我们提出了一种更快的方法，减少了搜索时间的样本驱动的算法的一部分。特别地，我们使用动态规划技术来消除一些公共子树的值的重新计算，并引入了一些新的加速技术，如使用链表，减少' -mer以使算法更快。由于使用链表作为主要的加速技术，我们将我们提出的算法命名为PMS 8的链表实现技术（LL-PMS 8）。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍*通讯作者：计算机科学与工程系，孟加拉国陆军科技大学（BAUST），SaidpurCanton- ment，Saidpur 5310，Bangladesh。电 子 邮 件 地 址 ： gmail.com ， gmail.com （ M 。 Hasan ） ， abusalehcse.ru @gmail.com（A.S.Musa Miah），moazzem.cse10@gmail. com（M.M. Hossain），sabir.cse@cuet.ac.bd（M.S. 侯赛因）。1BSc工程在CSE（CUET），讲师，计算机科学与工程系（CSE），孟加拉国陆军科技大学（BAUST），Saidpur，孟加拉国。2孟加拉国Saidpur孟加拉国陆军科技大学计算机科学与工程系讲师，计算机科学与工程硕士（RU）。3工程学硕士在CSE（RUET），讲师，计算机科学和工程系（CSE），孟加拉国陆军科技大学（BAUST），Saidpur，孟加拉国。4MSc Engg.在CSE（CUET），助理教授，计算机科学与工程系（CSE），工程技术吉大港大学（CUET），Chattogram，孟加拉国。沙特国王大学负责同行审查在现代世界中，从生物序列中发现模式是一个关键的困境。因为致命疾病的增加与总人口增长率成正比。面对这些疾病的适当治疗需要了解病毒，细菌或其他细菌的整体生物和遗传信息。为了正确理解遗传和生物信息，我们首先可以进入生物信息学领域，因为生物信息学的最终目的是更好地理解活细胞及其在分子水平上的工作方式。生物信息学有三个基本目标第一种是以数据库的形式有组织地存储生物数据这使研究人员能够方便地访问现有的信息，并建议新的条目。例如，用于核苷酸和蛋白质序列信息的基因库，用于3D大分子结构的蛋白质数据库等。2第二个目标是开发有助于数据调查的工具和资源。例如：BLAST（Altschul等人，生物信息学的第三个也是最重要的目标是利用这些计算工具来分析代表生物学结果的生物数据，https://doi.org/10.1016/j.jksuci.2020.11.0261319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3844PP2你好，]≤重要的时尚。但所有这些都依赖于对生物序列的正确分析，并找出绝对或至少是近似的结果。要做到这一点，应该发明适当的用于分析这些序列的一种这样的算法是种植基序搜索（PMS），其检查序列信息的几个原型 最近子串（Li等人， 2002）问题是PMS问题，其中意图是找到存在至少一个模体的最短d。这两个问题在PCR引物设计（Apte和Daniel，2009）、遗传探针设计（Xu等人，2009），寻找潜在的药物靶标，反义药物设计，获得蛋白质家族的公正一致，配制症状探针和基序发现（Eskin和Pevzner，2002）。因此，扩展有效的算法来解决PMS问题建立了强烈的好奇心，在生物学和生物信息学。为了识别一组DNA或蛋白质序列中的模体和重要保守区段，Pevzner和Sze在2000年提出了一种简单、经济和合理的（'，d）-模体搜索（Planted Motif Search，论文（Buhler和Tompa，2002）已经采用PMS算法来发现来自上游不同生物体的几种真核基因的已知转录调控元件。他们使用了四种不同基因的正向序列：前胰岛素原、二氢叶酸还原酶（DHFR）、金属硫蛋白和cfos。对于特定的转录因子，这些序列含有结合位点。他们的算法有利地识别了经验测量的转录因子结合位点。为了确定核糖体结合位点的问题，该算法也已进行了许多原核生物。为了找到复合监管模式，Paper（Eskin和Pevzner，2002）使用了他们 的定 制PMS 算法 MITRA。嘌 呤代 谢的上 游结 构域 包括三 个Pyrococcus基因组，已被他们操纵。在四组S.酿酒酵母基因，他们还测试了他们的算法。他们以这样一种方式控制两个转录因子，即转录因子的合并位点彼此靠近。论文（Kevin Lanctot等人，2003）已经使用他们的模式分支PMS方法来检测E.大肠杆菌，许多生物的真核基因的上游区域：DHFR，前胰岛素原，c-fos，金属硫蛋白，和酵母启动子区的样品‘‘Computing在大多数PMS算法中使用的基本步骤（例如（Dinh例如，2012 ， 2011;Bandyopadhyay 等 人 ， 2012;Nicolae 和Rajasekaran，2014; Davila等人，2007年）。这个问题在qPMS 7中得到了解决（Dinh等人，2012年）使用“线性规划（ILP）公式”（Nicolae和Rajasekaran，2014年）。作为预处理步骤的一部分，需要求解大量的ILP实例，并填充一个表 为了识别三聚体的共同邻居，然后频繁地查找该表。图案的存在是有机的独特的故事，发生在一系列生物逻辑链，如DNA/蛋白质链。模体在新的生物学发现中非常有用，如蛋白质运输因子的命名、蛋白酶切割位点的定位、蛋白质相互通信、蛋白质降解因子的感知等。存在许多用于模体搜索的算法。我们还研究了配对基序搜索算法（Yu等人，2012年）。但今天，种植基序搜索（PMS）算法被证明是最熟练和最值得信赖的。PMS算法在数学上被建立，以提供比其他算法更高的精确度来建模精确的图案，其中性能基于问题的最坏情况，即，问题的最坏情况决定了性能水平。所有现有的PMS算法在最坏情况下都需要指数时间，因此PMS是NP完全问题（Lanctot等人， 1999年）。我们还研究了PMS问题的基于模式的精确算法（Rajasekaran等人，2005 a，2005 b; Davila等人，2006年;Rajasekaran和Dinh，2011年）。在这些论文中，应用了一些效率技巧来减少时间和空间。但与PMS8相比，它并没有显着改善（Nicolae和Rajasekaran，2014）。此外，与传统的方法相比，这些技术不足以补偿和处理大型数据集。我们提出的算法我们还分析了用于基于最接近字符串和子串的模型的精确算法（Chen和Wang，2011），以解决种植的（l，d）基序，用于基于编辑距离的基序的顺序和并行算法（Chen等人，2016）、基于粒子群优化的模型来找到缺口基序和种植（l，d）基序（Lei和Ruan，2010 a，2010 b; Reddy等人，2013）、用于找到种植（l，d）基序的基于SMP簇的方法（Sahoo等人， 2011年）。但是这些技术与我们提出的方法相比，在时间和空间权衡方面并不那么重要。基于基本算法技术的一些琐碎的蛮力和动态编程（Ahammad 等人，2020;Hossain等人， 2020年）也被认为是为了扩大我们的算法意义。总是存在一个显着的性能差距，因为算法的许多元素有很大的运行时间，即使是合理的挑战性的情况下，虽然在这个领域已经做了很多研究第一节介绍了这方面的研究成果，并讨论了这些成果的局限性第二介绍了种植模体搜索问题的背景和研究现状。第3包含了我们提出的方法的方法和简要说明。第四部分是实验结果和根据实验结果提出的建议。最后，第5包含结论和未来的建议。2. PMS问题我们可以将这个问题的简化版本定义为：给定长度超过字母表的DNA序列，发现一个这就是所谓的种植- 基序搜索（PMS）问题。而经前综合症的解决要复杂得多。这个问题几乎可以与计算科学中的一个著名难题--公共近似子串（CAS）问题相比较更正式的PMS问题如下。给定n个序列S1，S2，. . ，Sn，每个长度为m，和两个整数'和d，标识所有'-聚体M，Ml，发生在在所述n个序列中的每一个序列中的至少一个位置具有至多d的汉明距离。更正式地说，M是一个基序，当且仅当8i，1≤我≤n，$ji，1 ≤j i≤m +1，等那dHM;Si j i：：j iM1）d.PMS问题与最近的问题相同子串问题。PMS（Planted Motif Search）创造了所有的理由-able让Ci= 3-聚体：AAG AGT GTC TCA CAG AGG GGA GAG AGT。现在，我们必须找到所有列表共有的基序：1）对所有序列执行此过程，2）找到所有Li共有的基序（一旦消除了重复）。这是种下的主题。见图1- 3 为 例 。3. 拟议方法精确PMS算法从给定的DNA或蛋白质序列中找到所有基序。在所提出的算法中，我们使用样本驱动和模式驱动的方法。我们为M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3845≤P←←←-≤算法1：生成邻域输入：候选（d）其他事项输出：公共d邻域Fig. 1. 所有模式的汉明距离d = 1。图二. 整理完名单后。图三. 消除重复。什么时候从样本驱动切换到模式驱动。对于任意的“- mers u作为”-mers v的d-邻域，如果u和v之间的汉明距离满足这个条件：dH（u，v）D. 现在如果u满足集合T中所有“-mer”的条件是集合T的公共邻域。公共邻域可以通过遍历所有可能的'-mer树来计算。在深度k处，我们检查修剪条件，如果它通过了修剪条件，我们将探索更深的深度。伪代码如下所示：1：开始生成邻域（“，d）2：对于k 1，|L|do s k d; 3：邻域生成器（L，g，1）4：邻域生成器（L，g，z）5：if（zl）则6：if（not prune（L，g））then7：对于2做8：qZ←a9：for（k ←1..| L|）do 10：Lk0<$Lk½2：：jSkj] 11：gk0<$gk12：如果（Lk[0]13：结束14：邻域生成器（L0; g0，z + 1）16：结束，如果17：否则18：报告20：结束生成邻域在我们的样本驱动部分，我们从给定的序列生成'-mer集。对于这个集合，我们计算模式驱动部分的公共邻域。对于'-mer集的生成，我们使用PMS 8程序（Nicolae和Rajasekaran，2014）。为此，我们构建n行和（m-1 + 1）列的矩阵R。在这见图4。 生成邻域的流程图。M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3846×←22···ð···ÞPP···ð··· Þ···我我H我-我矩阵我们保留了n个序列的所有可能的'，mer。 我们为'-mer集维护一个堆栈。我们从矩阵R的第一行选择a，并将其推到堆栈中。我们过滤掉矩阵R中与最近的推'-聚体具有大于2d的汉明距离的任何'-聚体。现在我们从矩阵R的第二行选择另一个'-mer并将其推到堆栈中。我们过滤掉矩阵R中与最近的push '-mer具有大于2d的汉明距离的任何'-mer。以类似的方式，我们继续过滤过程，直到某个过滤过程。 之后，我们使用堆栈中的'-mer来生成公共邻域。在过滤过程中，如果任何一行变为空，则我们弹出堆栈中的顶部'-mer并尝试来自矩阵R的不同'-mer。伪代码如下所示算法2：生成候选输入：输入字符串（S），最大汉明距离（d）输出：Motif1：开始PMS（S，d）2：对于k← 1到n，3：R k{u|};4：结束5：stack={}6：基序生成器（1，堆栈，R）7：基序生成器（z，栈，R）8：while（u Rz）do9：stack.push（u）10：R0← filter（R，stack）11：如果（R0.size> 0），则12：如果（阈值条件），则13：N←邻域生成器（堆栈，d）14：对于（m2 N）do15：if（isMotif（m，R0））then16：输出m;17：如果结束18：结束第19章：其他20：基序生成器（z + 1，R0）21：如果结束22：如果结束23：stack.pop（）第24章：结束25：结束PMS3.1. 动态规划技术我们改进了模式驱动的部分，在那里我们为'-mers集生成公共d-邻域。我们使用动态编程来快速搜索公共d-邻域。现在，如果我们看看图6中的所有可能的'-mer树，我们看到有一些子树重复了不止一次。对于一个子树，当我们第一次遍历它时，我们将保存一些必要的信息，这样当我们再次遍历一个类似的子树时，我们可以使用这些信息来避免探索不必要的节点，这节省了我们很多时间（见图7）。我们为每个子树保存的信息是，对于一个'-mer集l 1 ; l 2 ;：：; l k，我们是否找到了剩余汉明距离（d 1 ; d 2 ;：：; d k）的任何公共邻域。这个技巧是可行的，可以通过下面的定理1和定理2证明.定理1.在所有可能的'-mers树T中，设U和V是T的子树，a，b分别是由子树U和V的根表示的字母表。现在子树U和V将彼此相似，如果且只有当a=b且深度（U）=深度（V）时。图五. Generate Candidate ' -mers集合的流程图证据深度（U）和深度（V）都是1。所以，子树U和V只有一个节点，这个节点就是根本身。因为a=b，所以U和V是相似的。现在考虑深度（U），深度（V）为2。所以，子树U的根和V的根||子元素的数量，每个子元素代表一个字母。对于DNA字母表，U和V的根有四个孩子，他们代表A，C，T，G。因为子树U因此，通过对任意深度的归纳，我们可以证明定理1。定理2.设U和V是所有可能的'-mer树T的子树，L是'-mer的集合l1; l 2;Lk哪里|L| =k。设d1;d2;d，k是L开始遍历子树U时的剩余汉明距离，r1，r2，k是L的剩余汉明距离。; r k是剩余的汉明距离当开始遍历子树V时，L的值为0。假设U的子树在子树V之前遍历，则V的子树将至少具有相同的值当且仅当以下条件成立：i) 子树U和V彼此相似ii) ii）ri≥di;8i;1≤i≤k证据子树U和V相似，这意味着它们具有相同的深度和相同的结构。所以我们可以说U = V。现在让我们假设在U子树中w'-mers是'-mers集合L的公共邻域。 这意味着，d-H<$w;li<$≤di;8i，1≤i≤k。因为对于我来说，r≥d，所以d ≠ w;l ≠r。这意味着w是一个公共邻域M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3847子树V中的L因此定理2被证明。M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3848见图6。 所有可能的见图7。 所有可能的3.2. 加速技术3.2.1. 使用链表在样本驱动部分，过滤过程从矩阵R中去除了部分'-mer。但为了进一步的过程中，我们需要恢复删除项目。 使用链表，我们可以在O（行数）内完成此操作。我们为每一行建立链表。在链表中，每个节点保持各自行的'-mer索引和下一个节点的引用。在过滤过程中，我们从链表中删除相应的节点，并为这个过滤阶段创建一个删除项的链表因此，当我们想要恢复删除项时，我们只需将删除项的链表与相应行的剩余链表合并。3.2.2. 压缩该算法中有大量的汉明距离计算。因此，加快汉明距离的计算是一个主要的优势。我们使用PMS8中的这种加速技术（Nicolae和Rajasekaran，2014）。例如，对于DNA，我们使用两个比特来表示字符。我们找到两个'-mer的XOR。对于20位，我们预先计算查找表中的值，并使用该信息来找到两个′-mer的汉明距离。为求三聚体的一致总距离，我们采用了DNA序列的加速技术. DNA字母表有四个字符。对于每个字符表示，我们使用其中之一：{0001，0010，0100，1000}。为了找到三个'-mer的共有总距离我们对压缩的表示进行OR操作。一致的总距离等于压缩表示中的位数减去'-mer的长度。这大大改善了过滤过程。3.2.3. 按大小我们使用PMS8中的这种技术（Nicolae和Rajasekaran，2014）。在每个过滤过程之后，根据行的大小对行进行排序。这显著地改进了用于生成'-mer集合的样品驱动部分。3.2.4. ' -mer对的预处理距离在过滤步骤中，我们需要测试“-mers配对很多次。如果我们预处理汉明距离，M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3849表1在生成的数据集上进行重复比较。* 这里n = 20，序列长度= 600，s =秒，min =分钟，h =小时。则过滤过程将更快。该技术用于PMS 8（Nicolae和Rajasekaran，2014）。3.2.5. 查找字符串子集的motif这种加速技术在PMS6中描述。我们计算n' n个输入序列的基序然后我们对照剩余的n-n'序列检查基序。对于本文，n'是精确计算的”（Bandyopadhyay等人， 2012年）。4. 实验评价4.1. 数据集描述我们使用生成的数据和真实数据（Hasan等人， 2020年）。图8.第八条。所提出的LL-PMS 8算法单核在PMS 8上的加速PMS 8与单个内核上的拟议LL-PMS 8之间的负载比这两个程序都在相同的硬件和相同的数据集上执行。表2在真实数据集上进行比较。数据集n总数基地‘DPMS8LL-PMS8DM01R4600013442 min33分钟hm02r990002140.31秒0.26秒hm02r990002340.30秒0.23秒hm08r1575002340.22秒0.12秒hm08r1575002560.26秒0.11秒hm19r525002770.60秒0.80秒hm03r1015,0002340.79秒0.50 shm03r1015,0002550.90 s0.22秒hm03r1015,0002750.94秒0.49 Smus02r990002340.31秒0.22秒mus02r990002650.35秒0.23秒mus10r1313,0002550.88秒0.31秒mus10r1313,0002760.94秒0.29 Syst01r990002550.35秒0.22秒yst01r990002340.32秒0.225秒yst04r660002650.22秒0.16秒yst04r660002240.22秒0.17秒‘DPMS8LL-PMS810325 s8.5秒124波音707134秒1251.2 h31.5分钟1354.3 h3.4小时13683.9分钟58.3分钟1940.52秒0.17秒2340.51秒0.18秒2350.53秒0.173秒2550.58秒0.19秒2660.60秒0.19秒M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3850见图9。 增加阈值时的内存需求。见图10。“压缩”加速对运行时的影响。有压缩和没有压缩的算法之间的比较（参见第3.2节加速技术）。请注意，在这两个版本中，所有其他加速都已启用。cally distributed）模型生成长度为600的20个DNA串。将随机选择的“-mer”植入每个输入字符串中的随机位置，并且每个植入的基序在最多d个位置被修饰”（Nicolae和Rajasekaran，2014）。我们用C++语言实现了该算法在我们的实验中，我们运行在Linux操作系统与核心i3 2.4 GHz的CPU和4 GB RAM的程序。我们的数据集已经在在线Mendeley数据库中可用（Hasan等人， 2020年）。4.2. 性能我们将所提出的名为LL-PMS 8的算法的运行时间主要与PMS 8进行了比较（Nicolae和Rajasekaran，2014）。因为PMS8已经表现出比以前任何其他算法和加速技术更好的性能此外，我们的LL-PMS 8基于PMS 8（Nicolae和Rajasekaran，2014），并且表现出比PMS 8更好的性能（Nicolae和Rajasekaran，2014）。表1给出了PMS 8算法和LL-PMS 8算法在不同情况下的运行时间比较。LL-PMS 8算法的性能取决于模式驱动部分。在模式驱动部分中，'-mers后缀的重复越多，模体搜索速度越图图8示出了PMS 8和所提出的LL-PMS 8算法的运行时间比率。在模式驱动部分采用动态规划的方法，明显地改进了模式驱动部分。LL-PMS 8算法的性能取决于模式驱动部分。性能改善的变化可以在图中找到。8.第八条。这我们还使用PMS 8（Nicolae和Rajasekaran，2014）在讨论的真实数据集上测试了所提出的LL-PMS 8（Chen和Wang，2011）。表2显示了PMS 8和所提出的LL-PMS 8在真实数据集上的运行时比较。每个数据集是不同生物体的DNA序列的集合图案中M. Hasan，Abu Saleh Musa Miah，Md.Moazzem Hossain等人沙特国王大学学报3851驱动部分，我们基于候选集搜索公共邻域。候选'-mer集合的大小取决于用于从样品驱动部分切换到模式驱动部分的阈值。该算法采用动态编程的方法将先前访问过的状态保存在模式驱动部分中.这需要大量的内存。随着threshold值的增加，所需内存的大小也会增加。图9示出了相对于阈值的存储器增量属性。图图9中，存储器以“字节”测量并 在 “ Y ” 轴 中呈 现， 并 且 阈值 也在 “ X ” 上 呈现。图10特别描绘了我们提出的运行时的特殊压缩技术。它表明，当在运行时启用压缩技术时，我们提出的LL-PMS 8比PMS 8花费的时间更少（Nicolae和Rajasekaran，2014）。5. 结论和今后的建议在这里，我们提出了一个有效的精确算法的（'，d）-模体搜索问题。该算法比任何已知的PMS精确算法特别是，以前的算法重新计算一些共同的子树的值，而计算所有的共同邻居，这需要相当多的时间，并要求适量的内存。我们使用动态规划技术消除了这个问题。我们还添加了一些新的加速技术。所有这些特点使我们的方法比以前的方法更好。在这里，我们改进了修剪条件，减少了'-mer的数量。此外，通过改变某些条件，还可以改进一般d-邻域的生成过程。我们计划对公共d-邻域生成做进一步的分析，改进四个或更多'-mer的修剪条件。可以改善阈值条件以用于从图案驱动部分切换到样本驱动部分。引用Bandyopadhyay，S.，萨尼，S.，拉贾塞卡兰，S.，2012年。PMS6：A fast algorithmformotifdiscovery ， in ： 2012IEEE2ndInternationalConferenceonComputationalAdvancesinBioandMedicalSciences，ICCABS2012.https://doi.org/10.1109/ ICCABS.2012.6182627.Buhler，J.，Tompa，M.，2002年。使用随机投影寻找图案J.计算机Biol. 9（2），225https://doi.org/10.1089/10665270252935430网站。Davila，J.，Balla，S.，拉贾塞卡兰，S.，2007年快速实用的种植（l，d）模体搜索算法IEEE/ACM传输计算Biol.和Bioinf.4（4），544-552。https://doi.org/10.1109/TCBB.2007.70241网站。丁，H.，拉贾塞卡兰，S.，Davila，J.，2012年。qPMS7：一种快速的DNA和蛋白质序列中（ ' ， d ） - 基 序 搜 索 算 法 。 PLoSOne7 ， 1https://doi.org/10.1371/journal.pone.0041425.丁，H.，拉贾塞卡兰，S.，Kundeti，V.K.，2011年。PMS 5：（'，d）-模体发现问题的高效精确算法。 BMCBioinformatics12，410. https://doi.org/10.1186/1471-2105-12-410.Eskin，E.，Pevzner，P.A.，2002.寻找DNA序列中的复合调控模式。生物信息学18（增刊1），S354-S363。https://doi.org/10.1093/bioinformatics/18.suppl_1.S354。凯文·兰科特，Li，M.，妈妈，B.，王，S.，张，L.，2003.区分字符串选择问题。告知。Comput. 185（1），41-55。https://doi.org/10.1016/S0890-5401（03）00057-9.Lanctot，J.K.，Li，M.，妈妈，B.，王，S.，张，L.，1999年区别字符串选择问题，在：第十届年度ACM-SIAM离散算法研讨会论文集，SODA工业与应用数学学会，美国，pp。633-642Nicolae，M.，拉贾塞卡兰，S.，2014年。有效的顺序和并行算法种植模体搜索。BMC生物信息15（1）. https://doi.org/10.1186/1471-2105-15-34.Pevzner，P.A.，施淑娴，2000.在DNA序列中寻找微妙信号的组合方法。Proc. Int. Conf.内特尔系统摩尔Biol.余，Q，霍，H.，张玉，郭，H.，2012年。PairMotif：一种新的模式驱动的（l，d）DNA基序搜索算法PLoS One 7，e48442https://doi.org//journal.pone.0048442阿尔特舒尔，S。F.、吉什，W.，米勒，W.，迈尔斯，E. W.，&Lipman，D. J.（1990年）。基本的局部比对搜索工具。分子生物学杂志。粤https://doi.org/10.1016/备05022836号-1Li，M.，妈妈，B.，Wang，L.，美国，2002.最接近的字符串和子串问题。J. ACM49（2），157-171。https://doi.org/10.1145/506147.506150网站。Apte ， A. ， & 丹 尼 尔 ， S 。 （ 2009 年 ） 。 PCR 引 物 设 计 。 冷 泉 港 协 议https://doi.org/10.1101/pdb.ip65徐，Q，Schlabach，M.R.，G.J.汉农Elledge，S.J.，2009. 240，000个正交25聚体DNA条形码探针的设计。Proc.Natl.Acad.Sci.106（7），2289https://doi.org/10.1073/pnas.0812506106网站。拉贾塞卡兰，S.，Balla，S.，黄角，澳-地H、2005.种植模体问题的精确算法。J.计算机12（8），1117-1128. https://doi.org/10.1089/cmb.2005.12.1117天啊拉贾塞卡兰，S.，Balla，S.，Huang，C.H.，2005.种植模体挑战问题的精确算法。生物信息格式Adv. Bioinformat Comput. https://doi.org/10.1142/9781860947322_0025。Davila，J.，Balla，S.，&拉贾塞卡兰河，巴西-地（2006年）。空间和时间有效的算法种植 模 体 搜 索 。 计 算 机 科 学 讲 义 （ 包 括 人 工 智 能 讲 义 和 生 物 信 息 学 讲 义 ） 。https://doi.org/10.1007/11758525_110拉贾塞卡兰，S.，丁，H.，2011.（l，d）-模体发现算法的一种加速技术。BMC ResNotes 4（1）.https://doi.org/10.1186/1756-0500-4-54网站。陈志忠，王鲁生，2011。最近串和子串问题的快速精确算法及其在种植（L，d）-模体模 型 中 的 应 用 IEEE/ ACM 传 输 计 算 生 物 信 息 学 8 （ 5 ） ， 1400-1410 。https://doi.org/10.1109/www.example.com帕尔，S.，肖，P.，拉贾塞卡兰，S.，2016年。有效的顺序和并行算法，寻找编辑距离为基础的图案。BMC Genomics 17（S4）. https://doi.org/10.1186/s12864-016-2789-9.雷，C.，阮，J.，2010.一种基于粒子群优化算法的缺口模体发现方法。生物数据挖掘3（1）. https://doi.org/10.1186/1756-0381-3-9网站。Reddy，U.美国，Arock，M.，&雷迪A.第五章（2013年）。粒子群算法求解具有挑战性的planted（l，d）-Motif问题。生物信息学和计算生物学中的计算智能IEEE研讨会论文 集，CIBCB 2013 - 2013 IEEE 计算智能 研讨会系列， SSCI 2013 。https://doi.org/10.1109/ CIBCB.2013.6595413。雷，C.，&Ruan，J.（2010）.用一种新的进化算法寻找空位基序。计算机科学讲义（包括人工智能讲义和生物信息学讲义）。https://doi.org/ 10.1007/978-3-642-12211-8-5.Sahoo，B.，Sourav河，兰詹河，巴西-地Padhy，S.，2011.基于smp 集群的种植模体搜索精确算法的并行实现。EUR. J. Sci. Res.Ahammad，T.，哈桑，M.，哈桑，M.，侯赛因，M。美国，霍克，A.，&拉希德，M。M.（2020年）。用动态规划法求解工件排序问题的一种新方法。计算机与信息科学通信，1235 CCIS。https://doi.org/10.1007/978-981-15-6648- 6_25.Hossain，M.S.，蒙达尔，S.，阿里，R.S.，哈桑，M.，2020.优化快速排序的复杂性。In：Chaubey，N.，Parikh，S.，Amin，K.（编），计算机科学、通信和安全。Springer Singapore，pp. 329- 339哈桑，M.，Nicolae，M.，拉贾塞卡兰（2020年）。一种新的解决种植模体搜索问题的方法Mendeley Data，V2，doi：10.17632/x5sf9nywz2.2.