从图论到解析分子结构的应用：Floyd-Warshall 算法

原文towardsdatascience.com/the-floyd-warshall-algorithm-from-graph-theory-applied-to-parsing-molecular-structures-39f8c99c9fe1Floyd-Warshall 算法在图论中至关重要因为它提供了一种有效的方法来计算图中所有节点对之间的最短路径。这个经典的动态规划算法在传统网络分析中的应用之外得到了广泛的应用。它通过读取描述哪些节点对通过单条边连接的矩阵并输出连接每个可能节点对的最小边数https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/43ce0e9b1b444bce6873eb4c5c1b43f2.png一组节点红色通过边浅绿色线条连接然后是两个由 Floyd-Warshall 算法计算的距离节点对之间的链接数深绿色带有虚线的例子。直接链接编码在一个称为“邻接矩阵”的矩阵中其元素为 1节点连接或 0未连接。算法的输出是一个大小相等的矩阵但包含所有节点之间的距离作为分离任何两个节点的最小边数。这个和其他所有图表都是由作者制作的。这是一些关于图中连接性的宝贵信息它找到了大量的应用例如在优化通信网络、分析社交网络中的联系或者正如我将在下面介绍的那样在解析分子结构——这是许多化学信息学和结构生物信息学任务的核心。在这篇帖子中我将向您展示如何使用 Floyd-Warshall 算法来计算分子中原子之间的键距离或者用另一种方式说是分离每个可能原子对的键的最小数量。希望我的例子不仅能展示算法在化学中的应用还能激发您在其他领域的不同应用中使用它。正如我在大多数项目和教程中所做的那样因为我提供了所有 JavaScript 代码所以你可以直接在 Web 应用和网络软件中使用它。实际上我从我们实验室正在开发的基于 Web 的分子图形程序中提取并改编了这里显示的代码你可以在这里了解更多信息HandMol 让化学教育的未来触手可及在过去我也描述了该软件的其他一些组件这些组件涉及相当有趣的数学和几何学其应用范围远超化学例如 Kabsch 算法使用 Kabsch 算法对两组 3D 点进行对齐的确定程序Floyd-Warshall 算法在化学中的应用Floyd-Warshall 算法旨在在图中的每对节点之间找到最短路径使其成为网络分析的有力工具。该算法通过系统地考虑所有可能的通过中间节点的路径并相应地更新最短路径估计来实现。它的效率和完整性使其非常适合需要直接路径计算的密集图。将 Floyd-Warshall 算法应用于解析键和分子结构在化学中图论的概念特别有助于可视化和分析分子结构。原子可以表示为图中的节点键表示为边。通过使用 Floyd-Warshall 算法我们可以计算分子中任意两个原子之间的最短路径或键数这是许多化学信息学任务以及计算机程序处理分子结构的核心信息https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4fc539bab35030da01e4c2701d511941.png以丁醇分子为例它由 4 个灰色的碳原子、一个红色的氧原子和 10 个白色的氢原子球体通过键棒状连接而成。这些原子被解析为图中的节点键被解析为边任意两个原子之间的键数对应于通过 Floyd-Warshall 算法计算的距离用绿色虚线表示。该过程从一个由原子组成列表开始这些原子通过单键直接连接信息由一个大小为 n x n 的矩阵提供其中 n 是系统中的原子节点数量其元素为 1 如果两个原子直接键合通过边连接否则为 0。这样的矩阵我称之为“键矩阵”但在图论术语中对应于“邻接矩阵”因为它描述了哪些节点是相邻的即它们通过一个边连接可以通过简单的化学规则从分子结构中计算出来如果两个原子足够接近它们就会键合就像我在这个视频中通过使用名为 HandMol 的免费工具形成键一样cdn.embedly.com/widgets/media.html?srchttps%3A%2F%2Fwww.youtube.com%2Fembed%2FFvNgtUuMde8%3Fstart%3D37%26feature%3Doembed%26start%3D37display_nameYouTubeurlhttps%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DFvNgtUuMde8imagehttps%3A%2F%2Fi.ytimg.com%2Fvi%2FFvNgtUuMde8%2Fhqdefault.jpgkeya19fcc184b9711e1b4764040d3dc5c07typetext%2Fhtmlschemayoutube现在我们来分析一下应用 Floyd-Warshall 算法确定分子中原子之间键数的 JavaScript 代码。代码演示1. 生成键矩阵函数getBondsMatrix()创建一个矩阵表示原子之间直接、化学键的存在或不存在基于它们在三维空间中的位置。在图论术语中这是“邻接矩阵”因为它描述了相邻节点对即通过直接边连接的节点。getBondsMatrix的输入只是一个包含所有分子原子 x、y、z 位置的数组没有其他内容。function getBondsMatrix(atomPositions){let bondsMatrix[];//Initialize empty matrix//Now get the distancesforallpossible pairs of atoms,check//ifthey are within bonding distancefor(let i0;iatomPositions.length;i){let distsqr;let bondsMatrixRow[];//Initialize empty rowforatom ifor(let ji1;jatomPositions.length;j){let newBondsMatrixElement0;//Get distance squared distsqrMath.pow((atomPositions[i].x-atomPositions[j].x),2)Math.pow((atomPositions[i].y-atomPositions[j].y),2)Math.pow((atomPositions[i].z-atomPositions[j].z),2);//If distance squaredisless than1.2x thesumof the//atomic radii squared,then atoms iandj are bonded const radSumradiiSum(elementradii[i],elementradii[j]);if(distsqrradSumamp;amp;chains[i]chains[j]){newBondsMatrixElement1;}bondsMatrixRow.push(newBondsMatrixElement);}bondsMatrix.push(bondsMatrixRow);}returnbondsMatrix;}注意一个非常小的改进技巧即我们比较的是平方距离而不是实际距离这样可以跳过一次平方根计算。顺便说一下基于原子半径的键确定阈值由一个读取元素名称并从表中获取其半径的函数处理function radiiSum(elementA,elementB){return1.2*Math.pow(elementA.radiuselementB.radius,2);}2. 通过 Floyd-Warshall 算法创建距离矩阵下面我将向您展示的createDistanceMatrix()函数初始化并填充基于上述生成的键矩阵的距离矩阵该矩阵作为输入传递并使用 Floyd-Warshall 算法。function createDistanceMatrix(bondsMatrix){adjMatrixbondsMatrix;const nadjMatrix.length;const distMatrixArray.from({length:n},()Array(n).fill(Infinity));//Initialize the distance matrix distMatrix which will at the end//of the procedure contain the matrix of bond distancesfor(let i0;in;i){for(let j0;jn;j){if(ij){distMatrix[i][j]0;}elseif(adjMatrix[i][j]1){distMatrix[i][j]1;}}}//Apply the Floyd-Warshall algorithm on the distance matrix setup abovefor(let k0;kn;k){for(let i0;in;i){for(let j0;jn;j){if(distMatrix[i][k]Infinityamp;amp;distMatrix[k][j]Infinity){distMatrix[i][j]Math.min(distMatrix[i][j],distMatrix[i][k]distMatrix[k][j]);}}}}returndistMatrix;}第一个嵌套的 for 循环对自环的节点距离设置为 0对直接键设置为 1后者来自输入的邻接矩阵。然后包含 3 个嵌套 for 循环的块是算法本身的核心。它通过考虑中间节点来更新距离矩阵以找到最短路径。三个嵌套的 for 循环已经表明该算法可能扩展性不佳实际上您是对的事实上在我们的 AR/VR 分子图形系统中它运行良好因为它仅限于相对较小的分子分子中包含几百到低千个原子。但让我们接下来探讨算法的确切限制以及有哪些替代方案。Floyd-Warshall 算法的可扩展性正如您在我的代码中看到的该算法很容易遵循和理解但正如我们在结束上一节时提到的它并不非常高效。对于需要计算所有最短路径对的密集图或较小图它既直接又有效。然而其立方时间复杂度仅适用于节点数量相对较小的图例如我们用于分子图形软件的几百到几千个节点。随着节点数量的增加该算法的性能迅速下降因为其 O(n³)的可扩展性。对于大型图如在大规模社交网络、道路网络或包含数千个原子的分子系统中遇到的图时间复杂度变得过于昂贵。运行时间随着节点数量的立方增长使得它对于非常大的图来说不切实际。在化学中这不一定总是一个问题因为许多看似庞大或甚至巨大的分子系统包含数万甚至数百万个原子实际上是由重复的元素组成其子结构在事先就已经定义好了。例如蛋白质由 20 种氨基酸组成其结构清晰不需要计算并且通过明确的规则和位置“肽”键相互连接。核酸也是如此由已知结构的碱基组成通过简单的已知连接磷酸基团连接。在材料科学中大多数材料都是较小单元的规则排列这又可以很容易地处理。尽管如此对于化学中某些应用需要更有效的方法来计算键距离矩阵研究人员正在开发这类更高级的方法例如在这里连接步骤推导法CSD方法一种通用的化学结构信息提取…是否有更有效的方法但在图论中根据图的性质和具体问题Floyd-Warshall 算法有更有效的替代方案。我将在下面简要概述它们迪杰斯特拉算法单源最短路径使用基于斐波那契堆的优先队列提供了一种更有效的方法来找到从单个“源”节点到所有其他节点的最短路径特别是在稀疏图中。对于单源查询它比弗洛伊德-沃舍尔算法更快但它不计算所有对的最短路径。约翰逊算法所有对最短路径在需要所有对的最短路径时对稀疏图是高效的。它是迪杰斯特拉算法的一个变体但针对所有对对于大型稀疏图它比弗洛伊德-沃舍尔算法更高效。A算法*单对最短路径通过使用启发式方法来尝试加快搜索速度解决单对最短路径问题。它的缩放是可变的在最佳情况下它可能比迪杰斯特拉算法Dijkstra’s algorithm更好。原则上它对于在具有启发式如地理距离在定义良好的构建块的情况下可能是分子结构的图中找到特定节点对之间的最短路径来说是最好的。在一个算法中体现的数学的力量弗洛伊德-沃舍尔算法Floyd-Warshall algorithm相当简单正如你在代码和这篇文章中看到的但它有大量的应用因此它成为了一个很好的例子说明了数学如何影响技术——以及它如何直接影响我们的生活。通过利用这个算法研究人员和分析人员可以深入了解复杂系统从我在这里关注的化学相互作用因为我每天都与分子结构打交道到各个领域的网络优化。在网络分析中弗洛伊德-沃舍尔算法和其他上述算法用于优化通信网络和数据流的路径。在城市规划中这些算法有助于提高交通系统的路线规划和交通管理。应用于社交网络它们有助于找到社交联系和影响网络中的最短路径这对于在 LinkedIn 或 Facebook 等社区中推荐连接的算法至关重要。如果你像我一样对数学的重要性感到惊讶请查看这个通过这个 YouTube 频道确保您的数学以及科学和技术的剂量www.lucianoabriata.com我会写关于我广泛兴趣范围内的一切自然、科学、技术、编程等。通过电子邮件订阅以获取我的新故事Subscribe to get my new stories。要咨询小型工作*请查看我的**服务页面。您可以通过这里联系我。您还可以在这里给我小费**.*