ECFP及FCFP的计算过程

查阅起点来自《A Deep Learning Approach to Antibiotic Discovery》

---

摩根指纹一般指 Extended-connectivity fingerprints (ECFPs) ，可以调用 rdkit 得到，这篇文章描述实现的具体细节，主要参考 Extended-Connectivity Fingerprints。输入算法参数的是一个哈希函数（将列表映射为一个32bit的整数），待编码的分子 smiles，半径 r，最终编码长度 n_bits，下面是算法的大致描述，每个阶段的描述之后是python的实现，代码效率可能比较低（特别是对化学键的处理，暂时想不到好的办法，以后有机会改进），主要是辅助理解。原文细节描述很多，如果不懂下面的描述强烈推荐去读原文。

下面代码注释中提到的图都是来自原文中提到的示例分子，也即下面图片中的分子

from rdkit import Chem
from rdkit.Chem import AllChem
from collections import defaultdict
from rdkit.Chem.Draw import IPythonConsole
IPythonConsole.ipython_useSVG=True

smiles="CCCC(=O)N"
mol=Chem.MolFromSmiles(smiles)
mol
1
2
3
4
5
6
7
8
9

1.初始化

• 对每个原子初始化一个32bit的整数标识符，对于ECFP来说，使用的方法是 Daylight atomic invariants rule
  • Daylight atomic invariants rule 将每个原子映射为一个32bit的整数标识符，具体是先得到每个原子的描述列表，包括重原子邻居个数，化学价与邻接氢原子的差值，化学价，原子序数，原子质量，原子电荷数，邻接氢原子数，作者在这里另外加了一个元素是原子是否在环上。用算法参数中的哈希函数将这个描述列表变成一个32bit的整数，最后返回这个整数作为标识符

def myHash(array):
    #将数组hash为一个32bit的整数,首位是符号位
    key=2**32
    tmp=hash(tuple(array))%key
    #tmp在[0-2^32),下面将它移动到[-2^31,2^31),即32bit的int范围
    return tmp-2**31

def getECFPInit(mol,Hash=myHash):
    mol = Chem.AddHs(mol)     #显示添加氢原子
    atom2vec=defaultdict(list)
    atoms = mol.GetAtoms()
    for i in range(len(atoms)):
        atom2vec[atoms[i]].append(sum(atom.GetAtomicNum()==1 for atom in atoms[i].GetNeighbors()))  #统计连接氢原子信息
    atom2vec={key:value for key,value in atom2vec.items() if key.GetAtomicNum()!=1}                  #删除氢原子信息
    for atom in atom2vec.keys():
        atom2vec[atom].append(atom.GetDegree()-atom2vec[atom][0])           #所有连接原子减去氢原子,即重原子邻居个数
        atom2vec[atom].append(atom.GetTotalValence()-atom2vec[atom][0])     #原子化合价减去氢原子个数,这里的化合价暂时用 GetTotalValence,不确定是否正确
        atom2vec[atom].append(atom.GetAtomicNum())                          #原子序数
        atom2vec[atom].append(atom.GetMass())                               #原子质量
        atom2vec[atom].append(atom.GetFormalCharge())                       #原子电荷
        atom2vec[atom].append(atom2vec[atom][0])                            #连接的氢原子数目
        atom2vec[atom].append(int(atom.IsInRing()))                         #原子是否位于环上
    #atom2vec={key:value[1:] for key,value in atom2vec.items()}       #删除第一位的邻接氢原子个数信息
    atomIdx2int={key.GetIdx():Hash(value[1:]) for key,value in atom2vec.items()}     #每个原子的7位信息hash成一个32int
    return atomIdx2int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.迭代

• 对每个原子初始化一个化学键的集合，这个集合用于每次迭代后的去重，如果两个化学键集合完全一致，就删除本轮得到的其中一个标识符
• 每个分子对应一个指纹列表，它收集每轮迭代后所有分子的标识符，初始即为第一步初始化得到的所有标识符去重后的结构
• 对每个原子而言不断增大半径变成更大的结构片段，收集局部结构信息，如下图。收集局部信息的具体方式是：对当前的结构扩大一步键的范围，得到（键标识，新连接的原子标识符），其中键标识是单键，双键，三键，芳香键分别为1，2，3，4。将得到的元组列表利用哈希函数映射成32bit的整数，之后去重
  

import copy

