图论中一些基本的定义:
连通、连通图和连通分量
在无向图中,若从顶点a到顶点b有路径,则认为a和b是连通的。如果图中任意两个顶点都是连通的,则认为图为连通图。图中极大连通图子图称为图的连通分量
强连通图和强连通分量
把上述思想用在有向图中,就换成强连通图和强连通分量
双连通分量
包括双边连通分量和双点连通分量,其实就是任意两点直接有至少存在两条路径使得边不重复或者使得点不重复。
论文中的feature tree的表示形式
feature tree 有两种特性:
1、存在高分辨和低分辨之分,其实也就是subtree的大小可以调节; 2、适用于比对算法(所以当时提出的原因就是用来做分子的相似度计算) 所以node部分等价于fragement
关于feature tree 的形成
1.找到rings中最小环数的环(6/5上图中左右分子),组成cycle-graph的node,如果cycle-graph不是tree,则继续寻找图中的双连通分量,如图中3块,用node替换,组成tree即可。
2.图下中,为了避免b在加入共享原子数目信息之后,会形成一个cycle,就可以加入一个node去使他变成星型结构。这个node并不包含原子,所以又被称为zero-node。
关于相似度计算
这部分并不是我关注的重点,所以并没有仔细研究;大概是加入了tree中node的原子数、范德华体积、作用类型等属性,然后比对分析,计算两个分子之间的相似度。