交叉分片技術在DNA序列挖掘中的應用.pdf

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

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

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

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