一种用于量化生物进化树间相似度的算法

摘要

本发明公开了一种用于量化生物进化树间相似度的新算法。属于生物信息学和进化生物学领域。依据本发明中关于生物进化树间相似度的度量方法步骤和实施方案，提出了具体计算生物进化树相似度的方法，为生物学领域中生物进化树的物种间系统发育及相关方法研究、类似的树形结构图之间的比较研究提供参考。

说明书

一.发明领域

本发明属于生物学大学科下的生物信息学和进化生物学研究领域，更具体地说，涉及一种用于衡量生物进化树间的相似程度的估算方法。

二.背景技术

20世纪以来，分子生物学发展迅猛，特别是随着计算机科学和生物技术在生物学的广泛应用。进化生物学中的分子系统学也随着测序技术和生物分子数据的积累飞速发展。其中，构建生物进化树(又名：分子系统树，系统发育树等)是进行物种间系统发生推演或是亲缘关系研究的一个重要手段。随着构建和分析进化树的方法不断被发明，如最大似然法(Maximum likelihood，ML)，邻接法(Neighbor-Joining，NJ)，最大简约法(Maximumparsimony，MP)，贝叶斯推断(Bayesian inference，BI)等，目前开展进化树分析的研究也逐渐趋于这样一个情况：利用至少两种或是两种以上的方法构建出一致性较高的进化树才会被领域内认为是可信的。因此，比较分析两颗甚至多颗进化树的相似性(或称为一致性)对于任何一项进化分析研究来说都是不可避免的。

然而，据我们所知，到目前为止仍然没有一款用于横向比较两颗进化树相似度的计算方法或是软件。肉眼目测是最为常规的比较分析两颗进化树的方法。肉眼法对于小数量物种的进化树比较分析并不困难，然而，随着大数据时代到来，分子生物学研究构建的进化树涉及的物种数目已从上世纪的十几个物种到几十个物种发展到如今的几百个甚至上千个物种。肉眼观察和对比分析往往需要研究者富有极大的耐心和细心，一款能全面分析两颗进化树间的相似程度的算法亟需被提出。

基于此，本发明致力于提出一种用于量化生物进化树间相似度的算法，用于表征两颗进化树间的多项相似性程度指标。它包括：

“结构相似性程度”指标(SS)，“树形相似性程度”指标(ST)，和“关系相似性程度”指标(SR)3个子算法指标，这些度量指标将有助于全面考察两颗进化树的相似性程度，为生物信息学和进化生物学的进化树比较研究提供量化方法，也为进化树相似度软件的开发提供新思路。

三.发明内容

1.发明要解决的问题

本发明要解决以下问题：第一，总体来看，提出一种用于量化生物进化树间相似度的算法，为进化树间的总体比较和量化相似度问题提供解决方案；第二，具体地，该方法细化了比较的指标，包括只考虑进化树端部物种间关系的比较描述指标，只考虑进化树树形相似程度的比较描述指标，和兼顾树形和物种两个方面的结构相似度的比较描述指标；另外，本发明还从进化树的全局性和局部性提出比较指标，可以全局性比较进化树间的结构相似性程度，还可以局部地去比较物种间的亲缘关系远近。这些可以为进化树研究者们提供多角度的比较方案，可以全方位评估两颗进化树的相似性程度。

2.技术方案

本发明提出了一种用于度量生物进化树间的结构相似性程度的方法，具体实施方案如下：

(1)待比较的进化树数据获取

为完成本专利提出的一种用于量化生物进化树间相似度的算法，以下基础数据需要进行事先处理和准备：

①对于没有进化树文件(newick格式，即括号形式的关系式，简写成“.nwk文件”)的情况，需要在获得待比较的两颗进化树图后，运用手工方法或是相关图形识别软件进行进化树图形信息转化，将图形数据转化为nwk格式的数据，用于后续数据的分析；

②对于可以获得到进化树文件(如.tre文件)的数据，需要通过相关进化树可视化软件(如FigTree软件)或是进化树构建软件(如MEGA软件)等将其转化为nwk文件，如果本身就是nwk格式则无需转化；

③对待研究的进化树支端物种进行分析，包括提取物种名信息，可以人工获取，或是利用相关识别软件进行获取；

④对提取的物种信息进行分析整理，步骤如下：其一，分别去除两颗进化树中的外群物种，它们可能会包括一至多个物种；其二，对两个进化树中的物种进行对比分析，保留共同物种；其三，将获得的共同物种名单放入nwk格式文件中，删除非共同物种及其对应的括号关系式。如图1(i)原关系式为：((((A,B),C),D),(E,F)),如果该关系式中A-F代表5个物种，F物种为非共同物种，那关系是就会自动塌陷为：((((A,B),C),D),E)。

(2)新算法使用

