胡宏濤, 龔逸文

(西安石油大學 計算機學院, 西安 710065)

0 引 言

模體發(fā)現(xiàn)可以形式化地定義為植入(l,d)模體發(fā)現(xiàn)問題(Plant (l,d) motif search, PMS)。其中，PMS將模體定義為一個長為l的模式串m，其以最多d個位置失配出現(xiàn)于t條輸入序列中，m和其在序列中的出現(xiàn)分別稱為一個(l,d)模體和實例。給定t條長為n的DNA序列集合D= {s1,s2, … ,st}、l和d，qPMS的目標是找出D中所有的(l,d)模體。

1 方法描述

在描述模體發(fā)現(xiàn)算法之前，首先對本文中要使用到的符號做一個基本的定義，用來規(guī)定文中將要使用到的符號。論文中常用的符號對照見表1。

表1 文中常用符號對照表

1.1 基于候選模體實例字符串深度優(yōu)先搜索的PMS算法

首先，對基于候選模體實例字符串深度優(yōu)先搜索的PMS算法進行分析。在設計算法的時候用到了深度優(yōu)先的方式分別對長為l的字符串進行操作，最終輸出符合要求的模體和模體實例。下面對算法進行描述。

在此算法中需要建立一個分支節(jié)點為n-l+1的樹，樹的深度為t。建立該樹之后可以使用深度優(yōu)先搜索的方式對建立的樹進行初始化。在初始化時需注意，在每次深度優(yōu)先搜索時都需要先對下一條序列中長為l的字符串進行判斷，看其與前面樹中已經存在的字符串是否滿足海明距離 ≤ 2d，如果滿足，則證明這些長為l的字符串可能是屬于同一個模體的模體實例。相反如果不滿足條件，則證明這些字符串絕對不可能是屬于同一個模體的模體實例，這時就需要采取剪枝的策略來降低程序的時間和空間復雜度，直接減去不需要的字符串并且不再繼續(xù)遍歷。當程序遍歷到深度為t的時候，證明已經找到了t條模體實例，二者之間滿足相互之間的海明距離 ≤ 2d，此時，只需要進一步用位點比對的方式找到候選模體，并對t條l-mer進行判斷，如果符合模體發(fā)現(xiàn)問題的定義，則對模體和模體實例進行輸出。

1.2 基于候選模體字符深度優(yōu)先搜索PMS算法

1.1節(jié)主要是通過對t個模體實例進行操作，然后找出符合條件的候選模體，而在1.2節(jié)中，主要是通過遍歷所有的模體(其中加入剪枝算法)找到符合條件的模體。第二種方法更加直接，也能直接找到所有符合條件的模體。

在此算法中，程序使用棧的方式進行模體的查找。首先建立一個深度為l，分支數(shù)為4的樹。與1.1節(jié)相似，使用深度優(yōu)先搜索的方式對模體進行遍歷找到合適的模體。但與其不同的是，在基于候選模體字符深度優(yōu)先搜索PMS算法中是直接對模體進行遍歷而不是對模體實例中的字符串進行遍歷。對模體進行遍歷的好處在于當完成遍歷時，就可以得到所有可能的模體集合而不會遺漏滿足條件的模體。在對模體進行遍歷的同時，應該特別注意要使用剪枝的方法去除不符合條件的模體。一個長度≤l的候選模體與初始序列進行對比，如果在一個初始序列的某一列中不能滿足候選模體與長度等同的初始序列海明距離≤d,則表明候選模體不符合條件，進行剪枝，最終輸出所有符合條件的候選模體。

1.3 基于候選模體字符廣度優(yōu)先搜索PMS算法

基于候選模體字符廣度優(yōu)先搜索PMS算法與1.2節(jié)中的PMS算法基本思路相同，不同的地方在于上節(jié)中采取的是深度優(yōu)先搜索進行遍歷，而本節(jié)主要采用廣度優(yōu)先搜索進行遍歷。

在本節(jié)中，算法的主要思路可以借鑒1.2節(jié)的內容。需要注意的是，在遍歷的過程中需定義一個隊列對候選模體進行操作，當某一個候選模體符合海明距離 ≤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(wèi)-mer為止。

