序列數(shù)據(jù)的相似性查詢(xún)研究.pdf

1、序列數(shù)據(jù)是一種重要而特殊的數(shù)據(jù)類(lèi)型,廣泛存在于文本、Web訪問(wèn)序列、交易數(shù)據(jù)庫(kù)中的用戶購(gòu)買(mǎi)序列以及生物數(shù)據(jù)庫(kù)中的DNA和蛋白質(zhì)序列等應(yīng)用中。從直觀上看,序列是(值,序)信息對(duì)的有序鏈表,區(qū)別于傳統(tǒng)的集合數(shù)據(jù),其不同元素間具有獨(dú)特的時(shí)間序或空間序關(guān)系。序列中元素的值與序關(guān)系對(duì)分析和挖掘各種序列數(shù)據(jù)缺一不可。
　　 字符序列是一類(lèi)具有空間序的常見(jiàn)序列數(shù)據(jù)。各種字符序列數(shù)據(jù)的分析和挖掘一直是學(xué)術(shù)界和工業(yè)界共同關(guān)注的問(wèn)題。近年來(lái),隨著生

2、物信息領(lǐng)域各種生物數(shù)據(jù)的爆炸式增長(zhǎng),字符序列數(shù)據(jù)庫(kù)呈現(xiàn)出橫向長(zhǎng)度不斷增長(zhǎng)和縱向數(shù)據(jù)量不斷加大的特點(diǎn)。此外,由于Web技術(shù)的迅速發(fā)展和Intemet用戶數(shù)量的激增,基于關(guān)鍵字的搜索引擎和郵件系統(tǒng)中的字符拼寫(xiě)檢查器,以及數(shù)據(jù)清洗中的副本檢測(cè)等應(yīng)用,對(duì)字符序列的高效查詢(xún)研究也提出了嚴(yán)峻的挑戰(zhàn)。序列相似性連接是相似性查詢(xún)研究的擴(kuò)展,即找到所有滿足一定相似性閾值的序列對(duì),其中序列對(duì)中的每條序列分別來(lái)自給定的兩個(gè)序列集。相似性連接在數(shù)據(jù)清洗、剽竊檢

3、測(cè)和生物信息等中廣泛應(yīng)用。作為重要的數(shù)據(jù)分析技術(shù),字符序列的相似性查詢(xún)和連接研究迄今為止都非?；钴S。
　　 字符序列相似性查詢(xún)和連接研究的一個(gè)核心問(wèn)題是序列數(shù)據(jù)特征的提取和相似性度量的定義及有效計(jì)算。由于字符序列具有特征難以抽取及有效表達(dá)、相似性度量的計(jì)算量較大等特點(diǎn),使得對(duì)其進(jìn)行有效查詢(xún)成為研究難點(diǎn)?，F(xiàn)有關(guān)于字符序列的大多相似性查詢(xún)算法中,基本只利用基于序列自身特征的多種過(guò)濾器來(lái)加速算法運(yùn)行,且在應(yīng)用多過(guò)濾器時(shí)完全忽略過(guò)濾順序

4、對(duì)算法效率的影響。此外,在查詢(xún)不斷到來(lái)時(shí),現(xiàn)有算法基本把先前的查詢(xún)結(jié)果信息丟棄而沒(méi)有加以利用來(lái)加速當(dāng)前查詢(xún),且后處理也基本上是直接的編輯距離計(jì)算而沒(méi)加以?xún)?yōu)化。而在相似性連接方面的大多數(shù)研究中,只針對(duì)靜態(tài)序列集做優(yōu)化設(shè)計(jì),不適合現(xiàn)實(shí)應(yīng)用中高度動(dòng)態(tài)變化的數(shù)據(jù)環(huán)境。因此,針對(duì)以上不足,本文對(duì)字符序列數(shù)據(jù)的相似性查詢(xún)和連接算法進(jìn)行了系統(tǒng)研究,主要成果概括為以下三方面:
　　 (1).提出優(yōu)化多重過(guò)濾的序列相似性查詢(xún)算法SSQ_MF。