依据本专利提出的一种用于量化生物进化树间相似度的算法，以下为该方法可考察3项指标的具体实施步骤：

①度量两颗进化树的“结构相似性程度”指标计算方法如下：

其一，首先找出进化树nwk文件中的一个或多个最小分支(这里我们定义为只包含2-4个物种的分支类型)，该分支可以为图1中的a-h图中的任意一个，以此为最小单位，在此基础上进行逐步增加临近物种完成后续分析；

其二，以最小分支为基础，进行比对，找出完全一致(或高度相似的)的最小分支单元，如图1a和1b，就代表完全一致的关系，或者如图1f和图1g中的虚框中的A和B物种所在的最小分支单元；

其三，将相同的单元进行整体化处理，视为一个物种，再与邻近的物种形成最小分支单元，再次考察该分支单元中的关系，对于两个物种：如果其关系如图1a和图1b，则相似度SS＝100％；对于三个物种：如果关系如图1c，1d和1e中的任意两个，则它们之间的相似度SS＝0％，而如果两颗分支单元均属于1c，1d和1e中的任意1个，则相似度SS＝100％；对于四个物种：如果关系如图1f，1g和1h中的任意两个(注意：这里没有将4个物种的所有分支情况全部列出，其他情况以此类推)，则两个分支单元的相似度为33.33％。需要特别说明的是：如果待研究的树形如上文提及的情况，但是包含的物种并非完全相同，不同物种的比例需要去除掉(或是去除不同物种后计算比例)；还需注意的是：上述计算的比例应该考虑整体化之前的物种比例，而非整体化之后的比例；

其四，按照这样的方式遍历进化树上所有物种或是需要研究的部分物种，即可计算出两颗进化树整体或是局部的“结构相似性程度”的最终相似度比值。

②度量两颗进化树的“树形相似性程度”指标计算方法如下：

其一，首先找出进化树nwk文件中的最大分支，对该大分支包含物种数目进行统计(设其总数为n)，将两颗进化树中物种名相同的数目(m)占比在50％以上的最大分支归为待比较的对应分支。这里我们定义大分支内的树形可进一步归为两类：即分支类型或是嵌套类型，分别对应如图1h和1g所示。去除不同物种后，如果比较中的两类分别属于分支型和嵌套型，则表示树形不一致，相似度为ST＝0％，如果均属于一类分支，则树形为ST＝100％，之后，将树形ST值乘于其权重(m/Σn)获得该步的相似度比值；

其二，然后去除嵌套型树形的最外层物种，再次重复上述步骤；或是分别计算分支型树形的两支，按照上述步骤重复；对于两颗树中树形不一致，可以针对两种树形分别计算，选择该步获得相似度较大的一种结果作为该步的相似度比值；

其三，按照这种由大到小的剥离方式，将每一步的相似结果都计算出来，然后累加这些结果，获得最终的总树形相似性。

③度量两颗进化树的“关系相似性程度”算法指标计算方法如下：

其一，首先针对两颗树的对应物种或是对应类群(亦称为单元)进行两两关系计算，并用1，2，3，…N来表示两两之间的远近关系，如1表示两两间最近的亲缘关系(如图1c的A和B之间的关系)，2表示两两间存在一个间隔单元(如图1c的A和C之间的关系)，然后，分别针对对应两颗树中每个待检群，列举并计算出所有两两“单元对”及其关系。

其二，然后按照上述步骤，比较两颗树中两两关系对差异情况，根据物种或类群名称，统计出一致的“关系对”在所有关系对中的比例，该比值即为它们的关系相似性程度SR。

3.有益效果

采用本发明提供的一种用于生物进化树间的相似性程度的比较方法，具有如下具体有益效果：

(1)本发明是一种用于量化生物进化树间相似度的算法，其中包括提出了两颗进化树的“结构相似性程度”算法，该方法能有效比较涵盖物种与树形两类因素，兼顾全局和局部分析，可有效反映出两颗进化树间的相似性程度，为进化树在建树方法上或是研究结果上量化比较提供有效的分析方案。

(2)本发明是一种用于量化生物进化树间相似度的算法，其中包括提出了两颗进化树的“树形相似性程度”算法，该方法能有效比较进化树的树形本身间的拓扑学结构，兼顾考察树形的全局和局部，可有效聚焦树形本身的相似性情况，为进化树本身拓扑学的相似性比较提供有效的分析方案。

(3)本发明是一种用于量化生物进化树间相似度的算法，其中包括提出了两颗进化树中“关系相似性程度”算法，该方法能有效比较待测进化树中两两单元间的总体关系相似性情况，这里虽然只考察局部情况，但可以兼顾物种间或是类群间，为进化树中关键物种群或是关键“类群”的群间的两两关系精细分析提供有效的分析方案。

