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

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

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

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

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

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

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

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

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