5、r>　　 序列自身特征和度量空間性質(zhì)是序列“內(nèi)在”和“外在”的兩類(lèi)重要的特征,從兩個(gè)不同角度刻畫(huà)了序列數(shù)據(jù)自身性質(zhì)以及不同序列之間的關(guān)系。但現(xiàn)有查詢(xún)算法只基于序列自身特征或空間性質(zhì)進(jìn)行過(guò)濾,沒(méi)有把兩者很好地結(jié)合起來(lái)進(jìn)一步提高算法的過(guò)濾能力,且沒(méi)有分析多過(guò)濾器的執(zhí)行順序?qū)λ惴ㄐ阅艿挠绊?。算法SSQ_MF是有機(jī)結(jié)合了序列“內(nèi)在”和“外在”特征的多重過(guò)濾器算法,且從理論上提出了一種多過(guò)濾器的最優(yōu)過(guò)濾順序模型,使得SSQ_MF在整體過(guò)濾水平和

6、過(guò)濾代價(jià)方面得到進(jìn)一步優(yōu)化。詳細(xì)的實(shí)驗(yàn)對(duì)比表明,SSQ_MF在查詢(xún)性能上明顯優(yōu)于單一類(lèi)型的過(guò)濾器算法和基于“內(nèi)在”特征多過(guò)濾器的隨機(jī)執(zhí)行順序算法。
　　 (2)設(shè)計(jì)了基于參考集索引的增強(qiáng)序列查詢(xún)算法IRI
　　 IRI算法在現(xiàn)有基于參考集索引技術(shù)的基礎(chǔ)上,充分利用了先前查詢(xún)結(jié)果中含有的豐富過(guò)濾信息,且從理論上證明了能加速當(dāng)前查詢(xún)所必須保存的先前查詢(xún)結(jié)果數(shù)量下界;此外,IRI加進(jìn)了基于序列自身的特征來(lái)使過(guò)濾的上下界更緊,從

7、而使得算法過(guò)濾能力更強(qiáng)。在過(guò)濾完后的后處理階段,IRI提出了一種只計(jì)算部分動(dòng)態(tài)規(guī)劃表的方法來(lái)提高后處理的效率。在真實(shí)的DNA序列和蛋白質(zhì)序列數(shù)據(jù)上,實(shí)驗(yàn)結(jié)果表明算法IRI在查詢(xún)性能上明顯優(yōu)于現(xiàn)有的基于參考集索引方法RI。
　　 (3).設(shè)計(jì)了一個(gè)在動(dòng)態(tài)增量序列集上的有效相似性連接算法SJ-DASS
　　 針對(duì)現(xiàn)有相似性連接算法在動(dòng)態(tài)增加的序列數(shù)據(jù)集上不能高效增量式地運(yùn)行,提出了動(dòng)態(tài)序列集上高效相似性連接算法SJ-DASS

8、.動(dòng)態(tài)增加序列集是反映現(xiàn)實(shí)應(yīng)用的一種數(shù)據(jù)模型,本文從序列的空間性質(zhì)和自身特征出發(fā),設(shè)計(jì)了基于距離的可增量更新索引結(jié)構(gòu),且提出了兩個(gè)基于現(xiàn)有過(guò)濾器的更緊的距離下界,從而進(jìn)一步提高了過(guò)濾能力。SJ-DASS在動(dòng)態(tài)增加的實(shí)驗(yàn)數(shù)據(jù)集上,不僅運(yùn)行時(shí)間優(yōu)于現(xiàn)有算法,而且索引空間也大大減少。
　　 本文研究了序列數(shù)據(jù)中與相似性相關(guān)的兩個(gè)問(wèn)題:查詢(xún)和連接,并分別提出了有效的解決方案。本文提出的IRI和SSQ_MF算法對(duì)現(xiàn)有技術(shù)進(jìn)行了有效地改進(jìn),