[發明專利]大型系統進化樹的加速方法及裝置

在審

• 申請號: 202211241923.7
• 申請日: 2022-10-11
• 公開（公告）號: CN115691656A
• 公開（公告）日: 2023-02-03
• 發明（設計）人: 孟珍;張波;鄭玲璐;陳艷;胡智龍;汪嘉葭
• 申請（專利權）人: 中國科學院計算機網絡信息中心
• 主分類號: G16B10/00
• 分類號: G16B10/00;G16B40/30
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 陳艷

1.一種大型系統進化樹的加速方法，其特征在于，所述方法包括：

獲取系統進化樹中所有節點的屬性；其中，所述屬性包括：橫向坐標、縱向坐標、父節點、子節點、可見狀態和半徑，所述可見狀態的初始值為當前節點可見；

基于所述橫向坐標和所述縱向坐標，對所述系統進化樹的葉子節點進行聚類，以獲取離群點和節點簇；

在一個節點的子孫葉節點全部屬于一個所述節點簇，且所述子孫葉節點的數量不小于一數量閾值的情況下，將該節點作為一新的葉節點，且將所述子孫葉節點的所述可見狀態設置為當前節點不可見，以得到新的系統進化樹；其中，所述新的葉節點的半徑基于所述子孫葉節點的數量得到；

針對所述新的系統進化樹，通過判斷每一葉子分支是否因被其它節點覆蓋而導致不可見，獲取該葉子分支中各節點的可見狀態；

基于每一葉子分支中各節點的可見狀態，生成所述系統進化樹的加速結果。

2.如權利要求1所述的方法，其特征在于，所述獲取系統進化樹中所有節點的屬性，包括：

讀取系統進化樹的Newick格式文件，并轉換為JSON結構；

基于所述JSON結構初始化系統進化樹，并從所述系統進化樹的根節點開始，遍歷所有節點，記錄每個節點對應的父節點；

設定橫向縮放倍率SCALE_X、縱向縮放倍率SCALE_Y；

設置葉節點位置為(X，Y)＝(TOTAL_DISTANCE*SCALE_X，COUNT*SCALE_Y-BIAS_Y)；其中，TOTAL_DISTANCE表示當前節點到根節點之間所有路徑的路徑長度之和，COUNT為當前遍歷的葉節點的數量，BIAS_Y為Y軸方向上的偏移；

從葉節點回溯遍歷父節點直到根節點，并且當前遍歷的節點的位置為(X，Y)＝(TOTAL_DISTANCE*SCALE_X，(MIN_SON_Y+MAX_SON_Y)/2)；其中，MIN_SON_Y和MAX_SON_Y分別為子節點在Y方向的最小坐標值和最大坐標值；

層次遍歷所有節點和分支，設置所有節點為可見狀態。

3.如權利要求1所述的方法，其特征在于，所述基于所述橫向坐標和所述縱向坐標，對所述系統進化樹的葉子節點進行聚類，以獲取離群點和節點簇，包括：

設置第一超參數MIN_SAMPLES、第二超參數EPS，并設置輸入為所述系統進化樹中所有的葉節點；其中，所述第一超參數MIN_SAMPLES為一個簇中最少的樣本數量，所述第二超參數EPS為掃描半徑；

利用所述第一超參數MIN_SAMPLES和第二超參數EPS，對所有的葉節點執行DBSCAN算法，得到若干節點簇和離群點；其中每一節點簇中包含若干個葉節點。

4.如權利要求1所述的方法，其特征在于，所述在一個節點的子孫葉節點全部屬于一個所述節點簇，且所述子孫葉節點的數量不小于一數量閾值的情況下，將該節點作為一新的葉節點，且將所述子孫葉節點的所述可見狀態設置為當前節點不可見，以得到新的系統進化樹，包括：

設定數量閾值MIN_NODES，初始化列表TEMP_LIST為空；

對于每個類中的節點，從根節點開始層次遍歷，如果一個分支的子孫葉節點全部屬于一個節點簇，且這些子孫葉節點的數量大于或等于MIN_NODES個點，則設置該節點為的可見狀態修改為臨時狀態

對于每個節點簇中的節點，從根節點開始層次遍歷；

如果一個節點的子孫葉節點全部屬于一個所述節點簇，且所述子孫葉節點的數量大于或等于所述數量閾值MIN_NODES，則將所述節點的可見狀態修改為臨時狀態之后，加入到所述列表TEMP_LIST；

遍歷所述列表TEMP_LIST，將節點的可見狀態修改為當前節點可見，且基于節點的子孫葉節點的數量設置節點的半徑之后，將該節點作為新的葉節點，以得到新的系統進化樹。