仓库源文，站点原文

layout: post title: 分子中原子编号的匹配 categories:

以前的时候我曾简单介绍过有关分子匹配的问题分子匹配叠合及两种冰的结构异同, 也曾示例过如何借助GaussView来实现分子片段分析. 但所用的方法总觉得不很方便, 所以就想着自己能不能实现一个类似功能的简单脚本或在线工具. 但正如以前所说, 就一般情况而言, 这并不是一件简单的问题. 不过针对我们需要的功能, 还是有一些算法可以实现的, 主要是图匹配算法.

图匹配算法

如果你也需要了解这方面的知识, 请先阅读下面的相关资料.

总结一下, 目前常用的图匹配算法包括, Ullman, VF2, NAUTY, 效率依次递增, 但算法复杂度也依次递增.

可以参考的实现代码如下:

在匹配时, 还可以先使用化学信息学中常用的Morgan算法做粗略筛选, 但它不能保证匹配结果一定正确.

程序实现

当两个相同的分子具有不同的构型和原子编号顺序时, 如果我们要对它们的原子编号进行匹配, 在实现的时候不仅要考虑图匹配的作法, 还要考虑每个原子的元素种类和化学环境, 因此, 相比上面所讨论的图匹配, 我们还要适当考虑问题的特殊性. 通过提前对原子使用元素与成键原子类型进行匹配筛选, 可以大大减少后面图匹配的可能性, 提高匹配速度.

为了方便做成在线工具, 我选择了使用已有js代码的Ullman算法. 但事实证明, 这个算法耗时随原子数指数增大. 当分子中的原子数超过20之后, 算法运行时间过长, 基本没有意义, 因此这个算法的实用性不好. 为此, 我在程序中增加了手动添加"锚点"原子的功能, 也就是手动指定两个分子中必须匹配的原子编号. 利用锚点原子, 可以大大加快匹配速度. 很显然, 锚点原子越多, 匹配越迅速. 当锚点原子数与待匹配原子数相同时, 就相当于手动指定每个匹配原子了. 根据我的测试, 在不使用锚点原子的情况下, 30个原子的匹配已经是算法极限了, 但使用锚点原子后, 处理50个原子的匹配不成问题. 至于更多原子的情况, 还有待测试.

使用简介

我将这个工具命名为matchmol. 它是一个在线工具, 在浏览器中运行. 目前仅支持读入GaussView格式的PDB文件, 其中必须包含元素符号列和成键列表, 因为需要使用这些信息进行匹配.

加载两个PDB文件, 其分子相同, 但具有不同的原子编号顺序. 左方为参考分子, 右方为待匹配分子, 中间的文本框中列出每个分子的原子编号, 参考分子的编号顺序不可更改, 待匹配分子的编号可以更改.

可使用三种方法将待匹配分子的原子编号顺序调整至与参考分子一致:

  1. (全)自动模式: 点击Auto Match进行自动匹配. 如果找到匹配结果, 则会在右方文本框中列出待匹配分子中与参考分子对应的编号顺序. 点击Application, 则会根据列出的编号顺序调整待匹配分子的原子编号, 方便对比. 如果点击Save PDB File则会将调整顺序后的待匹配分子的PDB文件保存为conf.pdb. 注意: 全自动模式能处理的分子其原子数在20以下, 否则运行时间过长, 容易失败.

  2. 锚点模式(半自动模式): 如果待匹配原子数过多, 自动模式无法在短时间内完成匹配, 可手动指定锚点原子, 加速匹配. 指定方法是在待匹配分子原子编号文本框中使用带有*的编号. 举例来说, 如果参考分子中的3号原子对应于待匹配分子的7号原子, 那么将待匹配分子原子编号文本框中的3改为7*, 即表示3号原子锚定为7号原子. 接下来的操作与自动模式相同.

  3. 手动模式: 如果你手动指定每个原子的锚点原子, 那就无须在编号后面加*了. 注意, 这种情况下必须指定所有原子的锚点原子.

应用示例

简单分子

以下为同一分子不同原子编号顺序下的PDB文件, 用于说明支持的PDB文件的格式.

