帶有通配符和長度約束的模式匹配問題求解及其應(yīng)用研究.pdf

1、帶有通配符模式匹配是模式識別領(lǐng)域中重要的研究方向之一，在計算生物學(xué)、信息檢索、網(wǎng)絡(luò)安全等研究領(lǐng)域中都得到了廣泛關(guān)注。它是通過在模式識別問題中引入通配符這種特殊字符，來匹配字母表中的任意字符，這樣帶來更多靈活性的匹配結(jié)果，但也使得問題求解變得更為復(fù)雜。當(dāng)頻繁共現(xiàn)在一段文本區(qū)域內(nèi)的多個模式之間表現(xiàn)為某種模式形式。例如在DNA序列中，啟動子TATA序列常常出現(xiàn)在CAATCT序列下游中間間隔30-50個通配符，其中也不是簡單的重復(fù)。由這兩個子序

2、列共同組成的模式可提高序列特異性，可以標(biāo)記“CAATCT[30-50]TATA…”。將其特點(diǎn)推廣為子模式序列集間隔，其中兩個相鄰子模式的間隔在一定長度范圍內(nèi)，為表示這種靈活的位置間隔，將通配符從指代單個字符擴(kuò)展為指代一定長度的子串，此通配符稱作限長空位(Bounded length gaps)。同時通過引入one-off約束限制條件來保證匹配子串模式序列集的穩(wěn)定性。
　　研究帶有通配符可變長度約束的模式匹配問題。本文圍繞帶通配符和

3、長度約束的模式匹配問題中解結(jié)構(gòu)的復(fù)雜性特征，從設(shè)計求解算法以及相似性度量模型應(yīng)用等問題，展開一些研究工作，主要內(nèi)容概括為以下三個方面:
　　(1)結(jié)合帶通配符和長度約束的精確模式匹配問題中求解的復(fù)雜性、精確性與完備性等特征，針對目前已有研究成果中還缺少針對性的模型建立求解策略。為此，借鑒約束可滿足問題框架(CSPs)，首先對帶通配符和長度約束的精確模式匹配問題構(gòu)建三元組求解模型。模型對該問題的約束條件和解空間等基本概念給出形式化的

4、描述，并將該問題已知的8條特殊情況統(tǒng)一表述為問題的基本性質(zhì)，其中包括在特殊條件下的完備性和相鄰匹配解在文本中的位置關(guān)系。同時提出一種求解帶通配符的模式串精確匹配問題的FIN算法。首先在定義了解空間的劃分邊界中，提出了采用分治策略的解空間劃分算法，將帶通配符的模式串精確匹配問題等價劃分為若干獨(dú)立的子問題，并從理論上說明了劃分前后解結(jié)構(gòu)等價性。實(shí)驗(yàn)結(jié)果表明FIN算法與解決相同問題的算法(PAIG)對比，該算法不僅可以得到匹配數(shù)目，而且可以得

5、到完備的匹配解位置。
　　(2)針對處理帶通配符的近似模式匹配問題中，使用傳統(tǒng)算法求解存在匹配子串結(jié)果質(zhì)量不高、易丟解等問題，提出一種啟發(fā)式的算法W-DPBI。該算法采取文本倒置搜索策略與流程的優(yōu)化。與同類DP和SAIL-APPROX算法進(jìn)行實(shí)驗(yàn)對比，結(jié)果表明該算法獲取解的平均增長率可達(dá)21.9％，最高可達(dá)57％，匹配結(jié)果具有良好的優(yōu)勢，在特定情況下可以明顯提高求解近似匹配結(jié)果的質(zhì)量和能力，具有較好的運(yùn)用靈活性和啟發(fā)性。
　

6、　(3)結(jié)合模式匹配及其相關(guān)求解算法在計算生物學(xué)領(lǐng)域中應(yīng)用以及相關(guān)實(shí)驗(yàn)方法研究的成果，針對藥物基因和疾病基因序列中的相似度結(jié)構(gòu)等特征，對所收集的數(shù)據(jù)信息源，采用近似匹配協(xié)同過濾算法并與相關(guān)算法組合求解搜索的策略，著重從已知疾病信息與基因信息角度來計算藥物與疾病之間的相似度，應(yīng)用于藥物重定位與構(gòu)建模型研究。實(shí)驗(yàn)結(jié)果表明，該方法能夠明顯提高潛在治療關(guān)系的藥物-疾病的富集程度。相比于已有分類模型和隨機(jī)抽樣結(jié)果，可以有效降低了預(yù)測的假陽性率，其