相似度计算装置、相似度计算方法和记录程序的记录介质

摘要

本公开内容涉及相似度计算装置、相似度计算方法和记录程序的记录介质。一种计算第一材料与第二材料之间的相似度的相似度计算装置，包括：创建单元，其创建冲突图，冲突图是这样的图形，该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边；搜索单元，其通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集；以及计算单元，其基于最大独立集计算第一材料与第二材料之间的相似度。

说明书

技术领域

本文讨论的实施方式涉及相似度计算装置、相似度计算方法以及程序。

背景技术

通常，具有相似结构的化合物(分子)被预期具有相似的特征(性质)。例如，在通过预测化合物的性质来设计具有预定性质的化合物时，或者在通过筛选化合物的数据库来搜索具有预定性质的化合物时，广泛使用“相似化合物具有相似性质”的这种相似性质原理。

例如，当使用相似性质原理时，通过利用已有的化合物作为查询化合物，可以预测：从数据库检索到的具有相似度的化合物(具有与查询化合物的结构相似的结构的化合物)与查询化合物具有相同的功能(特征和物理性质)。此外，当新化合物用作查询化合物时，通过在数据库中搜索具有与查询化合物的结构相似的结构的化合物，也可以预测新化学物质的特征值。

在此，可以例如通过评价化合物间的结构相似度并且将结构相似度高的化合物指定为相似化合物来执行针对彼此具有相似结构的化合物的搜索。

尽管已提出了各种技术作为用于评价化合物间的结构相似度的技术，但是例如指纹法(fingerprint method)被广泛使用。在指纹法中，例如，将查询化合物的子结构是否包含在待比较化合物中由0或1表示，并评价相似度。

此外，还提出了通过用退火机等求解由伊辛模型等式表示的冲突图(conflictgraph)中的最大独立集问题来搜索化合物公共的子结构的技术(例如，参照非专利文献1)，作为评价结构相似度的技术。

然而，该提出的技术在要计算的结构相似度的准确性方面具有用于检查的空间。另外，在该提出的技术中，随着构成化合物的原子的数量增加，要用于退火机的位数增加。

Hernandez,Maritza；Zaribafiyan,Arman；Aramon,Maliheh；Naghibi,Mohammad，“A Novel Graph-based Approach for Determining Molecular Similarity”，arXiv:1601.06693(https://arxiv.org/pdf/1601.06693.pdf)(非专利文献1)作为相关技术被公开。

在一个方面，本申请的目的是提供相似度计算装置、相似度计算方法和程序，其在要计算的结构相似度的准确性方面是优秀的，并且能够减少要用于计算的位数。

发明内容

根据实施方式的一个方面，一种计算第一材料与第二材料之间的相似度的相似度计算装置，包括：创建单元，其创建冲突图，该冲突图是这样的图形，该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边；搜索单元，其通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集；以及计算单元，其基于最大独立集计算第一材料与第二材料之间的相似度。冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，并且与元素种类相比，原子类型被更精细地细分。

根据实施方式的另一方面，一种计算第一材料与第二材料之间的相似度的相似度计算方法，包括：创建冲突图，该冲突图是这样的图形，该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边；通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集；以及基于最大独立集计算第一材料与第二材料之间的相似度。冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，并且与元素种类相比，原子类型被更精细地细分。

根据实施方式的又另一方面，一种计算机可读记录介质，其存储有程序，所述程序使计算机执行以下处理：创建冲突图，该冲突图是这样的图形，该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边；通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集；以及基于最大独立集计算第一材料与第二材料之间的相似度，其中，冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，并且与元素种类相比，原子类型被更精细地细分。

在一个方面，本申请可以提供相似度计算装置、相似度计算方法和程序，其在要计算的结构相似度的准确性方面是优秀的，并且能够减少要用于计算的位数。

附图说明

图1是示出了乙酸和乙酸甲酯如何表示为图形的示例的现有技术的图；

图2是示出在分子A和分子B中的相同元素被组合并被用作冲突图的节点的情况下的示例性组合的现有技术的图；

图3是示出用于在冲突图中创建边的示例性规则的现有技术的图；

图4是现有技术的图，示出了分子A和分子B的示例性冲突图；

图5是现有技术的图，示出了图形中的示例性最大独立集；

图6是现有技术的图，示出了在通过求出冲突图中的最大独立集来求出分子A和分子B的最大公共子结构(求解最大独立集问题)的情况下的示例性流程；

图7是用于说明在节点的数量为六的图形中搜索最大独立集的示例性现有技术的说明图；

图8是用于说明在节点的数量为六的图形中搜索最大独立集的示例性现有技术的说明图；

图9是现有技术的图，示出了冲突图中的示例性最大独立集；

图10是表示基于通用AMBER力场(GAFF)的原子类型来将乙酸和乙酸甲酯表示为图形的示例的图；

图11是表示基于GAFF原子类型从乙酸和乙酸甲酯的图形创建冲突图的节点的示例的图；

图12是根据图11所示的节点创建的冲突图；

图13是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分1)的图；

图14是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分2)的图；

图15是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分3)的图；

图16是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分4)的图；

图17是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分5)的图；

图18是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分6)的图；

图19是用于使用乙酸和乙酸甲酯作为示例来说明从读取分子结构到搜索最大独立集的示例性顺序(部分7)的图；

图20是表示本申请中公开的相似度计算装置的示例性配置的图；

图21是表示本申请中公开的相似度计算装置的另一示例性配置的图；

图22是表示本申请中公开的相似度计算装置的另一示例性配置的图；

图23是表示本申请中公开的相似度计算装置的另一示例性配置的图；

图24是示出作为本申请中公开的相似度计算装置的实施方式的示例性功能配置的图；

图25是本申请中公开的相似度计算的实施方式的流程图；

图26是示出在退火方法中使用的优化装置(控制单元)的示例性功能配置的图；