<table class="highlighttable"><th colspan="2" style="text-align:left">mol1.pdb</th><tr><td><div class="linenodiv" style="background-color: #f0f0f0; padding-right: 10px"><pre style="line-height: 125%"> 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</pre></div></td><td class="code"><div class="highlight"><pre style="line-height:125%"><span></span>TITLE Molecule Name REMARK <span style="color: #666666">1</span> File created by GaussView <span style="color: #666666">5.0</span>.<span style="color: #666666">9</span> HETATM <span style="color: #666666">1</span> C <span style="color: #666666">0</span> <span style="color: #666666">-2.958</span> <span style="color: #666666">-0.067</span> <span style="color: #666666">-2.907</span> C HETATM <span style="color: #666666">2</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.409</span> <span style="color: #666666">-0.788</span> <span style="color: #666666">-2.338</span> H HETATM <span style="color: #666666">3</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.408</span> <span style="color: #666666">-0.697</span> <span style="color: #666666">-4.233</span> C HETATM <span style="color: #666666">4</span> O <span style="color: #666666">0</span> <span style="color: #666666">-3.739</span> <span style="color: #666666">-1.861</span> <span style="color: #666666">-4.248</span> O HETATM <span style="color: #666666">5</span> N <span style="color: #666666">0</span> <span style="color: #666666">-3.427</span> <span style="color: #666666">0.073</span> <span style="color: #666666">-5.380</span> N HETATM <span style="color: #666666">6</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.804</span> <span style="color: #666666">-0.532</span> <span style="color: #666666">-6.661</span> C HETATM <span style="color: #666666">7</span> H <span style="color: #666666">0</span> <span style="color: #666666">-4.713</span> <span style="color: #666666">-1.084</span> <span style="color: #666666">-6.541</span> H HETATM <span style="color: #666666">8</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.948</span> <span style="color: #666666">0.238</span> <span style="color: #666666">-7.390</span> H HETATM <span style="color: #666666">9</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.090</span> <span style="color: #666666">1.494</span> <span style="color: #666666">-5.474</span> C HETATM <span style="color: #666666">10</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.824</span> <span style="color: #666666">1.996</span> <span style="color: #666666">-6.069</span> H HETATM <span style="color: #666666">11</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.073</span> <span style="color: #666666">1.922</span> <span style="color: #666666">-4.493</span> H HETATM <span style="color: #666666">12</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.027</span> <span style="color: #666666">-1.191</span> <span style="color: #666666">-6.987</span> H HETATM <span style="color: #666666">13</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.127</span> <span style="color: #666666">1.603</span> <span style="color: #666666">-5.928</span> H HETATM <span style="color: #666666">14</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.334</span> <span style="color: #666666">0.779</span> <span style="color: #666666">-3.108</span> H HETATM <span style="color: #666666">15</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.817</span> <span style="color: #666666">0.247</span> <span style="color: #666666">-2.352</span> H <span style="color: #AA22FF">END</span> CONECT <span style="color: #666666">1</span> <span style="color: #666666">3</span> <span style="color: #666666">2</span> <span style="color: #666666">14</span> <span style="color: #666666">15</span> CONECT <span style="color: #666666">2</span> <span style="color: #666666">1</span> CONECT <span style="color: #666666">3</span> <span style="color: #666666">1</span> <span style="color: #666666">4</span> <span style="color: #666666">5</span> CONECT <span style="color: #666666">4</span> <span style="color: #666666">3</span> CONECT <span style="color: #666666">5</span> <span style="color: #666666">3</span> <span style="color: #666666">6</span> <span style="color: #666666">9</span> CONECT <span style="color: #666666">6</span> <span style="color: #666666">5</span> <span style="color: #666666">7</span> <span style="color: #666666">8</span> <span style="color: #666666">12</span> CONECT <span style="color: #666666">7</span> <span style="color: #666666">6</span> CONECT <span style="color: #666666">8</span> <span style="color: #666666">6</span> CONECT <span style="color: #666666">9</span> <span style="color: #666666">5</span> <span style="color: #666666">10</span> <span style="color: #666666">11</span> <span style="color: #666666">13</span> CONECT <span style="color: #666666">10</span> <span style="color: #666666">9</span> CONECT <span style="color: #666666">11</span> <span style="color: #666666">9</span> CONECT <span style="color: #666666">12</span> <span style="color: #666666">6</span> CONECT <span style="color: #666666">13</span> <span style="color: #666666">9</span> CONECT <span style="color: #666666">14</span> <span style="color: #666666">1</span> CONECT <span style="color: #666666">15</span> <span style="color: #666666">1</span> </pre></div> </td></tr></table><table class="highlighttable"><th colspan="2" style="text-align:left">mol2.pdb</th><tr><td><div class="linenodiv" style="background-color: #f0f0f0; padding-right: 10px"><pre style="line-height: 125%"> 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</pre></div></td><td class="code"><div class="highlight"><pre style="line-height:125%"><span></span>TITLE Molecule Name REMARK <span style="color: #666666">1</span> File created by GaussView <span style="color: #666666">5.0</span>.<span style="color: #666666">9</span> HETATM <span style="color: #666666">1</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.409</span> <span style="color: #666666">-0.788</span> <span style="color: #666666">-2.338</span> H HETATM <span style="color: #666666">2</span> C <span style="color: #666666">0</span> <span style="color: #666666">-2.958</span> <span style="color: #666666">-0.067</span> <span style="color: #666666">-2.907</span> C HETATM <span style="color: #666666">3</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.027</span> <span style="color: #666666">-1.191</span> <span style="color: #666666">-6.987</span> H HETATM <span style="color: #666666">4</span> O <span style="color: #666666">0</span> <span style="color: #666666">-3.739</span> <span style="color: #666666">-1.861</span> <span style="color: #666666">-4.248</span> O HETATM <span style="color: #666666">5</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.408</span> <span style="color: #666666">-0.697</span> <span style="color: #666666">-4.233</span> C HETATM <span style="color: #666666">6</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.127</span> <span style="color: #666666">1.603</span> <span style="color: #666666">-5.928</span> H HETATM <span style="color: #666666">7</span> N <span style="color: #666666">0</span> <span style="color: #666666">-3.427</span> <span style="color: #666666">0.073</span> <span style="color: #666666">-5.380</span> N HETATM <span style="color: #666666">8</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.804</span> <span style="color: #666666">-0.532</span> <span style="color: #666666">-6.661</span> C HETATM <span style="color: #666666">9</span> H <span style="color: #666666">0</span> <span style="color: #666666">-4.713</span> <span style="color: #666666">-1.084</span> <span style="color: #666666">-6.541</span> H HETATM <span style="color: #666666">10</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.948</span> <span style="color: #666666">0.238</span> <span style="color: #666666">-7.390</span> H HETATM <span style="color: #666666">11</span> C <span style="color: #666666">0</span> <span style="color: #666666">-3.090</span> <span style="color: #666666">1.494</span> <span style="color: #666666">-5.474</span> C HETATM <span style="color: #666666">12</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.824</span> <span style="color: #666666">1.996</span> <span style="color: #666666">-6.069</span> H HETATM <span style="color: #666666">13</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.073</span> <span style="color: #666666">1.922</span> <span style="color: #666666">-4.493</span> H HETATM <span style="color: #666666">14</span> H <span style="color: #666666">0</span> <span style="color: #666666">-2.334</span> <span style="color: #666666">0.779</span> <span style="color: #666666">-3.108</span> H HETATM <span style="color: #666666">15</span> H <span style="color: #666666">0</span> <span style="color: #666666">-3.817</span> <span style="color: #666666">0.247</span> <span style="color: #666666">-2.352</span> H <span style="color: #AA22FF">END</span> CONECT <span style="color: #666666">1</span> <span style="color: #666666">2</span> CONECT <span style="color: #666666">2</span> <span style="color: #666666">1</span> <span style="color: #666666">5</span> <span style="color: #666666">14</span> <span style="color: #666666">15</span> CONECT <span style="color: #666666">3</span> <span style="color: #666666">8</span> CONECT <span style="color: #666666">4</span> <span style="color: #666666">5</span> CONECT <span style="color: #666666">5</span> <span style="color: #666666">2</span> <span style="color: #666666">4</span> <span style="color: #666666">7</span> CONECT <span style="color: #666666">6</span> <span style="color: #666666">11</span> CONECT <span style="color: #666666">7</span> <span style="color: #666666">5</span> <span style="color: #666666">8</span> <span style="color: #666666">11</span> CONECT <span style="color: #666666">8</span> <span style="color: #666666">3</span> <span style="color: #666666">7</span> <span style="color: #666666">9</span> <span style="color: #666666">10</span> CONECT <span style="color: #666666">9</span> <span style="color: #666666">8</span> CONECT <span style="color: #666666">10</span> <span style="color: #666666">8</span> CONECT <span style="color: #666666">11</span> <span style="color: #666666">6</span> <span style="color: #666666">7</span> <span style="color: #666666">12</span> <span style="color: #666666">13</span> CONECT <span style="color: #666666">12</span> <span style="color: #666666">11</span> CONECT <span style="color: #666666">13</span> <span style="color: #666666">11</span> CONECT <span style="color: #666666">14</span> <span style="color: #666666">2</span> CONECT <span style="color: #666666">15</span> <span style="color: #666666">2</span> </pre></div> </td></tr></table>

AMBER建模工具所给构型与其他来源构型的匹配

  1. 纤维素二聚体: amber结构与晶体结构
  2. 脂分子: amber结构与下载结构

有待改进

  1. 或许无须手动指定锚点原子, 而是自动查找测试所有可能的锚点原子, 这样就可以自动处理原子数很多的情况. 具体处理速度待考察.
  2. 匹配时仅仅考虑原子间的连接, 没有考虑具体坐标和构型, 无法区分不同的构象.
  3. 匹配分两步进行, 首先匹配非氢原子, 然后将氢原子按出现顺序分配到所连重原子上, 因此无法区分不同异构体的氢, 如顺反式.
  4. 上面两个缺陷或许可以使用骨架匹配后, 进行最小二乘叠合, 查找最小RMSD的方法解决.