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

有效

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

1.一種基于序列模式挖掘算法的系統發生樹構建方法，其特征在于，包括如下步驟：

步驟1：挖掘隱藏在序列集中能夠用于衡量序列相似性的頻繁序列模式，得到初始模式集；

步驟2：過濾初始模式集中的非閉合頻繁模式，得到能夠代表序列集的優化模式集；然后構造模式向量集，再計算模式向量之間的距離，進而構建距離矩陣；根據距離矩陣生成最終需要的系統發生樹；

其中，步驟2中，構造模式向量集時，若構造賦有權重信息的模式向量，采用利用模式的長度信息的方式、去除模式之間的重疊部分的方式、對模式進行合并及擴展操作的方式、組合具有先后順序的模式為大模式的方式中的一種或幾種構造賦有權重信息的模式向量；

采用利用模式的長度信息的方式構造賦有權重信息的模式向量時，權重通過以下公式計算得到；

其中，W為權重，PatLength表示當前模式的長度，DBSize和PatSup分別表示序列數據庫的大小和當前模式的支持度大小。

2.根據權利要求1所述的一種基于序列模式挖掘算法的系統發生樹構建方法，其特征在于，步驟1的具體步驟如下：

第一，根據輸入序列集大小、序列類別以及序列長度信息，設定模式挖掘過程中支持度參數、精確匹配與模糊匹配位參數，指定輸入文件名及路徑、輸出特征集文件名及路徑以及輸出距離矩陣文件名及路徑；

第二，根據設定的支持度參數、精確匹配與模糊匹配位參數，通過序列模式挖掘算法對序列集進行挖掘，得到初始模式集。

3.根據權利要求2所述的一種基于序列模式挖掘算法的系統發生樹構建方法，其特征在于，通過序列模式挖掘算法對序列集進行挖掘的具體過程為：初始模式以一個空模式和其相對應的空投影數據庫開始模式增長過程，在模式增長的過程中，陸續保留那些滿足支持度參數、精確匹配與模糊匹配位參數的頻繁模式；相應的投影數據庫迭代更新，直到投影數據庫無法更新以滿足支持度參數，模式停止增長，得到初始模式集。

4.根據權利要求1所述的一種基于序列模式挖掘算法的系統發生樹構建方法，其特征在于，步驟2中，構造模式向量集時：將初始模式集中每條序列轉換為二進制的模式向量的形式，或是利用模式自身所含信息量的多少來將序列轉換為賦有權重信息的模式向量的形式。