[發明專利]一種基于序列模式挖掘算法的系統發生樹構建方法

有效

• 申請號: 201811408608.2
• 申請日: 2018-11-23
• 公開（公告）號: CN109545283B
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 葉凱;康永永;楊曉飛;賈鵬;藺佳棟;郭立
• 申請（專利權）人: 西安交通大學
• 主分類號: G16B40/00
• 分類號: G16B40/00;G16B30/00
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 安彥彥

一種基于序列模式挖掘算法的系統發生樹構建方法，包括挖掘隱藏在序列集中能夠用于衡量序列相似性的特異模式，得到初始模式集；過濾初始模式集中的非閉合頻繁模式，得到更能夠代表序列集的優化模式集；然后構造模式向量集，再計算模式向量之間的距離，進而構建用于生產系統發生樹的距離矩陣。本發明采取序列模式挖掘算法來提取序列集中頻繁出現的序列模式，然后利用過濾后的模式集將序列集轉換為二進制或是賦有權重信息的模式向量集的形式計算距離矩陣，后而構建系統發生樹。對大規模、低相似度的序列集，利用模式增長的策略可以挖掘序列集中更具代表性的模式，避免了提取對衡量序列相似性無用的冗余模式，優化了全局范圍內序列之間相似性的衡量。

技術領域

本發明涉及一種系統發生樹構建方法，具體涉及一種基于序列模式挖掘算法的系統發生樹構建方法。

背景技術

自上世紀八十年代開始，伴隨計算機技術，測序技術和分子生物學的不斷發展，各國研究人員實施完成了多項基因組計劃，通過基因組測序、蛋白質測序和結構解析等方法，積累了大量分子生物學數據。然而面對這些以指數速率增長的數據，研究者卻只獲得了少量有價值的信息，大量具有生物學意義的潛在信息淹沒在各種各樣的數據庫中，人們分析處理數據的能力已經遠落后于數據產生的能力。這就迫切需要計算能力更強大，硬件價格更優惠的計算設備以及數據分析研究者開發出復雜度更低、結果更優的算法來幫助人們分析處理各種各樣的測序數據。面對種類繁多的測序數據，快速，高效地挖掘具有生物學意義的序列信息，已經是一個科學研究的熱點問題，其中通過序列比對的方法，確定DNA、RNA、蛋白質序列之間可能的結構、功能、進化上的相似性是生物信息學中一個重要的基礎研究。通過將未知序列和已知序列進行相似性比較，可以推測未知序列所具有的功能和特點，因為相似的序列很可能具有相似的結構，相似的結構也很可能具有相似的功能。以進化學說為理論基礎，借助序列比對結果，如果比較的兩條序列之間相似性足夠高，那么就可推斷這兩條序列從同一個祖先進化而來，在進化分析中意義重大。

分子生物學中構建系統發生樹一個重要且關鍵的步驟就是對序列進行相似性比較。衡量序列之間的相似性關系，目前的技術策略主要可分為基于多序列比對的方法和非序列比對的方法。

1，基于多序列比對的方法。

比較兩條或是多條序列之間是否相似，傳統方法一般采用基于動態規劃算法的方法。簡單來說，多序列比對的過程就是通過在序列中插入空格的方式，來讓序列中更多相似的區域對齊的過程。這在序列相似度較高，序列集較小的時候，通常可以得的一個可靠的比對結果。但隨著分子生物學的快速發展，人們測序積累了大量不同物種不同器官組織的序列數據，一次比對任務，參與比對的序列數目成百上千，且序列間的相似性可能很低，這就導致傳統的比對方法，無法得到一個可靠的比對結果，或是直接無法比對。代表性的多序列比對工具有ClustalW家族軟件和MUSCLE等。然而隨著人們對復雜進化途徑的理解和關于生物序列性質的熟悉，僅僅采用基于多序列比對的序列比較方法的缺點逐漸顯露。主要有以下幾點：

(1)基于比對的序列比較方法假設同源序列包含一系列線性排列和或多或少保守序列的延伸，然而這些假設通常與現實情況相違背。

(2)進化過程中，隨著序列不斷積累單堿基突變和一些小片段的插入和刪除，序列之間的相似度越來越低，當序列相似性低于一定臨界點時，基于比對方法的準確性將迅速降低，甚至無法比對。

(3)由于大多數多序列比對方法基于動態規劃算法，時間復雜度高，資源占用多，尤其當有大規模低相似度的序列需要比對時，將是一個耗時耗力的過程。同時多序列比對計算是一個NP-hard問題。

(4)最終的比對結果會受到多個因素的影響，比對指導樹的構建，替換計分矩陣的選擇，空位罰分機制的設定等一些先驗假設。

(5)兩條序列之間的距離過度依賴于那些已經對齊的區域，忽略了一些本身含有一定生物學意義的序列片段。

2，非比對的方法。