支持得分矩陣的近似查詢處理技術(shù)研究.pdf

1、近幾年來，隨著生物信息學(xué)迅速發(fā)展，產(chǎn)生了大量的生物數(shù)據(jù)，對這些生物數(shù)據(jù)的研究和分析對于指導(dǎo)生命科學(xué)研究、揭示生命起源和進化的規(guī)律有著重大的意義。生物序列與生物序列模式是這些生物數(shù)據(jù)中的兩種重要內(nèi)容，在生物信息學(xué)研究中，為了對新發(fā)現(xiàn)的序列按照其蘊含的模式信息進行分類或者從序列數(shù)據(jù)庫中找出蘊含著某個特定模式信息的序列實例來，往往需要對生物序列與生物序列模式進行匹配。
　　最初，生物序列模式多以固定的字符串來表示，所以生物信息學(xué)領(lǐng)域的模

2、式匹配主要通過序列相似性分析等技術(shù)實現(xiàn)，包括精確查詢和近似查詢兩種查詢處理方法。但是并非所有的生物序列模式都適合用固定的字符串表示，很多時候生物序列模式是以得分矩陣的形式保存的，隨著以得分矩陣描述的生物序列模式數(shù)據(jù)及其數(shù)據(jù)庫的發(fā)展壯大，需要有相應(yīng)的近似查詢處理方法來解決這樣的模式與序列的匹配問題，這也正是本文的研究所要解決的問題。
　　本文針對提交的查詢分別為生物序列和以得分矩陣表示的生物序列模式這兩種不同的情況，將支持得分矩陣的

3、近似查詢分為在線和離線兩種情況。在在線的情況中，本文以順序前瞻算法為基礎(chǔ)，總結(jié)了查詢處理過程中的過濾原理，分析了兩種可能的優(yōu)化策略，并結(jié)合這兩種優(yōu)化的過濾策略提出了多矩陣的前瞻過濾算法。該算法首先對所有輸入矩陣進行預(yù)處理，構(gòu)造一個總的過濾自動機，之后以該自動機掃描序列，從中尋找與輸入矩陣匹配的序列片段。在離線的情況中，本文以后綴樹索引結(jié)構(gòu)為基礎(chǔ)，提出了基于后綴樹的多矩陣查詢算法。該算法對一次查詢所提交的所有得分矩陣進行預(yù)處理，之后通過對