Similar Supergraph Search Based on Graph Edit Distance
Similar Supergraph Search Based on Graph Edit Distance
复制标题
DOI：
10.3390/a14080225
复制
发表时间：
2021-07
期刊：
影响因子：
2.3
通讯作者：
Masataka Yamada;Akihiro Inokuchi
中科院分区：
文献类型：
--
作者：
Masataka Yamada;Akihiro Inokuchi
子图和超级搜索方法是用于开发新药的有前途的技术，例如，粉状疗法的化学结构（一种用于影响的抗病毒治疗）对象构成了RNA的某些组件的结构。但是，Favipiravir。搜索并设计有效的算法来解决该问题。代码树，它用于有效地编辑距离，我们的算法等于现有的有效算法，以进行精确的超级搜索实验表明，随着距离阈值的增加，计算时间呈指数增加，但随数据库中的图数量增加。
Subgraph and supergraph search methods are promising techniques for the development of new drugs. For example, the chemical structure of favipiravir—an antiviral treatment for influenza—resembles the structure of some components of RNA. Represented as graphs, such compounds are similar to a subgraph of favipiravir. However, the existing supergraph search methods can only discover compounds that match exactly. We propose a novel problem, called similar supergraph search, and design an efficient algorithm to solve it. The problem is to identify all graphs in a database that are similar to any subgraph of a query graph, where similarity is defined as edit distance. Our algorithm represents the set of candidate subgraphs by a code tree, which it uses to efficiently compute edit distance. With a distance threshold of zero, our algorithm is equivalent to an existing efficient algorithm for exact supergraph search. Our experiments show that the computation time increased exponentially as the distance threshold increased, but increased sublinearly with the number of graphs in the database.