植入(l, d)模体发现若干算法的实现与比较

胡宏涛, 龚逸文

(西安石油大学 计算机学院, 西安 710065)

0 引 言

模体发现可以形式化地定义为植入(l,d)模体发现问题(Plant (l,d) motif search, PMS)。其中，PMS将模体定义为一个长为l的模式串m，其以最多d个位置失配出现于t条输入序列中，m和其在序列中的出现分别称为一个(l,d)模体和实例。给定t条长为n的DNA序列集合D= {s1,s2, … ,st}、l和d，qPMS的目标是找出D中所有的(l,d)模体。

1 方法描述

在描述模体发现算法之前，首先对本文中要使用到的符号做一个基本的定义，用来规定文中将要使用到的符号。论文中常用的符号对照见表1。

表1 文中常用符号对照表

1.1 基于候选模体实例字符串深度优先搜索的PMS算法

首先，对基于候选模体实例字符串深度优先搜索的PMS算法进行分析。在设计算法的时候用到了深度优先的方式分别对长为l的字符串进行操作，最终输出符合要求的模体和模体实例。下面对算法进行描述。

在此算法中需要建立一个分支节点为n-l+1的树，树的深度为t。建立该树之后可以使用深度优先搜索的方式对建立的树进行初始化。在初始化时需注意，在每次深度优先搜索时都需要先对下一条序列中长为l的字符串进行判断，看其与前面树中已经存在的字符串是否满足海明距离 ≤ 2d，如果满足，则证明这些长为l的字符串可能是属于同一个模体的模体实例。相反如果不满足条件，则证明这些字符串绝对不可能是属于同一个模体的模体实例，这时就需要采取剪枝的策略来降低程序的时间和空间复杂度，直接减去不需要的字符串并且不再继续遍历。当程序遍历到深度为t的时候，证明已经找到了t条模体实例，二者之间满足相互之间的海明距离 ≤ 2d，此时，只需要进一步用位点比对的方式找到候选模体，并对t条l-mer进行判断，如果符合模体发现问题的定义，则对模体和模体实例进行输出。

1.2 基于候选模体字符深度优先搜索PMS算法

1.1节主要是通过对t个模体实例进行操作，然后找出符合条件的候选模体，而在1.2节中，主要是通过遍历所有的模体(其中加入剪枝算法)找到符合条件的模体。第二种方法更加直接，也能直接找到所有符合条件的模体。

在此算法中，程序使用栈的方式进行模体的查找。首先建立一个深度为l，分支数为4的树。与1.1节相似，使用深度优先搜索的方式对模体进行遍历找到合适的模体。但与其不同的是，在基于候选模体字符深度优先搜索PMS算法中是直接对模体进行遍历而不是对模体实例中的字符串进行遍历。对模体进行遍历的好处在于当完成遍历时，就可以得到所有可能的模体集合而不会遗漏满足条件的模体。在对模体进行遍历的同时，应该特别注意要使用剪枝的方法去除不符合条件的模体。一个长度≤l的候选模体与初始序列进行对比，如果在一个初始序列的某一列中不能满足候选模体与长度等同的初始序列海明距离≤d,则表明候选模体不符合条件，进行剪枝，最终输出所有符合条件的候选模体。

1.3 基于候选模体字符广度优先搜索PMS算法

基于候选模体字符广度优先搜索PMS算法与1.2节中的PMS算法基本思路相同，不同的地方在于上节中采取的是深度优先搜索进行遍历，而本节主要采用广度优先搜索进行遍历。

在本节中，算法的主要思路可以借鉴1.2节的内容。需要注意的是，在遍历的过程中需定义一个队列对候选模体进行操作，当某一个候选模体符合海明距离 ≤d的条件时程序将以队列的形式对其进行一系列的操作。

1.4 PMSP算法