def GetMorganFingerprint(mol,r=2,Hash=myHash,useFeatures=False):

    #下面是初始化

    bondType2int={                  #键的类型映射为数字
        rdkit.Chem.rdchem.BondType.SINGLE:1,
        rdkit.Chem.rdchem.BondType.DOUBLE:2,
        rdkit.Chem.rdchem.BondType.TRIPLE:3,
        rdkit.Chem.rdchem.BondType.AROMATIC:4,
    }
    if useFeatures:
        atomIdx2int=getFCFPInit(mol) #这里不实现
    else:
        atomIdx2int=getECFPInit(mol)
    atomIdx2substruAndBonds=defaultdict(list)  #以每个原子为中心形成的子结构片段所含的原子及键,dic[atom][0]是子结构包含的原子,dic[atom][1]是子结构包含的键
    bondNum=mol.GetNumBonds()
    for atomIdx in atomIdx2int.keys():
        atomIdx2substruAndBonds[atomIdx].append([]) #第一个空列表放子结构中的原子
        atomIdx2substruAndBonds[atomIdx][0].append(atomIdx)
        atomIdx2substruAndBonds[atomIdx].append([])    #第二个空列表放子结构中的键
        #遍历化学键,找到与子结构中原子相连的键,比较笨拙,暂时想不出什么好的办法△
        for i in range(bondNum):
            bond=mol.GetBondWithIdx(i)
            if (bond.GetBeginAtomIdx()==atomIdx or bond.GetEndAtomIdx()==atomIdx):
                #键的起点或终点之一是目前的这个原子,因此该键包含在此子结构中
                atomIdx2substruAndBonds[atomIdx][1].append(bond.GetIdx())
    """
    for key,value in atomIdx2substruAndBonds.items():
        print(key,value)       #可以print出来看一下,key是原子索引,value[0]是子结构包含的原子的索引,value[1]是子结构包含的键索引
    """
    fpList=[]                    #每轮迭代后都把信息去重后收集到这个列表中,最终返回

    #去重依靠的是每个子结构中的键的类型和原子类型是否完全一致,如果一致就去重一个,比如这个分子中C2和C3都是连接了两个单键,它们的信息只被收录入fpList一次
    #重复的两个标识符中迭代次数大的那个或哈希之后数字小的那个被删除,另一个保留

    diffSubstru=defaultdict(list) #索引是相同子结构,值是索引是生长出的子结构是索引那种子结构的初始中心原子

    #将其都转化为元组,使之能hash,将子结构中的原子转化为原子序数,表明是一种原子,键也映射为标识符
    tmp={atomIdx:tuple([tuple([mol.GetAtomWithIdx(thisAtomidx).GetAtomicNum() for thisAtomidx in substruAndBonds[0]]),
                     tuple([bondType2int[mol.GetBondWithIdx(thisbondidx).GetBondType()] for thisbondidx in substruAndBonds[1]]
                           )]) for atomIdx,substruAndBonds in atomIdx2substruAndBonds.items()}
    for atomIdx,subStructure in tmp.items():
        diffSubstru[subStructure].append(atomIdx)

    """
    for key,value in diffSubstru.items():
        print(key,value)    #可以print出来看一下,key是子结构(前一个元素是原子序数,后一个元素是键的映射),value这个子结构的原子中心,结合下面的分子图理解
    #可以看到有 ((6,), (1, 1)) [1,2]
    #解释是结构为【((6,), (1, 1))】的有两个原子,这个结构的解释是6号原子即C,和两个单键(单键映射是1),即下面的图中C2(序号是1)和C3(序号是2)两个原子都是连接了两个单键,它们是同样的结构
    """

    for subStructure,atomIdxList in diffSubstru.items():
        if len(atomIdxList)>1:
            #结构subStructure重复出现了,只收录标识符值更小的那个
            #下面找到标识符最大的那个
            minIdenti=atomIdx2int[atomIdxList[0]]
            for atomIdx in atomIdxList:
                if atomIdx2int[atomIdx]<minIdenti: minIdenti=atomIdx2int[atomIdx]
            fpList.append(minIdenti)
        else: fpList.append(atomIdx2int[atomIdxList[0]])      #结构特殊,记录此时的标识符atomList[0]

    #print(fpList) #6个原子但只收集到了5个标识符,因为有两个子结构重复了,与原文中描述的一致(到这里不理解强烈推荐回去看原文)


    #上面初始化结束,下面就是不断迭代扩展子结构,然后去重,然后收录入fpList,最后返回fpList

    diffStructureList=[] #保存迭代过程中产生的不同结构,用于去重

    for substructure in atomIdx2substruAndBonds.values(): diffStructureList.append(copy.deepcopy(substructure))

    #print(diffStructureList)

    for iteration in range(1,r+1):
        #print(len(fpList))
        #遍历所有子结构,增长一步键范围
        for atomIdx,subStructure in atomIdx2substruAndBonds.items():
            #遍历子结构中的键,把相连的原子全部放入当前子结构中(也就是原文中的"A"原子),子结构扩展了一步键
            bondsIdx=subStructure[1]
            AatomList=[]        #先记录之前的原子收集这一轮迭代扩展的"A"原子,在原文中提到,去原文看 Figure 7 即可,这轮迭代将上轮中的"A"变成真正的原子
            for atomIdx in subStructure[0]:AatomList.append(atomIdx)
            for bondIdx in bondsIdx:
                bond=mol.GetBondWithIdx(bondIdx)
                #----------------------------
                #键连接的原子全部插入后去重
                subStructure[0].append(bond.GetBeginAtom().GetIdx())
                subStructure[0].append(bond.GetEndAtom().GetIdx())
            subStructure[0]=list(set(subStructure[0]))
            AatomList=set(subStructure[0])-set(AatomList)      #得到这轮新增的'A'原子
            """
            print(AatomList) #每个中心原子向键的方向延伸,新增了'A'原子,与原文一致
            {1}
            {0, 2}
            {1, 3}
            {2, 4, 5}
            {3}         #N和O都是新增了原文中的4号碳原子,也就是这里的3号原子
            {3}

            #到这里已经将原文中的"A"原子扩展到了前一步子结构内部,下一步是扩展A原子连接的键
            #下面的print对应原文 Figure 7 中初始化之后的几轮,第一轮(New features after first iteration)可以对比一下,与原文一致
            #到这里可以看到子结构中的原子数量达到了2,3,3,4,2,2,不算A为原子的话(雀实不应该算)原文与这里得到的结果一样
            #还没有扩展延伸键,因此键的数量还是1,2,2,3,1,1。其中的两个2是有子结构,原文图中只画了去重后的一个2
            print(subStructure)
            [[0, 1], [0]] 
            [[0, 1, 2], [0, 1]]
            [[1, 2, 3], [1, 2]]
            [[2, 3, 4, 5], [2, 3, 4]]
            [[3, 4], [3]]
            [[3, 5], [4]]
            """
            #记录旧键集合
            oldBondList=[]
            for bondIdx in subStructure[1]: oldBondList.append(bondIdx)
            #下面开始延伸键,要延伸的键必须与这轮新增的'A'原子相连,新增后去重即可,与上面延伸原子的方法一样
            for i in range(bondNum):
                bond=mol.GetBondWithIdx(i)
                beginAtomIdx=bond.GetBeginAtom().GetIdx()
                endAtomIdx=bond.GetEndAtom().GetIdx()
                if beginAtomIdx in AatomList or endAtomIdx in AatomList:
                    #此键与A原子相连,加入子结构
                    subStructure[1].append(bond.GetIdx())
                subStructure[1]=list(set(subStructure[1])) #去重
            """
            #此时原子和键的延伸都已经完成,与原文中结果一致,可以对比原子和键的数量
            print(subStructure[0])
            print(subStructure[1])
            print('---------------下一个子结构-----------------')
            print('-----------------------下一轮扩展子结构--------------------------------')
            [0, 1] 
            [0, 1]
            ---------------下一个子结构-----------------
            [0, 1, 2]
            [0, 1, 2]
            ---------------下一个子结构-----------------
            [1, 2, 3]
            [0, 1, 2, 3, 4]
            ---------------下一个子结构-----------------
            [2, 3, 4, 5]
            [1, 2, 3, 4]
            ---------------下一个子结构-----------------
            [3, 4]
            [2, 3, 4]
            ---------------下一个子结构-----------------
            [3, 5]
            [2, 3, 4]
            ---------------下一个子结构-----------------
            -----------------------下一轮扩展子结构--------------------------------
            [0, 1, 2]
            [0, 1, 2]
            ---------------下一个子结构-----------------
            """

            newBondIdxList=list(set(subStructure[1])-set(oldBondList))

            #产生新的标识符,先产生二元组列表:[(与'A'原子相连的键的映射,原子标识符)]
            dataList=[]
            for atomIdx in AatomList:
                second=atomIdx2int[atomIdx]
                #下面找与'A'相连的并且不是新增的键,它肯定只有一个
                targetBond=None
                for bondIdx in subStructure[1]:
                    bond=mol.GetBondWithIdx(bondIdx)
                    if ((bond.GetBeginAtom().GetIdx()==atomIdx and bond.GetIdx() not in newBondIdxList) or (bond.GetEndAtom().GetIdx()==atomIdx and bond.GetIdx() not in newBondIdxList)):
                        targetBond=bond
                        break
                first=bondType2int[targetBond.GetBondType()]
                dataList.append((first,second))
            
            #print(dataList) 第四个原子 [(1, 648728907), (2, -1524169253), (1, -2022827512)] 就是原文中提到的 atom 4 得到的数据
            newIdenti=Hash(dataList)
            #替换原标识符并加入新fpList中
            atomIdx2int[atomIdx]=newIdenti

            #print("diffStructureList\n",diffStructureList)
            #print("subStructure\n",subStructure)
            if subStructure not in diffStructureList:  #看看新结构是否与之前的结构重复,删除的是迭代次数更大的那个标识符,因此
                fpList.append(newIdenti)
                diffStructureList.append(copy.deepcopy(subStructure))

    #最后对哈希得到的所有标识符进行一次去重
    fpList=list(set(fpList))
    return fpList

