1、生物信息學(xué)是20世紀(jì)80年代末，隨著人類基因組計(jì)劃的不斷發(fā)展、基因序列和蛋白質(zhì)數(shù)據(jù)的急速增加、以及信息理論和計(jì)算機(jī)技術(shù)的不斷發(fā)展而逐漸形成的。我們可以利用計(jì)算機(jī)技術(shù)對包括DNA、RNA和蛋白質(zhì)等生物序列進(jìn)行分析，為生物學(xué)家提供更多有價(jià)值的信息。 在DNA序列分析中，重復(fù)片段查找是一個(gè)重要的基礎(chǔ)性問題。人類DNA序列50％以上是由重復(fù)片段組成的，這些重復(fù)片段隱含了大量的生物信息，其中包含豐富的古生物記錄，并提供許多關(guān)鍵的生物進(jìn)化線

2、索。目前，重復(fù)片段作為一個(gè)重要的遺傳標(biāo)記，已廣泛運(yùn)用于精密遺傳連鎖作圖、腫瘤生化研究、法醫(yī)學(xué)個(gè)體識(shí)別、親子鑒定和群體遺傳學(xué)分析等領(lǐng)域。 相似性重復(fù)片段的查找是近年來一個(gè)熱點(diǎn)的研究問題。相比于精確重復(fù)片段查找，相似性重復(fù)片段的查找是一個(gè)較為新穎且難度較大的問題。針對這個(gè)問題，本文對DNA序列中的相似性重復(fù)片段查找進(jìn)行了深入研究，提出了一種在DNA序列中查詢相似性重復(fù)片段的高效方法。本文的主要工作總結(jié)如下： (1) 本文首先

3、提出了一種新的衡量相似性重復(fù)片段相似性的標(biāo)準(zhǔn)，這種新的標(biāo)準(zhǔn)既表達(dá)了距離和待比較片段間的長度關(guān)系，同時(shí)又避免了模式之間長度必須相同的限制； (2) 針對以往方法只能查找模式長度基本相同的相似性重復(fù)片段的缺陷，利用一種新的輕量級(jí)索引結(jié)構(gòu)——后繼數(shù)組，提出了一種新的序列劃分方法，這種方法可以使查找到的相似性重復(fù)片段的各個(gè)模式的長度不受限制； (3) 由于相似性重復(fù)片段查找的計(jì)算的高復(fù)雜性，本文提出了基于頻率距離的過濾方法，