PMSP算法相比前面3种算法有着更高的效率，PMSP思路如下：对于s1中的每一个长为l的字符串x，都可以生成一个模体集，在这个模体集合里面所有的模体与l-merx的海明距离都 ≤d，这个集合就被称为候选模体集。用候选模体集中的每一个候选模体y去和s2-st中的每一个l-merx'进行比较，判断是否在si中存在一个与y的海明距离不大于d的字符串，如果在s2-st中的每一个序列中都存在这一个字符串，则表明候选模体y是一个潜在的模体，而在s2-st满足海明距离为的l-mer都是潜在的模体实例；否则，从s1中选择下一个l-mer，重新生成其候选模体集，再进行上述判断过程，直到遍历完s1中的所有l-mer为止。

2 实验比较

通过上一节中对4种算法的描述，可以分别实现程序，并且对4种算法的运行时间进行记录，比较其运行时间并得出一定的结论。在实验比较的过程中，分别选用了(9, 1)、(11, 2)、(13, 3)、(15, 4)对程序进行测试统计运行时间。程序运行时间的记录数据见表2。

表2 模体发现4种算法比较

可以看到，在模体发现问题的4种精确算法中，程序实现时间随着(l,d)的变化算法有着比较大的差异。通过实验，可以得到产生这些变化的原因。

首先，在pms_1中对于每一个输入字符串，每次都要加入一个模体实例，如果判断出来一组模体实例符合模体实例互相≤ 2d的条件，且这组模体实例的总数小于t，则必须加入n-l+ 1个模体实例继续进行深度优先遍历。通过对比可以得知，pms_1和PMSP算法有着比较相近的时间和空间复杂度，只是pms_1算法在处理相对比较大的问题上没有PMSP算法高效。在这里需要注意的是，pms_1算法并不像其它3种算法那样能够完全遍历出所有的模体，可能会遗漏掉一些模体，但是pms_1输出的模体一般都是得分较高的模体。

接下来，通过比较pms_2和pms_3可以发现二者在运行时间上并没有较大的差异，但这并不意味着二者在算法上没有什么区别。在这2种算法中分别采用了深度和广度优先的方式对算法进行设计，其中在广度优先中由于程序需要额外在队列中存储比较多的元素，因此必然会占用更大的内存。过大占用内存也证明了pms_3算法效率较低。pms_2和pms_3算法运行时占用内存见表3。

表3pms_2和pms_3占用内存对比

Tab.3Theoccupiedmemorycornparisonofpms_2andpms_3memoryoccupiedcontrast

算法名称CPU/s占用内存/Kpms_2452 188pms_341157 860

最后，通过对前面3种算法的实现，本文提出另一种相对于前面算法来说更加高效的PMSP算法。在1.4中已经比较详细地介绍了PMSP算法的基本思想，相对于前面的算法提出了一种比较新的思路来解决模体发现问题，在这种新的思路下，模体发现问题算法运行时间将大大减小。在PMSP算法中，程序可以解决前面算法很难处理的(15, 4)问题。

3 结束语

本文主要实现并比较了模体发现的4种算法，通过比较可以发现，由于模体发现是生物信息学、计算生物学和计算机科学的挑战问题，因此算法的选择至关重要。对于同样一个问题，选择不同的模体发现算法其程序执行时间可能会出现比较大的差异。这就要求设计者在进行PMS算法设计时充分考虑到算法的时间和空间复杂度，从而设计出运行时间更短的PMS算法。

论文中存在的不足及改进方法如下：

(1)基于候选模体实例字符串深度优先搜索的PMS算法存在问题：当进行位点比对时，并不是只有当模体实例符合一致序列条件的时候得出的模体才满足模体的定义，有可能有一些候选模体不符合一致序列条件，但同样符合模体的条件。改进办法：遍历所有候选模体然后再输出所有满足条件的模体。

(2)PMSP算法中存在问题。在PMSP中，程序主要使用了1.4节PMSP算法的思路和伪代码对其进行研究，但是由于在编码过程中缺乏对程序的优化，导致程序进行测试时运行的时间过长，在后续的研究中应加以改进。