#fpList=GetMorganFingerprint(mol,3)
#print(len(fpList))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

3.函数接口

def GetMorganFingerprintAsBitVect(mol,nBits,r=2,Hash=myHash):
    fpList=GetMorganFingerprint(mol,r)
    res=set()
    for identi in fpList:
        bit = identi % nBits
        res.add(bit)
    return res
1
2
3
4
5
6
7

下面是与rdkit的对比

mol=Chem.MolFromSmiles("CCCC(=O)N")
nbits=2048
for r in range(5):
    print("rdkit's:",len(AllChem.GetMorganFingerprint(mol,r).GetNonzeroElements().keys()),len(AllChem.GetMorganFingerprintAsBitVect(mol, r, nBits=nbits).GetOnBits()))
    print("my:",len(GetMorganFingerprint(mol,r)),len(GetMorganFingerprintAsBitVect(mol,nbits,r)))
"""
rdkit's: 5 5
my: 5 5
rdkit's: 11 11
my: 11 11
rdkit's: 14 14
my: 14 14
rdkit's: 14 14
my: 14 14
rdkit's: 14 14
my: 14 14
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对示例分子而言，原文，rdkit和这里的实现得到的结果一致

mol=Chem.MolFromSmiles('CC(C)Oc1ccc(-c2nc(-c3cccc4c3CC[C@H]4NCCC(=O)O)no2)cc1C#N')
nbits=2048
for r in range(10):
    print("rdkit's:",len(AllChem.GetMorganFingerprint(mol,r).GetNonzeroElements().keys()),len(AllChem.GetMorganFingerprintAsBitVect(mol, r, nBits=nbits).GetOnBits()))
    print("my:",len(GetMorganFingerprint(mol,r)),len(GetMorganFingerprintAsBitVect(mol,nbits,r)))
"""
rdkit's: 16 15
my: 14 14
rdkit's: 44 43
my: 46 46
rdkit's: 71 68
my: 73 73
rdkit's: 95 91
my: 97 96
rdkit's: 114 110
my: 115 114
rdkit's: 129 125
my: 130 129
rdkit's: 141 137
my: 142 140
rdkit's: 150 146
my: 151 149
rdkit's: 156 152
my: 157 155
rdkit's: 159 155
my: 160 157
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

其他分子得到的结果可能略有不同，可能是某些细节实现方法有误或与rdkit源码实现有差别。
FCFP与ECFP的区别仅仅在于得到 atomIdx2int 的区别，即初始化原子信息，FCFP的初始化是：

• 该原子是否是氢键供体
• 该原子是否是氢键受体
• 该原子是否负离子化
• 该原子是否正离子化
• 该原子是否是芳香性原子
• 该原子是否是卤素原子

得到 6 个元素为 0 或 1 的列表后，通过哈希函数将原子映射为标识符就可以进行迭代，剩下的处理与ECFP完全一致

实现略复杂，遇到了很多坑，可能还有些细节问题，看不懂的话强烈推荐看原文 Extended-Connectivity Fingerprints