2 實驗比較

通過上一節(jié)中對4種算法的描述，可以分別實現(xiàn)程序，并且對4種算法的運行時間進行記錄，比較其運行時間并得出一定的結論。在實驗比較的過程中，分別選用了(9, 1)、(11, 2)、(13, 3)、(15, 4)對程序進行測試統(tǒng)計運行時間。程序運行時間的記錄數(shù)據(jù)見表2。

表2 模體發(fā)現(xiàn)4種算法比較

可以看到，在模體發(fā)現(xiàn)問題的4種精確算法中，程序實現(xiàn)時間隨著(l,d)的變化算法有著比較大的差異。通過實驗，可以得到產生這些變化的原因。

首先，在pms_1中對于每一個輸入字符串，每次都要加入一個模體實例，如果判斷出來一組模體實例符合模體實例互相≤ 2d的條件，且這組模體實例的總數(shù)小于t，則必須加入n-l+ 1個模體實例繼續(xù)進行深度優(yōu)先遍歷。通過對比可以得知，pms_1和PMSP算法有著比較相近的時間和空間復雜度，只是pms_1算法在處理相對比較大的問題上沒有PMSP算法高效。在這里需要注意的是，pms_1算法并不像其它3種算法那樣能夠完全遍歷出所有的模體，可能會遺漏掉一些模體，但是pms_1輸出的模體一般都是得分較高的模體。

接下來，通過比較pms_2和pms_3可以發(fā)現(xiàn)二者在運行時間上并沒有較大的差異，但這并不意味著二者在算法上沒有什么區(qū)別。在這2種算法中分別采用了深度和廣度優(yōu)先的方式對算法進行設計，其中在廣度優(yōu)先中由于程序需要額外在隊列中存儲比較多的元素，因此必然會占用更大的內存。過大占用內存也證明了pms_3算法效率較低。pms_2和pms_3算法運行時占用內存見表3。

表3pms_2和pms_3占用內存對比

Tab.3Theoccupiedmemorycornparisonofpms_2andpms_3memoryoccupiedcontrast

算法名稱CPU/s占用內存/Kpms_2452 188pms_341157 860

最后，通過對前面3種算法的實現(xiàn)，本文提出另一種相對于前面算法來說更加高效的PMSP算法。在1.4中已經比較詳細地介紹了PMSP算法的基本思想，相對于前面的算法提出了一種比較新的思路來解決模體發(fā)現(xiàn)問題，在這種新的思路下，模體發(fā)現(xiàn)問題算法運行時間將大大減小。在PMSP算法中，程序可以解決前面算法很難處理的(15, 4)問題。

3 結束語

本文主要實現(xiàn)并比較了模體發(fā)現(xiàn)的4種算法，通過比較可以發(fā)現(xiàn)，由于模體發(fā)現(xiàn)是生物信息學、計算生物學和計算機科學的挑戰(zhàn)問題，因此算法的選擇至關重要。對于同樣一個問題，選擇不同的模體發(fā)現(xiàn)算法其程序執(zhí)行時間可能會出現(xiàn)比較大的差異。這就要求設計者在進行PMS算法設計時充分考慮到算法的時間和空間復雜度，從而設計出運行時間更短的PMS算法。

論文中存在的不足及改進方法如下：

(1)基于候選模體實例字符串深度優(yōu)先搜索的PMS算法存在問題：當進行位點比對時，并不是只有當模體實例符合一致序列條件的時候得出的模體才滿足模體的定義，有可能有一些候選模體不符合一致序列條件，但同樣符合模體的條件。改進辦法：遍歷所有候選模體然后再輸出所有滿足條件的模體。

(2)PMSP算法中存在問題。在PMSP中，程序主要使用了1.4節(jié)PMSP算法的思路和偽代碼對其進行研究，但是由于在編碼過程中缺乏對程序的優(yōu)化，導致程序進行測試時運行的時間過長，在后續(xù)的研究中應加以改進。