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

在審

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

本發明公開了一種大型系統進化樹的加速方法及裝置，所述方法包括：獲取系統進化樹中所有節點的屬性；基于橫向坐標和縱向坐標，對系統進化樹的葉子節點進行聚類，以獲取離群點和節點簇；在一個節點的子孫葉節點全部屬于一個所述節點簇，且所述子孫葉節點的數量不小于一數量閾值的情況下，將該節點作為一新的葉節點，且將所述子孫葉節點的所述可見狀態設置為當前節點不可見，以得到新的系統進化樹；針對所述新的系統進化樹，通過判斷每一葉子分支是否因被其它節點覆蓋而導致不可見，獲取該葉子分支中各節點的可見狀態，以生成所述系統進化樹的加速結果。本發明避免了大型系統進化樹可視化時扎堆折疊的現象。

技術領域

本發明屬于應用生物信息學技術領域，涉及一種大型系統進化樹的加速方法及裝置。

背景技術

系統進化樹在生物學研究中是必不可少的，它將物種或種群以層次結構關聯起來，可用來闡明生物的進化形式、各大門類生物的親緣關系、以及生物的動態變化規律。系統進化樹在應用層面有積極的意義，比如用于預測哪些物種正在消亡，人們可以據此做出相應的防范措施；幫助識別具有藥理學意義的物種的相關的具有密切關系的成員；對包括細菌在內的各種微生物進行識別和分類等。

目前已有超過8萬種物種被分析了進化關系，而多達超過100萬種物種仍未被分析進化關系，這表明了對物種進化關系進行分析的市場依然巨大。生物信息學領域已有許多針對系統進化樹可視化的工具，如iTOL v5、PhyD3、PhyloTree等，它們在元數據可視化、軟件可移植性、功能擴展性上十分優秀。但同時，由于高通量測序技術和人工智能技術的發展，海量的生物信息數據被創造出來，系統進化樹的規模也在不斷增加，為了提高大規模系統進化樹的可視化效率，需要采用一些加速方法。而如何設計這種加速方法，則是一個亟待解決的問題。

現有的系統進化樹工具在可視化系統進化樹時，往往是將所有的節點與分支全部繪制出來，這樣做的好處是可以保留原始進化樹的全部特征，不因為縮放而產生失真的情況。但是這種方法的效率會比較低下，尤其是在處理大型系統進化樹的場景下，研究人員面對的系統進化樹的大小從以往的不到1000個葉節點增長到超過10萬個葉節點，這類大型進化樹可視化效率十分低下，以致不能滿足研究人員對大型系統進化關系的分析需求。

為了提高大型系統進化樹的可視化效率，生物信息學領域對此進行了長期的探索，目前的方案主要集中在折疊子樹上，即通過將大型進化樹的某些較大的子樹折疊，以減少需要渲染的節點數量和分支數量。這種方法雖然可以實現大型進化樹的加速，但是它們折疊的子樹往往會具有較多的特性，以iTOL為例，它會將擁有超過200個節點的子樹自動折疊，扎推性折疊會使這些子樹包含的大量特性消失，從全局來看，葉節點對于系統進化關系的分析十分重要，而折疊方法加速后的系統進化樹無法體現原始系統進化樹葉節點的特征。此外，生物進化學使用聚類方法來推斷物種之間的分類關系，而由于聚類方法的分組特點，結合聚類方法將大型進化樹的葉節點進行分組并加速的方法具有廣闊的應用前景。

因此，面對系統進化樹規模越來越大、大型系統進化樹可視化場景越來越多的現狀，提出一種大型系統進化樹加速并盡可能保留葉節點特征的方法具有重要意義。

發明內容

本發明針對大型系統進化樹可視化效率過低的情況，提出了一種大型系統進化樹的加速方法及裝置，主要應用于大型系統進化樹可視化、大型系統進化關系探索、大規模物種劃分等相關領域的大型系統進化樹加速方法。

本發明的技術內容包括：

一種大型系統進化樹的加速方法，所述方法包括：

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

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