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

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

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

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