[發(fā)明專利]一種基于多序列比對遺傳算法的處理方法及裝置

無效

• 申請?zhí)枺?/td>: 201210045408.1
• 申請日: 2012-02-27
• 公開（公告）號: CN102622535A
• 公開（公告）日: 2012-08-01
• 發(fā)明（設計）人: 賈鐵軍
• 申請（專利權(quán)）人: 上海電機學院
• 主分類號: G06F19/24
• 分類號: G06F19/24;G06N3/12
• 代理公司: 上海思微知識產(chǎn)權(quán)代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

技術領域

本發(fā)明涉及信息處理技術領域，特別涉及一種基于多序列比對遺傳算法的處理方法及裝置。

背景技術

目前，序列比對(Sequence?Alignment，SA)是分析探究生物信息本質(zhì)特征最基本、最重要的一項關鍵技術，通過序列比對可以發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進化等重要信息。多序列比對(Multiple?Sequence?Alignment，MSA)是生物信息中對多重序列進行比對的基本的有效方法，具有極為重要而廣泛的應用，對于其他相近或相關學科在特征信息識別、檢測、故障診斷、制藥醫(yī)療和信息處理等方面也有較好地應用和重要的借鑒作用。

生物序列的比對是生物信息學中最基本、最重要的一項處理工作，通過序列比對可以揭示并發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)以及進化信息，在序列分析、基因識別、蛋白質(zhì)結(jié)構(gòu)預測、生物進化樹的構(gòu)建等領域中有著廣泛的應用。生物序列的信息量巨大，對其進行比對操作花費時間太大，所以，序列比對的啟發(fā)式算法與并行計算已經(jīng)成為研究的一個熱點問題。現(xiàn)在，國內(nèi)外在序列比對算法的方面的研究，主要采用為確定多個序列之間的相似性及同源性，而將它們按照一定的規(guī)律排列與比較，其計算量與信息處理繁雜程度非常獨大，采用傳統(tǒng)一般方法根本無法實現(xiàn)。將多個序列排列一起標明其相似之處。序列中可以插入間隔(常用“-”表示)。對應的相同或相似的符號(在核酸中是A，T/U，C，G，在蛋白質(zhì)中是氨基酸殘基的單字母表示)排列在同一列上。比對中錯配與突變相應，空位與插入或缺失對應。這一方法常用于研究由共同原祖進化而來的序列，特別是如蛋白質(zhì)序列或DNA序列等生物序列。序列比對還可用于語言進化或文本間相似性之類的研究。

生物信息學是一門新興的交叉學科，所研究的對象是生物學的觀測數(shù)據(jù)，研究方法則是從各種計算模型技術衍生出來的.數(shù)學中的各個領域如統(tǒng)計學、概率論、運籌學、計算數(shù)學等均在生物信息學中有廣泛的應用。雖然在序列比對的啟發(fā)式算法與并行計算新技術、新方法、新應用層出不窮，如多重序列比對的遺傳算法、蟻群求解算法Ant-Align、聚類分析法、粒子群算法、模擬退火算法、A星算法、傅立葉變換法等，但是，在比對精度、速度、穩(wěn)定性等方面都有一定程度的缺陷或不足，特別是在具體關鍵算法方面需要進行進一步改進、創(chuàng)新和完善。由于生物序列較長，求解序列比對特別是多重序列比對的計算復雜度較高。可以證明，即使對于最簡單的計分函數(shù)，尋找最優(yōu)的多重序列比對也是一個NP-完全問題。在實際計算中不太可能用精確的算法求得多重序列的準確比對，而只能用啟發(fā)式的算法在合理的時間內(nèi)求得近似解。本文研究了對生物序列如何用啟發(fā)式的算法，在綜合考慮解的正確性以及計算速度兩方面因素的前提下，求得質(zhì)量較高的多序列比對。

目前，國內(nèi)外雖然在序列比對的啟發(fā)式算法與并行計算新技術、新方法、新應用層出不窮，如多重序列比對的遺傳算法、蟻群求解算法Ant-Align、聚類分析法、粒子群算法、模擬退火算法、A星算法、傅立葉變換法和其他神經(jīng)網(wǎng)絡等方法及單一算法，但是，在比對精度、速度、穩(wěn)定性等方面都有一定程度的缺陷或不足，特別是在具體關鍵算法方面需要進行進一步改進、創(chuàng)新和完善。，有效的解決了局部收斂的問題，加強了算法尋求全局最優(yōu)解的能力，但是，在比對精度、速度、穩(wěn)定性等方面都有一定程度的缺陷或不足。目前，采用的單一粗糙集(Roug?Set，RS)處理處理模糊性與不確定性信息技術，或LVQ神經(jīng)網(wǎng)絡分類識別算法，雖然在局部最優(yōu)解收斂等某些方面有所提高，但在多序列比對效率和速度方面尚有不足。

針對現(xiàn)有技術遺傳算法存在的收斂慢和易陷入局部最優(yōu)的不足，以及目前屬性約簡算法計算復雜度高，不適合規(guī)模數(shù)據(jù)約簡的弱點和在描述屬性集合等方面的不足的問題，提出一種基于多序列比對遺傳算法的處理方法及裝置是信息處理技術領域目前急待解決的問題之一。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明實施例提出了一種基于多序列比對遺傳算法的處理方法及裝置，通過構(gòu)建簡約分類識別模型，并對具體的實際問題確定參數(shù)集，接著對確定的參數(shù)集進行編碼設計，然后簡約分類初始化后的子種群，最后對子種群進行算法計算并判斷其性能，依據(jù)判斷結(jié)果進行處理，本方案有助于高效比對識別，彌補了遺傳算法存在的收斂慢和易陷入局部最優(yōu)的不足，以及目前屬性約簡算法計算復雜度高，不適合規(guī)模數(shù)據(jù)約簡的弱點和在描述屬性集合等方面的不足，提高了處理效率。

為解決上述技術問題，本發(fā)明實施例的目的是通過以下技術方案實現(xiàn)的：

一種基于多序列比對遺傳算法的處理方法，包括：

步驟一、構(gòu)建簡約分類識別模型；