(4)本发明是一种用于量化生物进化树间相似度的算法，该方法还可以延伸推广至研究类似进化树的其他树形或分支图形间的比较分析，如层次聚类(HierarchicalClustering)分析方法中R语言利用H-clust()函数所产生的聚类树间的比较。

附图说明

图1为基于本方法进行生物进化树相似度比较研究的可能涉及到的各类进化树单元或进化树类型图；

图中的标号说明：(a)，(b)：只包含两个物种的进化树形；(c)，(d)，(e)：包含三个物种的进化树关系情况，其中(c)图标出该树形的两个节点及节点末端的三个物种，(d)和(e)标出了图中A和B物种间较远的亲缘关系；(f)，(g)，(h)：包含四个物种的进化树关系中的三种情况，其中(f)和(g)图标出两颗树形中A和B物种所在支具有相似的关系被虚线框出；(i)，(j)：包含6个物种的两颗进化树树关系图中的两种情况，它们被用于实施例中的进化树相似度的比较。

上述10颗进化树对应的newick格式文件如下：

(a):(A,B)；

(b):(B,A)；

(c):((A,B),C)；

(d):((A,C),B)；

(e):((B,C),A)；

(f):(((A,B),C),D)；

(g):(((A,B),D),C)；

(h):((A,B),(C,D))；

(i):((((A,B),C),D),(E,F))；

(j):(((((A,B),D),C),E),F)；

具体实施方式

为进一步了解本发明的内容，结合附图列举实施例对本发明作详细描述。

实施例

针对两颗进化树，在本实施例中将详细介绍利用本算法进行3种相似度衡量指标的分析计算，具体细节如下：

(1)获取进化树数据

本专利涉及的数据可由两种方式获得：①通过不同方法自行构建获得两颗包含物种相同的进化树；②对已发表的进化生物学研究领域的学术论文中的进化树图进行人工信息提取。

(2)数据预处理

根据进化树树形关系和物种信息，将待比较的进化树进行newick格式转化，然后根据该格式下的物种关系及物种名称进行后续分析。本实施例以图1例中的i和j两颗进化树为例，先写出它们的newick格式文件，如上文附图说明部分所示，即图1i为((((A,B),C),D),(E,F))，而图1j为(((((A,B),C),D),E),F)。

(3)计算两颗进化树i和j的“结构相似性程度”

首先找出最小分支单元(A,B)，发现该单元在两颗树中表现为关系一致，然后按照有小到大的顺序考察更大节点即((A,B),C)和((A,B),D)，发现该节点不一致，依此类推，直至比较到最外一层，最后将计算出结构相似性结果累加在一起，即为：SS＝(1+0+0+0+0)/5＝20％。需要说明的是，在计算过程中，树i还存在另一个最小分支单元(E,F)，将其与j树比较，该支结构相似度SS＝0％。

(4)计算两颗进化树i和j的“树形相似性程度”

先进行两颗树所有物种数目求和，及6个物种的和：1+2+3+4+5+6＝21，然后由大到小，由外至内开始逐项剥离。对于最外层，可以直接看出树形不一致，即为相似度为0，因此，最外层的ST＝0*(6/21)＝0；再看倒数第二层，i树为分支型，j树为嵌套型，可以分别计算。在该层中，分别计算的结果哪一个大，便以它为该步的相似度的结果。j树去掉最外层后，5个物种与i树的相似度仍为0。所以，再考虑i树的分支型，在分支型中，下支(E,F)与j树相似度为0，上支(((A,B),C),D)与j树的(((A,B),D),C)树形一致ST＝1*(4/21)＝19.04％；继续剥离可得两颗树的树形分别为((A,B),C)和((A,B),D)，因为C和D物种不同，此时即塌陷为最内层(A,B)，再发现此时这两者树形一致，因此ST＝1*(2/21)＝9.52％；最终获得两颗树的树形相似度ST＝0+19.04％+0+0+9.52％＝28.56％。

(5)计算两颗进化树i和j中A，B，C和D四个物种间的“关系相似性程度”

首先计算出A，B，C和D四个物种的可能关系包括6种情况(C(4,2)＝6)，分别是(A,B)，(A,C)，(A,D)，(B,C)，(B,D)和(C,D)这6种情况。对于i树中的A，B，C和D，可以计算出它们之间的远近关系为(A,B)＝1，(A,C)＝2，(A,D)＝3，(B,C)＝2，(B,D)＝3和(C,D)＝3。而对于j树6种情况的远近关系为(A,B)＝1，(A,C)＝3，(A,D)＝2，(B,C)＝3，(B,D)＝2和(C,D)＝3。，由此可以看出，6种关系中只有2个关系是一致的(即为：(A,B)＝1和(C,D)＝3)，因此它们四个物种的关系相似度SR＝2/6＝33.33％。