图27是以电路级示出转变控制单元的示例的框图；

图28是示出了转变控制单元的示例性操作流程的图；

图29是示出芳樟醇的化学结构的图；

图30是表示常规示例中的位数的图；以及

图31是表示示例中的位数的图。

具体实施方式

(相似度计算装置、相似度计算方法、程序)

本申请公开的相似度计算装置是计算第一材料与第二材料之间的相似度的装置。

相似度计算装置包括创建单元、搜索单元和计算单元，并且取决于状况，还包括其他单元。

创建单元创建冲突图。

冲突图是这样的图形：该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点，以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边。

搜索单元通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集。

计算单元基于最大独立集计算第一材料与第二材料之间的相似度。

这里，冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，原子类型与元素种类相比被更精细地细分。

本申请中公开的相似度计算方法是计算第一材料与第二材料之间的相似度的方法。

相似度计算方法包括创建处理、搜索处理和计算处理，并且取决于状况，还包括其他处理。

创建处理是创建冲突图的处理。

冲突图是这样的图形：该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点，以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边。

搜索处理是通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集的处理。

计算处理是基于最大独立集计算第一材料与第二材料之间的相似度的处理。

这里，冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，原子类型与元素种类相比被更精细地细分。

本申请中公开的程序包括使计算机执行创建处理。

创建处理是创建冲突图的处理。

冲突图是这样的图形：该图形具有由构成第一材料的相应原子与构成第二材料的相应原子的组合构成的多个节点，以及在多个节点中的两个节点之间形成的边，并且当两个节点被比较且彼此不相同时，该图形在这两个节点之间具有边，当两个节点被比较且彼此相同时，该图形在这两个节点之间不具有边。

这里，冲突图的多个节点均由在第一材料与第二材料之间原子类型相同的两个原子的组合构成，原子类型与元素种类相比被更精细地细分。

首先，在描述本申请中公开的技术的细节之前，将给出现有技术的描述，该现有技术搜索待比较材料的公共子结构，并通过以冲突图求解最大独立集问题来计算材料之间的相似度。

当通过以冲突图求解最大独立集问题来计算化合物之间的结构相似度时，通过将化合物表示为图形来处理化合物。在此，将化合物表示为图形是指，使用例如关于化合物中的原子(元素)的类型的信息和关于各个原子之间的键合状态的信息来表示化合物的结构。

化合物的结构可以使用例如MOL格式或结构数据文件(SDF)格式的表达来表示。通常，SDF格式是指通过收集关于以MOL格式表达的多个化合物的结构信息而获得的单个文件。此外，除了MOL格式结构信息之外，SDF格式文件还能够处理针对每种化合物的附加信息(例如，目录号、化学文摘服务(CAS)编号、分子量等)。可以以逗号分隔值(CSV)格式将这样的化合物的结构表示为图形，在CSV格式中，例如，“原子1(名称)，原子2(名称)，关于原子1的元素信息，关于原子2的元素信息，原子1与原子2之间的键序”都包含在单个行中。

