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

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

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

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

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

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

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