植入(l, d)模體發(fā)現(xiàn)若干算法的實(shí)現(xiàn)與比較

胡宏濤, 龔逸文

(西安石油大學(xué) 計算機(jī)學(xué)院, 西安 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)模體和實(shí)例。給定t條長為n的DNA序列集合D= {s1,s2, … ,st}、l和d，qPMS的目標(biāo)是找出D中所有的(l,d)模體。

1 方法描述

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

表1 文中常用符號對照表

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

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

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

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

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

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

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

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

在本節(jié)中，算法的主要思路可以借鑒1.2節(jié)的內(nèi)容。需要注意的是，在遍歷的過程中需定義一個隊列對候選模體進(jìn)行操作，當(dāng)某一個候選模體符合海明距離 ≤d的條件時程序?qū)⒁躁犃械男问綄ζ溥M(jìn)行一系列的操作。

1.4 PMSP算法

PMSP算法相比前面3種算法有著更高的效率，PMSP思路如下：對于s1中的每一個長為l的字符串x，都可以生成一個模體集，在這個模體集合里面所有的模體與l-merx的海明距離都 ≤d，這個集合就被稱為候選模體集。用候選模體集中的每一個候選模體y去和s2-st中的每一個l-merx'進(jìn)行比較，判斷是否在si中存在一個與y的海明距離不大于d的字符串，如果在s2-st中的每一個序列中都存在這一個字符串，則表明候選模體y是一個潛在的模體，而在s2-st滿足海明距離為的l-mer都是潛在的模體實(shí)例；否則，從s1中選擇下一個l-mer，重新生成其候選模體集，再進(jìn)行上述判斷過程，直到遍歷完s1中的所有l(wèi)-mer為止。

2 實(shí)驗比較

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

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

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

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

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

表3pms_2和pms_3占用內(nèi)存對比

Tab.3Theoccupiedmemorycornparisonofpms_2andpms_3memoryoccupiedcontrast

算法名稱CPU/s占用內(nèi)存/Kpms_2452 188pms_341157 860

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

3 結(jié)束語

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

論文中存在的不足及改進(jìn)方法如下：

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

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