交叉分片技術(shù)在DNA序列挖掘中的應(yīng)用.pdf

1、數(shù)據(jù)挖掘是致力于數(shù)據(jù)分析和理解、揭示數(shù)據(jù)內(nèi)部蘊藏知識的技術(shù)，它成為未來信息技術(shù)應(yīng)用的重要目標(biāo)之一。經(jīng)過十幾年的努力，數(shù)據(jù)挖掘產(chǎn)生了許多新概念和方法，相應(yīng)研究向著更深入的方向發(fā)展，并被不斷被應(yīng)用到新的領(lǐng)域。生物技術(shù)是21世紀(jì)研究的重點之一。由于生物數(shù)據(jù)種類多，維數(shù)高，結(jié)構(gòu)復(fù)雜，因此生物數(shù)據(jù)的分析成為生命科學(xué)研究的瓶頸。近年來地研究表明，把數(shù)據(jù)挖掘技術(shù)于應(yīng)用到生物學(xué)研究領(lǐng)域，是解決生物數(shù)據(jù)的處理、分析、挖掘和理解的重要途徑之一。DNA序列是

2、生物信息最主要的載體，攜帶著大量的遺傳信息，因此破譯DNA遺傳密碼對生命科學(xué)的研究有著重要科學(xué)意義。 本文的研究主要集中在DNA序列分析中的數(shù)據(jù)挖掘算法研究、設(shè)計以及相關(guān)的原型系統(tǒng)的實現(xiàn)上。一般地說，DNA序列是不同質(zhì)的，存在編碼區(qū)(CodingRegion)和非編碼區(qū)(Non-CodingRegion)，編碼區(qū)和非編碼區(qū)的邊界稱為變異點(ChangePoint)。編碼區(qū)攜帶著重要的遺傳信息，是DNA分析的主要方面。然而，DNA

3、序列中的編碼區(qū)需要通過分析才能加以界定，因此尋找編碼區(qū)和非編碼區(qū)的變異點是DNA序列分析中的一個基礎(chǔ)而重要的工作。分片技術(shù)是用于尋找變異點的常用方法，而不交叉分片方法又是目前普遍采用的技術(shù)。采用不交叉分片，當(dāng)變異點恰好在分片交界處時，容易查找到錯誤的變異點，本文采用交叉分片方法來解決這一問題，分析DNA序列。 本文的研究是在廣泛使用的信息熵方法和最小描述長度(MDL)方法基礎(chǔ)上進行的。信息熵方法是一種廣泛使用的有限字符分類方法，

4、經(jīng)常結(jié)合分治法完成對DNA序列特征的全局描述。它的主要問題是處理時間的復(fù)雜度偏高。MDL方法嘗試采用最優(yōu)的分片長度，具有實現(xiàn)簡單、效率高等優(yōu)點。但是，MDL方法相對于分治法精度偏低，而且目前普遍使用的不交叉技術(shù)可能導(dǎo)致分片邊界點的變異點的丟失。本文主要解決的問題有：首先，針對傳統(tǒng)的MDL方法可能導(dǎo)致分片邊界處的變異點無法跟蹤的情況，我們引入交叉分片技術(shù)，并設(shè)計、實現(xiàn)和評估了相應(yīng)的算法；其次，針對典型MDL方法的精度偏低的問題，將分治法和