以下，通过以创建乙酸(CH

首先，乙酸(下文中有时称为分子“A”)和乙酸甲酯(下文中有时称为“分子B”)表示为图形，并如图1所示给出。在图1中，形成乙酸的原子用A1、A2、A3和A5表示，并且形成乙酸甲酯的原子用B1至B5表示。此外，在图1中，A1、A2、B1、B2和B4表示碳，A3、A5、B3和B5表示氧，而用细实线表示单键，用粗实线表示双键。注意，虽然在图1所示的示例中，除氢以外的原子被选择并被表示为图形，但是当将化合物表示为图形时，包括氢的所有原子可以被选择并被表示为图形。

接下来，将表示为图形的分子A和分子B的顶点(原子)组合以创建冲突图的顶点(节点)。此时，如图2所示，分子A和B中的相同元素被组合并用作冲突图的节点。在图2所示的示例中，表示碳的A1、A2、B1、B2和B4的组合以及表示氧的A3、A5、B3和B5的组合被用作冲突图的节点。

在图2的示例中，通过分子A的碳和分子B的碳的组合创建六个节点，并且通过分子A的氧和分子B的氧的组合创建四个节点；因此，由表示为图形的分子A和B创建的冲突图中的节点的数量被给定为十个。

随后，创建冲突图中的边(edge)(分支或边(side))。此时，比较两个节点，并且当节点由彼此处于不同的状况(例如，原子序数、键的存在或不存在、键序等)的原子构成时，在这两个节点之间创建边。另一方面，当比较两个节点并且节点由相同状况下的原子构成时，在这两个节点之间不创建边。

这里，将参照图3描述用于在冲突图中创建边的规则。

首先，在图3所示的示例中，将描述是否在节点[A1B1]与节点[A2B2]之间创建边。从图3中表示为图形的分子A的结构可以看出，包括在节点[A1B1]中的分子A的碳A1和包括在节点[A2B2]中的分子A的碳A2相互键合(单键键合)。同样，包括在节点[A1B1]中的分子B的碳B1和包括在节点[A2B2]中的分子B的碳B2相互键合(单键键合)。例如，碳A1与A2之间的键合状况和碳B1与B2之间的键合状况彼此相同。

以这样的方式，在图3的示例中，分子A中碳A1和A2的状况和分子B中碳B1和B2的状况彼此相同，并且节点[A1B1]和[A2B2]被认为是由彼此处于相同状况的原子构成的节点。因此，在图3所示的示例中，在节点[A1B1]与[A2B2]之间没有创建边。

接下来，在图3所示的示例中，将描述是否在节点[A1B4]与节点[A2B2]之间创建边。从图3中表示为图形的分子A的结构可以看出，包括在节点[A1B4]中的分子A的碳A1和包括在节点[A2B2]中的分子A的碳A2相互键合(单键键合)。另一方面，如从表示为图形的分子B的结构可以看出，包括在节点[A1B4]中的分子B的碳B4和包括在节点[A2B2]中的分子B的碳B2具有夹在碳B4与B2之间的氧B3，并且不直接键合。例如，碳A1和A2之间的键合状况与碳B4和B2之间的键合状况彼此不同。

因此，在图3的示例中，分子A中碳A1和A2的状况与分子B中碳B4和B2的状况彼此不同，并且节点[A1B4]和[A2B2]被认为是由彼此处于不同状况的原子构成的节点。因此，在图3所示的示例中，在节点[A1B4]与[A2B2]之间创建了边。

以这样的方式，可以基于如下规则来创建冲突图：当节点由不同状况下的原子构成时，在这些节点之间创建边，并且当节点由相同状况下的原子构成时，在这些节点之间不创建边。

图4是示出分子A和B的示例性冲突图的图。如图4所示，例如，在节点[A2B2]和[A5B5]中，分子A中碳A2和氧A5之间的键合状况与分子B中碳B2和B5之间的键合状况彼此相同。因此，节点[A2B2]和[A5B5]被认为是由彼此处于相同状况的原子构成的节点，并且因此在节点[A2B2]和[A5B5]之间没有创建边。

这里，冲突图的边可以例如基于两种化合物的化学结构数据来创建，其中，将针对这两种化合物计算结构上的相似度。例如，当使用SDF格式文件输入化合物的化学结构数据时，可以通过使用计算器例如计算机、基于SDF格式文件中包含的信息执行计算来创建(指定)冲突图的边。

接下来，将描述如非专利文献1中描述的示例性现有技术中的以所创建的冲突图来求解最大独立集问题的方法。

冲突图中的最大独立集(MIS)意指构成冲突图的节点集中的这样的集：所述集包括数量最多的在节点之间没有边的节点。例如，冲突图中的最大独立集是指在由节点彼此之间不具有边的节点形成的集之中的大小(节点的数量)最大的集。

图5是示出图形中的示例性最大独立集的图。在图5中，包括在集中的节点用附图标记“1”标记，并且未包括在任何集中的节点用附图标记“0”标记；对于节点之间存在边的情况，节点由实线连接，而对于不存在边的情况，节点由虚线连接。注意，这里，如图5所示，为了简化说明，将节点的数量为六的图形作为示例进行描述。

在图5所示的示例中，在由节点之间没有边的节点构成的集合中，存在具有最大数量的节点的三个集，并且这些集的每一个中的节点的数量是三个。例如，在图5所示的示例中，由单点划线围绕的三个集被给出作为图形中的最大独立集。

这里，如上所述，基于如下规则来创建冲突图：当节点由不同状况下的原子构成时，在这些节点之间创建边，并且当节点由相同状况下的原子构成时，在这些节点之间不创建边。因此，在冲突图中，求出最大独立集与求出两个分子公共的子结构中的最大子结构同义，其中，最大独立集是由在节点之间没有边的节点构成的集中节点的数量最大的集。例如，两个分子的最大公共子结构可以通过求出冲突图中的最大独立集来指定。

因此，通过将两个分子表示为图形，基于表示为图形的分子的结构创建冲突图，并求出冲突图中的最大独立集，可以求出两个分子的最大公共子结构。

图6示出了在通过求出冲突图中的最大独立集来求出分子A(乙酸)和分子B(乙酸甲酯)的最大公共子结构(求解最大独立集问题)的情况下的示例性流程。如图6所示，冲突图以这样的方式创建，即，分子A和B每个都表示为图形，相同的元素被组合并用作节点，并且根据构成节点的原子的状况形成边。然后，通过求出所创建的冲突图中的最大独立集，可以求出分子A和B的最大公共子结构。

这里，将描述用于求出(搜索)冲突图中的最大独立集的示例性具体方法。

例如，可以通过使用哈密顿函数来执行对冲突图中的最大独立集的搜索，其中，最小化意味着搜索最大独立集。例如，可以通过使用如下公式(1)所示的哈密顿函数(H)来执行搜索。

[数学公式1]

这里，在如上公式(1)中，n代表冲突图中的节点的数量，b

此外，当在第i节点与第j节点之间存在边时，w

此外，x

注意，α和β代表正数。

将更详细地描述由上述公式(1)表示的哈密顿函数与对最大独立集的搜索之间的关系。上述公式(1)是以二次无约束二进制优化(QUBO)格式表示伊辛模型等式的哈密顿函数。

在上述公式(1)中，当x

因此，在上述公式(1)中，通过在状态被指定为1(位被指定为1)的节点之间不存在边的约束下搜索其中尽可能多的节点具有状态1的组合，可以检索到最大独立集。

这里，将描述上述公式(1)中的每项。

上述公式(1)右侧的第一项(具有系数-α的项)是这样的项：该项的值随着x

上述公式(1)右侧的第二项(具有系数β的项)是这样的惩罚项：当在位具有1的节点之间存在边时(当w

如上所述，当许多节点具有位1时，上述公式(1)具有较小值，并且当在位具有1的节点之间存在边时，上述公式(1)具有较大值；因此，可以说，使上述公式(1)最小化意味着搜索最大独立集。

这里，将参照附图使用示例来描述由上述公式(1)表示的哈密顿函数与对最大独立集的搜索之间的关系。

将考虑如图7中所示的示例那样对节点数量为六的图形中的每个节点的位进行设置的情况。在图7的示例中，如图5那样，对于节点之间存在边的情况，节点由实线连接，而对于不存在边的情况，节点由虚线连接。

针对图7中的示例，假设在上面的公式(1)中，b

[数学公式2]

H＝-α(x

＝-α(1+0+1+0+1+0)+β(1*1*0+0*1*1+0*1*0+0*1*1+0*1*0+…)＝-3α

以这样的方式，在图7的示例中，当没有在位具有1的节点之间存在边的情况时(当作为独立集没有矛盾时)，右侧的第二项具有0，并且第一项的值被原样给出为哈密顿函数的值。

接下来，将考虑如图8所示的示例中那样对每个节点的位进行设置的情况。如图7中的示例那样，假设在上面的公式(1)中，b

[数学公式3]

H＝-α(x

＝-4α+5β

以这种方式，在图8的示例中，由于有在位具有1的节点之间存在边的情况，因此右侧的第二项不具有0，并且哈密顿函数的值被给定为右侧的两项之和。在此，在图7和图8所示的示例中，例如，在假设α＞5β的情况下，满足-3α＜-4α+5β，并且因此，图7的示例中的哈密顿函数的值比图8的示例中的哈密顿函数的值小。在图7的示例中，获得了作为最大独立集没有矛盾的节点的集，并且可以看出，通过对上述公式(1)中的哈密顿函数的值变得较小的节点的组合进行搜索，可以检索到最大独立集。

接下来，将描述如非专利文献1中描述的示例性现有技术中的基于检索到的最大独立集来计算分子间的结构相似度的方法。

分子间的结构相似度可以例如使用如下公式(2)来计算。

[数学公式4]

这里，在如上公式(2)中，S(G

此外，V

此外，V

符号δ代表从0到1的数。

另外，在上述公式(2)中，max{A,B}意味着从A和B中选择较大的值，并且min{A,B}意味着从A和B中选择较小的值。

在此，如图1和其他附图那样，以乙酸(分子A)和乙酸甲酯(分子B)为例，描述计算相似度的方法。

在图9所示的冲突图中，最大独立集由四个节点构成：节点[A1B1]、节点[A2B2]、节点[A3B3]和节点[A5B5]。因此，在图9的示例中，|V

[数学公式5]

以这样的方式，在图9的示例中，基于上述公式(2)，将分子间的结构相似度计算为0.9。

如上所述，在如非专利文献1中描述的示例性现有技术中，使用上述公式(1)和(2)计算化合物(分子)之间的结构相似度。

然而，在这样的现有技术中，如图2所示，分子A和B中的相同元素被组合并被用作冲突图的节点。因此，当创建冲突图的节点时，没有考虑除了元素之外的原子的状态，并且在相似度的准确性方面有改进的空间；此外，如果构成化合物的原子的数量增加，则要用于计算的位数增加。

鉴于此，本发明人发现，当计算相似度时，通过根据在第一材料与第二材料之间原子类型相同的两个原子的组合来构造冲突图的节点(其中，原子类型与元素种类相比被更精细地细分)，并且搜索冲突图以寻找最大独立集，可以提高相似度的准确性，并且可以减少节点的数量(这意味着可以减少用于计算的位数)。

当冲突图的节点由在第一材料与第二材料之间原子类型相同的两个原子的组合构造时(原子类型与元素种类相比被更精细地细分)，原子类型包括例如轨道杂化、芳香性(aromaticity)的类型、原子的化学环境的类型等。将描述这种情况的示例。

此外，例如，冲突图的多个节点均由第一材料与第二材料之间的原子类型和键类型相同的两个原子的组合构成。键类型包括，例如，有关组合是否包含在芳香环中，以及有关组合是否具有共价键、离子键或配位键。

图10是示出乙酸和乙酸甲酯如何表示为图形的示例的图。

在图10中，形成乙酸的原子由A1、A2、A3和A5表示，并且形成乙酸甲酯的原子由B1至B5表示。此外，在图10中，A1、A2、B1、B2和B4表示碳，A3、A5、B3和B5表示氧，同时由细实线表示单键，由粗实线表示双键。注意，虽然在图10所示的示例中，除氢以外的原子被选择并被表示为图形，但是当将化合物表示为图形时，包括氢的所有原子可以被选择并被表示为图形。直到此时，该图形与图1中所示的图形相同。然而，在图10中，基于轨道杂化、芳香性和化学环境将碳和氧进一步细分。在图10中，基于通用AMBER力场(GAFF)的原子类型来细分原子类型。GAFF原子类型例如在以下文献的表1等中引入。

文献：WANG,JUNMEI；WOLF,ROMAIN M.；CALDWELL,JAME S W.；KOLLMAN,PETER A.；CASE,DAVID A.,“Development and Tes ting of a General Amber Force Field”,Journal of Computational Chemistry,第25卷，第9期。

在此，在图10中,“c3”表示sp

图10中乙酸的图形和乙酸甲酯的图形具有这些关于原子类型的信息。

接下来，将表示为图形的分子A和分子B的顶点(原子)组合以创建冲突图的顶点(节点)。此时，例如，如图11所示，分子A和B中的相同原子类型被组合并被用作冲突图的节点。在图11中所示的示例中，表示原子类型“c3”的A1、B1和B4的组合、表示原子类型“c2”的A2和B2的组合、以及表示原子类型“o”的A5和B5的组合被用作冲突图的节点。以这样的方式，通过将不是相同元素而是具有相同原子类型的原子的组合用作节点(其中与元素种类相比，原子类型被更精细地细分)，可以抑制节点的数量，并且可以使计算器的要被用于求解最大独立集问题的位数更小。

在图11的示例中，根据表示为图形的分子A和B创建的冲突图的节点的数量如图11所示被给定为四。

另一方面，在图2的示例中，通过组合分子A的碳和分子B的碳而创建了六个节点，通过组合分子A的氧和分子B的氧而创建了四个节点。因此，根据表示为图形的分子A和B创建的冲突图的节点的数量被给定为十。

随后，冲突图被创建并且如图12所示给出。

在本申请公开的技术的示例中，例如，第一材料代表要与第二材料进行比较的材料，其中，要针对第二材料来求出相似度。

第一材料没有特别限制并且可以根据目的而适当地选择，其可以是分子或者可以不是分子。除分子以外的第一材料的示例包括无机晶体等。

此外，第一材料不受特别限制，只要采用可以表示为图形的材料，并且可以根据目的而适当地选择所述材料即可。

在本申请公开的技术的示例中，例如，第二材料是指要针对其求出与第一材料的相似度的目标材料。

第二材料没有特别限制并且可以根据目的而适当地选择，其可以是分子或者可以不是分子。除分子以外的第二材料的示例包括无机晶体等。

此外，第二材料不受特别限制，只要采用可以表示为图形的材料，并且可以根据目的而适当地选择所述材料即可。

在此，在本申请所公开的技术的示例中，优选的是，将第一材料和第二材料的化学结构数据作为包含大量材料的化学结构数据组(数据库)输入。例如，优选的是，作为本申请中所公开的技术的示例的相似度计算装置具有包含大量材料的化学结构数据组。

化学结构数据组的格式(数据结构)没有特别限制，并且可以根据目的而适当地选择；格式的示例包括先前描述的SDF格式等。

在本申请所公开的技术的示例中，例如，可以通过接受第一材料和第二材料的化合物名称或通用名称等，并将第一材料和第二材料与化学结构数据组进行对照，来指明第一材料和第二材料各自的结构。此外，在本申请公开的技术的示例中，例如，可以通过直接输入第一材料和第二材料的化学结构数据来指明第一材料和第二材料的结构。

在本申请公开的技术的示例中，例如，当使用上述公式(1)和(2)求出第一材料与第二材料之间的相似度时，适当地优化上述公式(1)和(2)的参数。

在本申请公开的技术的示例中，例如，如在上述现有技术中，通过基于第一材料和第二材料的分子结构搜索最大独立集，可以使用公式(1)求出相似度。

[数学公式6]

然而，在上述公式(1)中，H代表哈密顿函数，其中，使H最小化意味着搜索最大独立集。

符号n被理解为：表示为图形的第一材料和第二材料的冲突图中的节点的数量。

此外，冲突图被理解为图形，该图形将构成被表示为图形的第一材料的相应节点原子与构成被表示为图形的第二材料的相应节点原子的组合用作为节点，并且该图形是基于这样的规则而创建的：当两个节点被比较并且彼此不相同时，在这两个节点之间创建边，以及当两个节点被比较并且彼此相同时，在这两个节点之间不创建边。

符号b

当在第i节点与第j节点之间存在边时，符号w

符号x

注意，α和β代表正数。

这里，在本申请公开的技术的示例中，“两个节点被比较并且彼此相同”的情况意味着，当两个节点被比较时，这些节点由彼此处于相同的状况(键合状况)的节点原子构成。同样，在本申请公开的技术的示例中，“两个节点被比较并且彼此不相同”的情况意味着，当比较多个节点时，这些节点由彼此处于不同的状况(键合状况)的节点原子构成。

这里，键合状况可以由键序来代表，但是也可以由比键序更详细的键合状况来代表。例如，键合状况可以包括有关组合是否包含在芳香环中以及有关组合是否具有共价键、离子键或配位键。比键序更详细的键合状况的示例包括由奥斯汀模型1(AM1)-键电荷校正(BCC)定义的键类型。

例如，由AM1-键电荷校正(BCC)定义的键类型被引入以下文献中。

文献：JAKALIAN,ARAZ；JACK,DAVID B.；BAYLY,CHRISTOPH ER I.,“Fast,Efficient Generation of High-Quality Atomic Charges.AM1-BC C Model:II.Parameterization and Validation”,Journal of Computational Ch emistry,23:1623-1641,2002。

在本申请所公开的技术的示例中，当使用上面的公式(1)执行对最大独立集的搜索时，创建被表示为图形的第一材料和第二材料的冲突图并非是高度优先的，并且可以至少最小化上面的公式(1)就足够了。例如，在本申请中所公开的技术的示例中，在第一材料和第二材料的冲突图中搜索最大独立集被以哈密顿函数(其中,最小化意味着搜索最大独立集)表示的组合优化问题所代替，并被求解。这里，通过使用退火机等执行退火方法(退火)，可以在短时间内执行如上公式(1)中的由QUBO格式的伊辛模型等式所表示的哈密顿函数的最小化。注意，稍后将描述退火方法的细节。

此外，在本申请中所公开的技术的示例中，例如，如在上述现有技术中，可以使用公式(2)基于检索到的最大独立集来求出相似度。

[数学公式7]

然而，在如上公式(2)中，G

此外，V

V

注意，δ代表从0到1的数。

从读取分子结构到搜索最大独立集的示例性顺序将使用乙酸和乙酸甲酯作为示例来进一步描述。

首先，根据诸如SDF的文件格式，读取图13所示的乙酸(A)和乙酸甲酯(B)的化学结构。

接着，将读取的化学结构用作输入，使用antechamber来定义原子类型和键类型(键合状况)。这里，antechamber是包括在AMBER工具中的模块。

因此，乙酸(A)和乙酸甲酯(B)各自的原子类型和键类型(键合状况)定义如下。注意，下面的编号对应于分配给图13中的分子的原子的编号。

(Ⅰ)原子类型

(A)1：c3

2：c2

3：oh

5：o

(B)1：c3

2：c2

3：os

4：c3

5：o

(II)键类型

(A)1-2:单键

2-3：单键

2-5：双键

(B)1-2:单键

2-3：单键

2-5：双键

3-4：单键

然后，原子类型和键类型分别被用作节点标签和边标签，并且被表示为图形，所述图形如图14所示给出。

接下来，使用所创建的图形，根据图15中所示的流程图寻找成对的相同的原子类型，并且所找到的对被用作冲突图的节点。这里，图15所示的流程图中的附图标记的含义如下。

·ia:分子A(乙酸)的原子索引。

·ja:分子B(乙酸甲酯)的原子索引。

·nA:分子A(乙酸)的所有原子数。

·nB:分子B(乙酸甲酯)的所有原子数。

·at[i]:原子i的原子类型。

作为结果，图16中所示的四对被用作冲突图的节点。然后，向每个节点分配一个位。

接下来，在具有不同键合状况的节点之间创建边。

图17示出了冲突图。注意，在图17的冲突图中，节点之间的实线表示边，节点之间的虚线表示没有创建边。

然后，根据图18所示的流程，将没有边的节点(位)之间的权重指定为0，并且将有边的节点(位)之间的权重指定为1(或者等于或大于1的整数值)。

这里，例如，关于[0]-[1]，w

接着，使用上述公式(1)，执行对处于使哈密顿函数(H)最小化的位状态下的最大独立集的搜索。例如，使用数字退火器(注册商标)来执行对最大独立集的搜索。

作为结果，如图19所示，可以看出，当满足x

在下文中，将使用示例性装置配置、流程图等来更详细地描述本申请中公开的技术的示例。

图20示出了本申请所公开的相似度计算装置的示例性硬件配置。

在相似度计算装置10中，例如，控制单元11、存储器12、存储单元13、显示单元14、输入单元15、输出单元16和输入/输出(I/O)接口单元17经由系统总线18而彼此连接。

控制单元11执行算术运算(例如，四则算术运算、比较运算以及用于退火方法的算术运算)、硬件和软件操作控制等。

控制单元11不受特别限制，并且可以根据目的来适当地选择；例如，控制单元11可以是中央处理单元(CPU)或用于后面描述的退火方法的优化装置，或者可以是这些设备的组合。

本申请所公开的相似度计算装置的创建单元、搜索单元以及计算单元例如能够通过控制单元11来实现。

存储器12是诸如随机存取存储器(RAM)或只读存储器(ROM)的存储器。RAM存储从ROM和存储单元13读取的操作系统(OS)、应用程序等，并且用作控制单元11的主存储器和工作区。

存储单元13是存储各种类型的程序和数据的装置，并且可以是例如硬盘。存储单元13存储要由控制单元11执行的程序、要在执行程序时使用的数据、OS等。

此外，本申请中所公开的程序存储在例如存储单元13中，加载到存储器12的RAM(主存储器)中，并由控制单元11执行。

显示单元14是显示装置，并且例如可以是诸如阴极射线管(CRT)监视器或液晶面板的显示装置。

输入单元15是用于各种数据的输入装置，并且例如可以是键盘或定点装置(诸如鼠标等)。

输出单元16是用于各种数据的输出装置，并且例如可以是打印机等。

I/O接口单元17是用于连接各种外部装置的接口。

I/O接口单元17使得数据能够输入在例如光盘只读存储器(CD-ROM)、数字多功能盘只读存储器(DVD-ROM)、磁光(MO)盘或通用串行总线(USB)存储器(USB闪存驱动器)上，以及将数据从其上输出。

图21示出了本申请中所公开的相似度计算装置的另一示例性硬件配置。

图21所示的示例是采用云型的相似度计算装置并且控制单元11独立于存储单元13等的情况的示例。在图21所示的示例中，包括存储单元13等的计算机30经由网络接口单元19和20连接至包括控制单元11的计算机40。

网络接口单元19和20是使用因特网执行通信的硬件。

图22示出了本申请中公开的相似度计算装置的另一示例性硬件配置。

图22所示的示例是采用云型的相似度计算装置并且存储单元13独立于控制单元11等的情况的示例。在图22所示的示例中，包括控制单元11等的计算机30经由网络接口单元19和20连接至包括存储单元13的计算机40。

图23示出了本申请中所公开的相似度计算装置的另一示例性硬件配置。

图23所示的示例是优化装置21与控制单元11分开地包括的情况的示例。另外，图23所示的示例是采用云型的相似度计算装置的情况的示例。在图23中，优化装置21独立于控制单元11、存储器12、存储单元13等。在图23所示的示例中，包括控制单元11等的计算机30经由网络接口单元19和20连接至包括优化装置21的计算机40。优化装置21是例如在稍后描述的退火方法中使用的优化装置。

在图23所示的示例中，例如，本申请所公开的相似度计算装置的创建单元和计算单元通过控制单元11来实现，且搜索单元通过优化装置21来实现。

图24示出了作为本申请中公开的相似度计算装置的实施方式的示例性功能配置。此外，图25示出了本申请中公开的相似度计算的实施方式的流程图。

如图24所示，相似度计算装置10包括结构获取单元51、化学结构绘图单元52、创建单元53、搜索单元54和计算单元55。

结构获取单元51根据诸如SDF的文件格式来读取材料(第一材料和第二材料)的化学结构数据60作为输入(过程：S1)。

化学结构绘图单元52针对读取到的化学结构数据60将第一材料和第二材料表示为的图形(过程：S2)。在创建的图形中，例如，如图10所示，构成节点的原子被根据原子类型分类。

创建单元53使用创建的图形创建冲突图(过程：S3)。

搜索单元54通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集(过程：S4)。例如，使用作为优化装置的退火机，通过使公式(1)的哈密顿函数最小化来搜索最大独立集。

计算单元55基于最大独立集计算第一材料与第二材料之间的相似度(过程：S5)。例如，根据公式(2)计算相似度。

输出所计算的相似度。

退火机不受特别限制，只要使用采用对由伊辛模型表示的能量函数执行基态搜索的退火方法的计算机即可，并且可以根据目的适当地选择退火机。退火机的示例包括量子退火机、使用半导体技术的半导体退火机、以及使用CPU或图形处理单元(GPU)执行由软件执行的模拟退火的机器。此外，例如，数字退火器(注册商标)可以用作退火机。

下面将描述退火方法和退火机的示例。

退火方法是使用随机数值和量子位的叠加概率性地求出解的方法。下面以使要优化的评价函数的值最小化的问题为例进行描述。评价函数的值被称为能量。此外，当评价函数的值被最大化时，仅需要改变评价函数的符号。

首先，从向每个变量分配一个离散值的初始状态开始处理。相对于当前状态(变量值的组合)，选择接近该当前状态的状态(例如，仅一个变量改变的状态)，并考虑这两个状态之间的状态转变。计算与状态转变有关的能量变化。根据该值，概率性地确定是采用状态转变以改变状态，还是不采用状态转变以保持原始状态。在能量下降时的采用概率被选择为大于能量上升时的采用概率的情况下，可以预期：将在能量平均下降的方向上发生状态改变，并且随着时间的推移，将发生向更合适的状态的状态转变。然后，存在如下可能性：可以最终获得最优解或者给出与最优值接近的能量的近似解。

如果以确定性的方式在能量下降时采用状态转变并且在能量增加时不采用状态转变，则从广义上讲，能量变化相对于时间单调减少，但是当达到局部解时，则不再进一步改变。如上面所描述的，由于在离散优化问题中存在非常大量的局部解，因此状态几乎肯定会陷入不太接近最优值的局部解中。因此，当求解离散优化问题时，概率地确定是否采用状态是重要的。

在退火方法中，已经证明，通过如下确定状态转变的采用(允许)概率，状态在无限时间(迭代计数)的限制内达到最优解。

以下，对使用退火方法求出最优解的方法进行逐步说明。

(1)对于由于状态转变引起的能量变化(能量减少)值(-ΔE)，状态转变的允许概率p由以下函数f()中的任何一个确定。

[数学公式8]

p(ΔE，T)＝f(-ΔE/T) (公式1-1)

[数学公式9]

f

[数学公式10]

这里，T代表称为温度值的参数，并且例如可以如下进行改变。

(2)如由下面的公式所表示的，温度值T相对于迭代计数t对数地减小。

[数学公式11]

此处，T

在使用由(1)中描述的公式表示的允许概率的情况下，如果在足够的迭代之后达到稳态，则对于热力学中的热平衡状态，每种状态的占有概率都遵循玻尔兹曼分布。

然后，当温度从高温逐渐降低时，低能量状态的占有概率增加。因此，认为当温度充分降低时获得低能量状态。由于该状态与当材料退火时引起的状态变化非常相似，因此该方法被称为退火方法(或伪退火方法)。注意，使能量增加的状态转变的概率性发生与物理学中的热激发相对应。

图26示出了执行退火方法的优化装置的示例性功能配置。然而，在以下描述中，还描述了生成多个状态转变候选的情况，但是基本退火方法一次生成一个转变候选。

优化装置100包括保持当前状态S(多个状态变量值)的状态保持单元111。此外，优化装置100包括能量计算单元112，该能量计算单元112计算在由于多个状态变量值中的任何一个状态变量值的变化而发生相对于当前状态S的状态转变时的每个状态转变的能量变化值{-ΔEi}。另外，优化装置100包括控制温度值T的温度控制单元113以及控制状态变化的转变控制单元114。

转变控制单元114基于温度值T、能量变化值{-ΔEi}以及随机数值，根据能量变化值{-ΔEi}与热激发能量之间的相对关系来概率性地确定是否接受多个状态转变中的任何状态转变。

在此，转变控制单元114包括：候选生成单元114a，其生成状态转变候选；以及适当性确定单元114b，用于基于能量变化值{-ΔEi}和温度值T概率性地确定是否允许针对每个候选的状态转变。此外，转变控制单元114包括：转变确定单元114c，其从被允许的候选中确定要采用的候选；以及随机数生成单元114d，其生成随机变量。

优化装置100在一次迭代中的操作如下。

首先，候选生成单元114a生成从保持在状态保持单元111中的当前状态S到下一状态的一个或更多个状态转变候选(候选编号{Ni})。接着，能量计算单元112使用当前状态S和状态转变候选来计算被列为候选的每个状态转变的能量变化值{-ΔEi}。适当性确定单元114b使用由温度控制单元113生成的温度值T和由随机数生成单元114d生成的随机变量(随机数值)，根据每个状态转变的能量变化值{-ΔEi}，以上面(1)中所描述的公式的允许概率来允许状态转变。

然后，适当性确定单元114b输出每个状态转变的适当性{fi}。在存在多个被允许的状态转变的情况下，转变确定单元114c使用随机数值随机地选择被允许的状态转变之一。然后，转变确定单元114c输出所选择的状态转变的转变编号N和转变适当性f。在存在被允许的状态转变的情况下，根据所采用的状态转变来更新被存储在状态保持单元111中的状态变量值。

从初始状态开始，在温度控制单元113降低温度值的同时重复以上描述的迭代。当满足完成确定条件(例如达到一定迭代计数或能量下降到低于特定值)时，操作完成。优化装置100输出的答案是操作完成时的状态。

图27是用于一次生成一个候选的普通退火方法中的转变控制单元(特别是用于适当性确定单元的算术单元)的示例性配置的电路级框图。

转变控制单元114包括随机数生成电路114b1、选择器114b2、噪声表114b3、乘法器114b4和比较器114b5。

选择器114b2选择并输出针对各个状态转变候选计算的能量变化值{-ΔEi}中与作为由随机数生成电路114b1生成的随机数值的转变编号N相对应的值。

稍后将描述噪声表114b3的功能。例如，诸如RAM或闪存的存储器可以用作噪声表114b3。

乘法器114b4输出通过将由噪声表114b3输出的值与(对应于以上描述的热激发能量的)温度值T相乘而获得的乘积。

比较器114b5输出通过将由乘法器114b4输出的乘法结果与由选择器114b2选择的能量变化值-ΔE进行比较而获得的比较结果，作为转变适当性f。

图27中示出的转变控制单元114基本上按原样实现上述功能。然而，将更详细地描述以由(1)中的公式表示的允许概率允许状态转变的机制。

可以通过将均匀随机数输入以下比较器来实现以允许概率p输出1并且以允许概率(1-p)输出0的电路，其中，均匀随机数针对输入A取允许概率p并且针对输入B取区间[0,1)中的值，该比较器具有两个输入A和B，当满足A>B时输出1并且当满足A

这意味着，利用当f(ΔE/T)大于u时输出1的电路，可以实现上述功能，其中，f是在(1)中的公式中使用的函数，并且u是取区间[0,1)中的值的均匀随机数。

此外，通过进行以下修改，也可以实现与上述功能相同的功能。

将相同的单调递增函数应用于两个数不会改变大小关系。因此，即使将相同的单调递增函数应用于比较器的两个输入，也不会改变输出。如果采用f的反函数f

图27中的噪声表114b3是用于实现该反函数f

[数学公式12]

[数学公式13]

转变控制单元114还包括保持确定结果等的锁存器，生成其定时的状态机等，但是为了简化说明这些未在图27中示出。

图28是示出了转变控制单元114的示例性操作流程的图；图28所示的操作流程包括：选择一个状态转变作为候选的步骤(S0001)，通过将针对状态转变的能量变化值与温度值和随机数值的乘积进行比较来确定状态转变的适当性的步骤(S0002)，以及如果允许状态转变则采用状态转变并且如果不允许状态转变则不采用状态转变的步骤(S0003)。

本申请中公开的程序可以被配置为例如使计算机执行本申请中公开的相似度计算方法的程序。此外，例如，可以使本申请中公开的程序的适当模式与本申请中公开的相似度计算方法的适当模式相同。

本申请中公开的程序可以根据要使用的计算机系统的配置、操作系统的类型和版本等使用各种已知的编程语言来创建。

本申请中公开的程序可以记录在诸如内部硬盘或外部硬盘的记录介质中，或者可以记录在诸如CD-ROM、DVD-ROM、MO盘或USB存储器的记录介质中。

此外，在本申请中公开的程序被记录在如上所述的记录介质中的情况下，取决于状况，该程序可以被直接使用，或者可以被安装到硬盘中，然后通过包括在计算机系统中的记录介质读取器来使用。此外，本申请中公开的程序可以被记录在可通过信息通信网络从计算机系统访问的外部存储区域(另一计算机等)中。在这种情况下，取决于状况，可以直接使用记录在外部存储区域中的本申请中所公开的程序，或者可以将其安装在硬盘中，然后通过信息通信网络从外部存储区域使用该程序。

注意，本申请中公开的程序可以针对任何处理的每一个而被划分，并且被记录在多个记录介质中。

(记录介质)

本申请中公开的记录介质是通过记录本申请中公开的程序而获得的。

本申请中公开的记录介质是计算机可读的。

本申请中公开的记录介质不受特别限制，并且可以根据目的适当地选择。记录介质的示例包括内部硬盘、外部硬盘、CD-ROM、DVD-ROM、MO盘和USB存储器。

此外，本申请中所公开的记录介质可以包括多个记录介质，其中，在针对任何处理的每一个划分本申请中公开的程序之后，在多个记录介质中记录本申请中公开的程序。

本申请中所公开的记录介质可以是暂态的或非暂态的。

<计算示例>

作为本申请中所公开的相似度计算装置的一个计算示例，计算芳樟醇与香料(fragrance)分子之间的相似度。

芳樟醇具有图29中所示的化学结构，并具有柑橘香味。

在食品卫生执法条例(Food Sanitation Law Enforcement Regulation)的表1中列出的分子中，其香味登记在佳香公司(Good Scents Company)信息系统(http://www.thegoodscentscompany.com/index.html)中的132个分子被用作香料分子。

<<常规示例>>

按照图25所示的流程计算相似度。

根据SDF文件格式读取香料分子的化学结构数据作为输入(过程：S1)。

将读取到的化学结构数据表示为图形(过程：S2)。在所创建的图形中，根据元素种类对构成节点的原子进行分类。

使用所创建的图形创建冲突图(过程：S3)。这里，当创建冲突图时，冲突图的节点是根据两个分子之间的元素种类相同的两个原子的组合创建的。

通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集(过程：S4)。在此，使用作为优化装置的退火机，通过使公式(1)的哈密顿函数最小化来搜索最大独立集。

基于最大独立集计算相似度(过程：S6)。这里，根据公式(2)计算相似度。

在常规示例中，在创建芳樟醇和松油醇的冲突图时，创建了101个节点。这意味着，如图30所示，采用101位来搜索最大独立集。

此外，表1示出了根据常规示例计算132个分子中的一部分与芳樟醇的相似度的结果。

[表1]

<<示例>>

按照图25所示的流程计算相似度。

根据SDF文件格式读取香料分子的化学结构数据作为输入(过程：S1)。

将读取的化学结构数据表示为图形(过程：S2)。在所创建的图形中，根据通用AMBER力场(GAFF)的原子类型对构成节点的原子进行分类。

使用所创建的图形创建冲突图(过程：S3)。这里，当创建冲突图时，根据在两个分子之间具有相同GAFF原子类型的两个原子的组合来创建冲突图的节点。

通过使用退火方法执行基态搜索来搜索冲突图中的最大独立集(过程：S4)。在此，使用作为优化装置的退火机，通过使公式(1)的哈密顿函数最小化来搜索最大独立集。

基于最大独立集计算相似度(过程：S6)。这里，根据公式(2)计算相似度。

在该示例中，当创建芳樟醇和松油醇的冲突图时，创建57个节点。这意味着，如图31所示，采用57位来搜索最大独立集。

此外，表2示出了根据示例计算132个分子中的一部分与芳樟醇的相似度的结果。

[表2]

比较表1和表2，在该示例中，不是基于柑橘的薄荷醇的相似度指示比在常规示例中计算的相似度的值更低的值。这意味着，该示例具有比常规示例的准确性更高的相似度准确性。认为该差异的原因是，在示例方法中，以下两个结构中的子结构(H

[化学式1]