具有放松持久性的、善于捕捉键合效应的原子轨迹运动簇

《ACM Transactions on Spatial Algorithms and Systems》：Bond-Aware Moving Clusters of Atomic Trajectories with Relaxed Persistency

　　摘要
我们致力于高效检测分子轨迹集合中共同运动的物体簇的问题，这些物体簇除了满足空间邻近性外，还满足特定化学性质的语义标准。具体来说，我们关注的是来自不同分子的原子在运动过程中形成氢键（HB），并且这种氢键能够持续存在。虽然传统的连续空间邻近性是一个重要标准，但哪些分子中的原子在共同运动以及它们是否也在特定的空间范围内同样重要。使用现有的形式化方法（如群体、车队、蜂群等）可能很有吸引力，然而由于氢键形成的化学语义特性，存在显著差异：（1）簇内部有额外的约束；（2）从化学相互作用的角度来看，簇内的氢键可以在短时间内中断（即，键的持久性可以放宽），只要它很快就能重新建立。为了能够在原子轨迹数据集中检测到这种现象，我们引入了“基于氢键的松弛运动簇”（BARMC）模式——这是一种与分子动力学相关的新型时空运动簇。我们提供了一种高效检测BARMC模式的算法，并通过实验评估展示了其相较于基于传统车队的天真方法的优势。

人工智能总结
这个总结是使用自动化工具生成的，不是由文章作者撰写或审核的。它旨在帮助发现、帮助读者评估相关性，并协助来自相关研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的主要总结。完整文章是权威版本。点击这里了解更多信息。点击这里评论这个总结的准确性、清晰度和实用性。这样做将有助于改进和未来重新生成的版本。

1 引言
在过去三十年中，定位技术、计算设备和通信系统的进步使得产生了大量的运动数据[12, 26, 59]。这些大量的轨迹数据为检测各种移动模式提供了机会，从而提高了多种应用中使用的工具的效率和效果，例如旅行推荐[18, 87, 89]、动物运动模式[42, 43, 47]、交通预测和控制[61, 76, 90]等。作为一个具体的挑战，共同运动模式的检测在过去（即历史轨迹）和实时（即流式）轨迹的背景下吸引了越来越多的研究兴趣[70, 79]。已经探讨了几种变体，如运动簇[31, 40]、群体[6, 19]、车队[29]、群体模式[75]、蜂群[41]、排[39]、聚集[85, 86]、旅行伴侣[55, 70]、演化群体[34, 79]、伴侣群体[38]等。此外，其他最近的研究在轨迹挖掘中引入了来自多个领域的数据整合[88]。除了基于GPS设备（例如车辆、个人和水上船只）的移动物体的位置时间数据来源外，还研究了动物群体（如鱼群或鸟群）的集体运动模式[25, 68]。在自然界中，这些动态运动是由特定规则驱动的，这些规则并不总是明确的。例如，鱼群的行为模式是由吸引力、排斥力和平行取向等属性定义的[11]。此外，将语义属性添加到运动中[51]也带来了基于语义增强地理背景[54]和基于语义的距离函数[81]的运动聚类结果。在这项工作中，我们专注于化学领域，并考虑了分子动力学模拟（MDS）的设置，它生成了大量包含不同分子中各种原子位置的三维轨迹数据，这些原子参与了特定的相互作用。MDS是化学研究中的一个常见范式（例如新药物发现），因为它可以在早期探索阶段避免进行实际实验所涉及的高成本和风险[2]。与GPS轨迹数据相比，典型的MDS设置中的原子轨迹带来了独特的挑战。首先，单个原子在三维空间中移动，并且它们的运动不是独立的——即，多个原子通过分子内力结合在一起。其次，可能会发生分子间相互作用，在极端情况下，这会导致不同分子中的原子之间形成键。领域科学家对移动原子之间关系演变的兴趣（例如吸引力/排斥力和键的持久性）要求采用新的方法来高效有效地从原子/分子轨迹数据中提取知识。

在这项工作中，我们关注的是除了形成共同运动的物体簇（原子）之外，不同分子中的特定原子之间还发生了化学相互作用并且持续了相当长时间的设置。特别是，我们关注氢键（HB）在不同分子中的原子之间形成（并持续）的情况。由于氢键的独特性质，它在许多生物、化学和物理过程中起着关键作用，因此是多项研究的重要课题[7, 22, 33, 77]。鉴于邻近性在某种意义上是形成氢键的前提条件，我们将问题定义为高效发现紧密移动的原子簇。我们这样做是因为，在手性分离过程中（参见第2.1节），领域科学家不仅对氢键的形成和持久性感兴趣，也对周围的原子感兴趣。

领域专家通常通过测量寿命、占用率和网络 connectivity 来分析 MD 轨迹中的氢键模式。“氢键‘占用率’或‘分数存在’”计算特定氢键存在的总模拟时间的百分比[72]。例如，[69] 区分了水中的连续氢键和间歇性氢键，并将缩小的寿命与网络碎片化联系起来，而 [73] 将多糖手性静态相中的平均氢键寿命与对映体保留率相关联。连续寿命和间歇性寿命之间的区别对于传感器应用至关重要，因为键的形成和解离速率是传感器响应时间的最相关指标[84]。同样，[21] 识别了水中形成的桥接大分子之间的扩展氢键网络，并跟踪了这种桥链随时间的持久性，这对于理解光合作用系统中的质子转移机制至关重要。然而，这些方法主要依赖于成对的、平均的指标，这些指标的计算方式更为繁琐，也无法直接揭示哪些分子群体随时间持久并一起移动，这对于理解许多应用中氢键驱动的机制非常重要。我们论文的目的是通过检测时间连贯的氢键簇（允许短暂中断）来识别导致氢键形成和断裂的持续交互模式。

在现有结果中，例如车队和蜂群[29, 41]，并不具备高效检测 MDS 中感兴趣的共同运动簇的能力，在这项工作中，我们向这个领域迈出了第一步。我们在两个重要方面与之前的工作区分开来：（1）我们关注的是包含氢键的共同运动簇，这些氢键除了邻近性外，还涉及某些语义方面（例如原子类型）；（2）由于化学相互作用的性质（例如手性分离），我们需要容忍氢键在时间维度上存在的某些（允许的）间隙。这种跨越几个时间点的间隙的语义是由氢键形成的本质决定的。也就是说，紧密移动的不同分子中的原子进入化学相互作用形成氢键是常见的——但在某些时刻，特定的键可能是“松散”的。然而，从全局角度来看（例如，某种药物的吸收特性），氢键的短暂中断是可以接受的。为此，我们研究了一种称为“基于氢键的松弛运动簇”（BARMC）的新变体，这种变体更符合 MDS 设置中永久氢键的发现需求。这种基于轨迹、以簇为中心的视角符合领域专家的需求，并通过揭示关键氢键交互的识别、持续时间和时空一致性来增强传统方法。我们的主要贡献可以总结如下：
- 我们正式引入了一种称为 BARMC 模型的新型运动模式，允许容忍氢键存在的时间间隙。
- 我们提出了一种高效的方法 BARMC-Miner，通过早期剪除不满足 MDS 基本语义标准的簇来检测 BARMC，采用类似倒排索引的方法，首先关注语义，而不是直接进入簇检测。
- 我们提供了详细的实验评估，量化了所提出技术在效率方面的优势，并说明了参数的影响。

我们注意到这项工作的初步版本出现在 [64] 中，它除了引入了 BARMC 的概念外，还提出了一种天真的检测算法。除了更详细的讨论外，当前版本还提供了以下扩展：（i）我们引入了一种更高效的算法（BARMC-Miner）；（ii）我们提供了额外的实验结果；（iii）我们改进了工作与相关文献的定位（扩展列表）。

在本文的其余部分，第2节提供了背景和初步定义。第3节提供了模型的详细信息并形式化了 BARMC 的定义。第4节介绍了检测方法及其算法细节。第5节展示了实验结果，第6节将我们的结果置于相关工作的背景中。第7节提出了结论性意见并概述了未来工作的方向。

2 背景
我们现在讨论两个互补的方面，以便为正确的背景提供必要的信息：氢键形成的化学性质和共同移动物体的挖掘。

2.1 氢键的形成
如第1节所述，这项工作的重点在于手性分离领域，这是化学中的一个关键领域。简而言之，手性指的是分子内（以及分子间）原子群的空间取向在潜在相互作用中的重要性。手性分离消耗了化学过程工业中几乎80%的能量，并且可以由多种分子特性驱动。应用领域包括药物对映体的分离、液体提取、水溶液等[13, 23]。

本研究中使用的轨迹数据来自我们之前的工作[73, 74]，该工作使用 MDS 研究了聚合物表面上手性药物的分离。这些研究产生了约100 GB的原子轨迹数据，其中包含了药物分子原子与聚合物原子之间的运动和相互作用。这个数据集的重要性在于它能够识别关键的化学现象——特别是氢键的形成（和持久性）。氢键是一种分子间力，当一个氢（H）原子与一个高电负性的原子（称为供体）如氮（N）或氧（O）共价键合，并与另一个具有孤对电子的原子（受体）如另一个 N、O 或氟（F）相互作用时就会发生[4, 52]。图1 描述了氢键的形成过程。要被视为氢键，供体和受体原子需要在一定的结构阈值范围内，这个范围可以在2.2-4.0?之间[28, 46]。氢键中供体-受体原子的角度（α）通常为160°-180°[71]。

氢键在（生物）化学的广泛应用中深刻影响了结构和化学行为。例如，氢键是许多关键的生命维持属性的关键，如在寒冷天气中维持海洋中的生命。水分子之间的氢键（HB）形成了一个晶态几何图案，这阻止了水分子紧密地排列在一起，例如在液态水中，从而导致体积增大和密度降低。氢键的另一个影响是稳定蛋白质和DNA的结构。长氢键链的存在特别受到研究人员的关注，因为它影响了手性分离中的保留时间。我们注意到，在整个氢键链中，尽管供体-H-受体角度接近180度，但它可能会随时间略微偏离。这种偏差取决于多种因素，如氢键的强度、涉及分子的几何形状以及周围环境。2.2 车队轨迹检测旨在从某些数据集中提取与移动物体相关的群体行为（例如鱼群和汽车队列），这对于理解动物迁徙、交通流等更广泛的问题非常重要。正如第1节所提到的，已经提出了几种形式主义和算法来检测连续移动的轨迹模式——例如车队、蜂群、队列等[29, 39, 41]——其中特别值得关注的是车队。车队的概念最早在[29]中引入。正式来说，给定一组移动实体的轨迹，车队被定义为至少有m个在ε距离阈值内连续移动的实体，并且这种状态至少持续了k个时间点。然而，车队的定义只考虑了物体群体的连续接近性，而没有考虑到任何结构性背景。这使其不适用于需要某些（在我们的案例中是类型和空间）约束的情景，除了群体的整体接近性之外。因此，用于检测车队的算法不适合检测随时间持续存在的氢键。此外，它们也不能用于识别可接受或不可接受的氢键中断。然而，这对于手性分离的设置非常相关，因为在手性分离中，如前所述，特定氢键的小幅干扰后能够迅速重新建立，这对于保持给定共移动原子的“兴趣度”是完全可以接受的。图2展示了两个示例情景来说明语义影响。具体来说，图2(a)展示了四个物体，其中三个（o1, o2, o3）由于它们的连续接近而形成了一个车队。相比之下，尽管o4在t=2时与其他物体位于同一位置，但它并不属于该车队。作为补充，图2(b)展示了一个简化的2D情景，显示了尽管三个物体（O1、O2和O3）在三个时间点上相对接近，但由于它们空间关系的干扰，在T=2时没有形成键。现有的方法会正确地检测到整个T∈[1, 3]区间内车队的存在——然而，它们将无法捕捉到这一模式中的领域背景，这应该表明氢键实例在某个时间点缺失了。对于蜂群[41]和队列[39]模式的检测也是如此（这些方法只关注三个物体从未离开群体的事实）。在这项工作中，关键标准是保持形成氢键的原子的身份。图2. 移动群体：（a）没有语义约束；（b）有语义约束。我们采用[29]中的车队模型作为定义我们共移动模式的基础。与基于磁盘的连接性的鸟群不同，车队依赖于密度连通性，使它们更适合于原子群体的不规则几何形状。这一属性还允许我们在不改变基本定义的情况下纳入语义约束（例如，原子类型、供体-受体取向）。相比之下，蜂群[41]允许时间上的间隙，但不保证连续的密度连通性，这对于保持相互作用的化学有效性至关重要。同样，虽然可以在队列[39]的聚类阶段纳入语义信息，但在使用深度优先搜索（DFS）寻找满足我们给定约束的共移动群体时，会面临更大的挑战。3 模型与问题表述我们现在正式化在氢键链设置中共移动模式的新变体。原子的运动受到吸引力和排斥力的影响。力场影响原子距离、形状/取向等。化学键的形成通常取决于某些结构阈值。正如第2.1节所述，形成氢键有两个基本标准：原子来自不同分子的距离/接近性以及分子环的角度范围——在这项工作中，我们关注的是距离。通常，氢键的形成伴随着一个更全局的属性——即一群原子紧密地一起移动。这种近距离运动可以用车队[29]的概念来很好地捕捉。然而，并非所有的车队都同等重要——即，有些可能永远不会形成氢键。因此，我们需要引入“感知键的移动群体”（BAMC）的概念。定义3.1。（BAMC）设O表示一组移动原子的轨迹。不失一般性，假设它们都在T_start时间开始，并在T_end时间结束。BAMC是O的任何子集，包括至少m个原子轨迹，在至少k个连续时间单位内，这些原子的移动距离都在ε阈值范围内，并且在这些时间单位内始终存在氢键，这些原子来自m个原子中的一个固定子集。BAMC在概念上类似于车队或移动群体[29]，共享相同的ε、k和m参数。与传统的定义不同，我们的设置还强制执行了语义约束（原子类型）和由距离和角度定义的空间条件（见第2.1节）。图3说明了BAMC与“普通”车队之间的区别——没有氢键。我们观察到，除了形成车队1之外，还有三个原子（用灰色、蓝色和红色表示）形成了氢键。根据定义3.1，这被视为一个有效的BAMC实例。相比之下，车队2将不符合定义3.1的标准，因为尽管群体在整个五个时间点都持续存在，但没有形成氢键。图3. 车队与BAMC。虽然定义3.1捕捉到了原子保持接近性时氢键持续存在的现象，但我们重申，从化学过程的角度来看，特定的氢键可能会短暂消失然后再次形成。这是由于某些标准（距离或角度）暂时无效造成的。然而，在手性分离的特定设置中（即关于特定药物的性质）：（1）氢键连续性的中断是可以接受的，只要相同的氢键在短时间内再次形成。换句话说，连续时间点中氢键的短暂不存在仍然被认为构成一个有效的链，只要围绕氢键聚集在一起的周围原子继续这样移动。（2）同样重要的是，这种非存在氢键的总持续时间不应超过某个特定阈值。由于时间间隔会使得BAMC的概念失效，我们通过允许在时间领域内的“放松”来扩展定义3.1。更具体地说，我们引入了对时间间隔的容忍度，以捕捉氢键链中的中断。正式地，我们有以下BARMC的定义。定义3.2。（BARMC）与之前相同，设O表示一组原子轨迹，并假设它们都在T_start时间开始并在T_end时间结束。对于给定的τ1和τ2值，BARMC是O的任何子集，包括至少m个原子轨迹，在这些时间单位内，它们在距离阈值ε范围内移动了至少k个时间单位，在此期间：（1）最大有τ1个连续时间单位内没有氢键；（2）没有氢键的时间百分比不超过τ2。为了说明BAMC和BARMC模式之间的区别，请考虑图4中的示例。在这里，我们在任何k≥3的时间单位内都不会识别出任何BAMC，因为在t3时群体中不包含氢键。如果我们选择k=2，我们会得到两个较小的BAMC（从t1-t2到t4-t5）。相比之下，对于任何连续的时间间隔τ1=1时间单位，我们会将给定序列分类为BARMC模式，从t1-t5。图4. 移动群体中氢键的不连续性。虽然在这个例子中我们省略了τ2的作用，但τ2的存在基于领域的语义。也就是说，如果没有对间隔的上限，定义将允许出现“病态”情况，即使对于τ1=1，我们也可能会得到一个50%的时间没有氢键的BARMC模式（想象一个氢键交替形成和分解的序列）。显然，这不是一个有效的氢键链——即，氢键的存在应该是普遍的，其缺失的时间间隔应该是短暂的。作为具体示例，在我们实验中使用的数据集（参见第5节）中，领域专家已经识别出了氢键链，τ2的值是BARMC持续时间的≤25%。图5提供了一个三维运动的替代示例，以展示BAMC和BARMC的细微差别。如图1所示，图5中的氢原子、供体原子和受体原子分别用白色（氢）、蓝色（供体）和红色（受体）表示。因此，可以通过将图5中的原子与图1进行比较来推断出图5中簇的角度α和距离dθ。图5. BAMC与BARMC。在图5中，图3中显示的相同的三个（氢、供体和受体）原子，在不同时间的情况如下：—t=1：满足dθ≤3.5?和135°≤α≤180°的标准，形成了氢键。—t=2：由于再次满足标准，氢键持续存在。—t=3：尽管135°≤α≤180°，但dθ≤3.5?，氢键失效。—t=4：供体（蓝色）和受体（红色）原子再次靠近，dθ≤3.5?，重新形成了氢键。—t=5：氢键再次持续存在。对于τ1=1的情况，这种情况仍然会符合BARMC的标准（但不符合BAMC的标准）。我们以关于图3和图5的补充观察来结束这一节。即，使用传统的车队定义，从领域科学家的角度来看，会产生太多的假阳性，从而增加计算开销。相比之下，应用定义3.1（对时间间隔（τ1或τ2）或k没有容忍度）可能会引入假阴性，因为这会消除一个从相互作用角度来看有效的氢键链。4 方法论我们现在专注于处理BARMC查询的算法方面。首先，我们讨论了一种利用现有车队发现方法[29]的简单方法。然后，我们介绍了一种考虑领域背景的智能算法，以加快有效BARMC的检测速度。4.1 简单的BARMC检测这种方法首先检测所有可能的原子轨迹车队，然后分析每个车队中是否存在满足τ1和τ2约束的氢键链。以下是简单方法的主要步骤（第4.1.4节中的伪代码）：4.1.1 车队发现。我们采用了一种连贯的移动群体（CMC）算法[29]，该方法基于移动群体方法[31]来从轨迹中计算车队。我们使用基于密度的空间聚类算法DBSCAN[15]来计算群体。DBSCAN是一种基于密度的算法，它将彼此靠近的点分组，并将远离的点分开。该算法通过声明每个群体内的点密度远高于群体外的点来定义群体。这是通过使用两个参数来完成的：-\(\varepsilon\)：每个点“邻域”的半径；-\(\mathit {MinPts}\)：该点\(\varepsilon\)-邻域内的最小点数。 later，通过以下步骤验证车队（convoys）的条件：(i) 每个候选车队必须至少由k个连续的簇组成，以及(ii) 候选车队中的簇之间至少有m个共同的原子。4.1.2 HB检测。在这个步骤中，我们检查构成车队的簇中的HB链。回想一下（参见第2.1节），HB检测需要满足两个标准——即距离阈值(\(d_{\theta }\)和角度范围(\(\alpha\))。对于每个时间帧：- 我们计算在\(d_{\theta }\)距离阈值内的供体和受体对（在本研究中，\(d_{\theta }\) = 3.5 ?）。然后，我们找到每个供体原子最近的H原子。通过这样做，我们得到几个（供体、H和受体）组合，这些组合在一起可以形成一个HB。- 我们计算每个（供体、H和受体）组合的角度，并应用\(\alpha\)标准，我们选择\(135 ^\circ -180 ^\circ\)。- 我们将输出标记为HB实例。最后，我们检测所有BAMCs（参见定义3.1），这些BAMCs本质上是在每个时间帧中连续存在HB的车队或车队的一部分。4.1.3 BARMC计算。如果两个或更多BAMCs包含相同的n个原子（其中\(n \ge m)\)，并且包含相同的HB实例，并且保持时间间隔容忍度\(\tau _1\)和\(\tau _2\)（如定义3.2中解释的），我们将这些BAMCs合并并将结果标记为BARMC实例。如果只有一个BAMC，即没有与其他BAMC合并，则将其单独标记为BARMC。4.1.4 天真方法的伪代码。在算法1中，getConvoys函数是第4.1.1节中描述的车队的直接（且简单的）实现。一旦计算出车队，算法就会遍历所有时间帧来计算HB实例及其相应的语义属性。然后，在车队中搜索这些HB以计算BAMCs（如第4.1.2节中解释的）。最后，computeBARMCs函数只是接收这些BAMCs并迭代地构建BARMCs，确保满足\(\tau _1\)、\(\tau _2\)和k的条件，如第4.1.3节中详细说明的。4.2 提出的方法：BARMC-Miner。在前一节中，我们介绍了一种基于朴素技术的方法，通过识别连续移动的原子的簇来寻找BARMC模式，然后对它们进行“后处理”以验证域上下文（即考虑时间间隔的HB链的存在）。在本节中，我们提出了一种称为BARMC-Miner的新方法，使用语义知识来检测BARMCs。与朴素技术不同，BARMC-Miner首先关注给定时间点的簇级别的HB检测，然后检查这些簇是否形成BARMCs。4.2.1 输入数据的简化。在某个特定时间点形成HB时，我们只需要考虑两个原子来进行邻近性计算：来自两个不同分子的供体和受体（参见第2.1节）。我们利用这一领域知识来早期简化可能不会对BARMC有贡献的轨迹数据。这个想法是通过使用距离阈值参数\(d_{\delta }\)来细化原子对的组合，从而减少用于识别簇的数据量。\(d_{\delta }\)的值是根据化学领域确定的，这反映了上下文意识方面。我们如下说明给定时间点的初始简化过程：(1) 生成来自不同分子的原子对组合。(2) 检查哪些原子对之间的距离\(\le d_{\delta }\)。(3) 提取可能形成HB的原子所在的分子。我们注意到，我们保留“分子”而不仅仅是“原子”，是因为不仅仅是形成HB的个别原子是领域特定感兴趣的，HB实例周围的原子也可能有其他的“有趣”属性。虽然这些额外的“有趣”现象和属性确实值得注意，但对其潜在影响的彻底分析留待未来的工作。4.2.2 BARMCs的逐步构建。在这一步中，我们开始使用构成分子的原子来构建BARMCs（在简化之后）。首先，我们使用DBSCAN计算原子簇，并保留包含HB的簇作为后续时间帧中要考虑的BARMC候选者。对于每个候选者，我们分别维护间隔和\(\mathit {totalGaps}\)，以考虑\(\tau _1\)和\(\tau _2\)条件。每当看到HB不再存在的时间点时，我们相应地增加间隔和totalGaps的计数器。每当遇到HB时，间隔变量重新初始化为\(gap = 0\)。在每个时间点，对于长度为\(L = T_{end} - T_{start} + 1\)的给定BARMC候选者，只要\(gap \le \tau _1\)且\(\frac{totalGaps}{L} \le \tau _2\)，我们就继续跟踪该BARMC候选者。为了展示一个运行示例，我们参考图5。首先在\(t = 1\)计算簇，\(c_1\)是包含HB的簇，因此被保留为BARMC候选者。在\(t = 2\)时，它会继续存活；在\(t = 3\)时，当HB条件不满足时，间隔和totalGaps参数增加1，由于\(gap \le \tau _1 = 1\)，我们继续跟踪它。在\(t = 4\)时，由于我们看到HB重新出现，我们更新\(gap = 0\)，并继续跟踪BARMC候选者。最后，在\(k = 3\)时，\(\tau _1 = 1\)，这个BARMC候选者被输出为BARMC，因为它满足所有条件。算法2展示了使用BARMC-Miner进行BARMC检测的伪代码。BARMC-Miner接收参数data、\(\tau _1、\tau _2、k、m、\varepsilon\)、\(d_{\delta }\)作为输入。getinterestingMolecules函数简化数据并计算每个时间点的“有趣”分子。createClusters函数接收简化后的数据作为输入，并输出簇（使用DBSCAN）给定的\(\varepsilon\)和\(m = \mathit {MinPts}\)值。该算法检查每个新计算的簇是否与任何现有的BARMC候选者匹配——使用算法2a——通过取给定簇的索引和现有BARMC候选者的索引的交集。由于每个簇中的“索引”是帮助我们识别数据集中每个原子的唯一标识符，我们知道交集将给出相同的簇（如果它存在）。此外，由于交集检查至少有m个原子，因此可能有原子“动态”加入或离开那个特定簇。然而，根据这些原子的类型和邻近性，并不是所有原子都参与HB的形成。如果找到匹配，HBCheck函数检查交集中的共同索引是否包含HB，并返回一个布尔值以及参与HB的原子（以区分不同的HB实例）。在HBCheck函数内部还会进行进一步的简化，如果没有氢、氮或氧原子，我们就停止计算（并随后简化整个簇）。为了避免重复进行HB检查的计算，我们还维护一个字典（HBHashes），其中键是簇中原子的哈希值，值是该簇中原子的HB信息。由于每个帧中所有原子的位置都会改变，时间帧也是键的一部分。这样做的主要加速是在给定簇或簇的交集中查找HB时实现的。这个过程发生在HBCheck函数中检查HB时，之前会搜索字典以查看输入的HB信息是否已被计算过。另外：(1) 在给定时刻可能会有\(\gt\)1个HB实例；(2) 它们可能同时存在于同一个簇中。因此，我们将所有HB实例分别作为单独的BARMCs进行跟踪，并同时跟踪哪些HB原子已经被考虑过。算法2aa中的updateBARMCcandidate()函数存储和更新BARMC候选者的属性，如：BARMC的开始时间、结束时间、BARMC的新候选者索引（交集之后）、HB原子、间隔容忍度等。如果我们在给定帧中没有找到任何新的匹配簇，我们就增加BARMC候选者的时间间隔计数器。在增加计数器之后，我们检查每个候选者的BARMC条件（\(k、\tau _1、\tau _2\)），并相应地根据条件更新特定的候选者——即继续跟踪、丢弃或最终确定它。如果还有任何HB簇尚未被视为BARMC候选者，我们开始将它们作为新的BARMC候选者进行跟踪，如算法2b所示。当所有时间帧结束时，我们会检查任何剩余的BARMC候选者是否满足\(L \ge k\)和\(\tau _2\)的条件，并在适用的情况下将其最终确定为BARMC。这最后一步是为了处理算法运行过程中BARMC候选者从未超出任何\(\tau _1\)条件的情况。最后，返回所有（有效的）BARMC的信息。4.3 复杂性分析。我们在本节的最后对方法的复杂性分析进行说明。设n表示每个时间帧中的原子数，\(T = (T_{end} - T_{start})\)表示输入时间帧的总数。两种方法都采用了DBSCAN，其计算成本为\(O(n^2)\) [15, 29]。设\(p_t\)表示时间点t计算的簇数。我们需要将\(p_t\)中的簇与\(p_{t-1}\)中的簇进行比较以发现BARMCs。这相当于\((T-1)(p_t * p_{t-1})\)次比较。由于每个簇最多可以有n个原子，因此逐个元素比较簇以找到交集需要\(O(n^2)\)的时间。HB检查需要比较3种类型的原子（HB的要求）——在最坏的情况下，我们可能在一个簇中有所有n个原子，其中有\(\frac{n}{3}\)是键三角形的顶点候选者——导致\(O(n^3)\)的时间复杂性。回想一下，该函数还实现了一个Python字典（HBHashes），其平均最坏情况为\(O(p_t)\) [56]。因此，检查HB的总复杂性为\(O(n^3 + p_t)\)。朴素方法的复杂性（参见第4.1节）是DBSCAN聚类、车队发现和HB检查过程的总和，即\(O(Tn^{2} + (T-1)(p_t*p_{t-1}*n^2) + T\kappa {n^3 + p_t})\)，其中\(\kappa\)是车队的数量。由于我们在BARMC-Miner中简化了数据集，我们认为BARMC-Miner的HB检查将处理更少的数据，因此HB检查的复杂性为\(O(\bar{n}^3)\)，其中\(\bar{n} \ll n\)。因此，BARMC-Miner的时间复杂性为\(O((T-1)(p_t*p_{t-1}*\bar{n}^2) + T(\bar{n}^3 + p_t))\)。我们注意到，在最坏的情况下\(\bar{n} \approx n\)，朴素方法和BARMC-Miner的相应“O()”时间复杂性将是相似的。然而，正如我们在第5.1节中将展示的，\(\bar{n} \ll n\)在运行时间方面有着显著的影响。5 实验我们现在将介绍我们的实验评估的详细信息，包括设置、效率、算法选择的影响以及参数的影响。我们注意到，为了保证再现性，源代码和样本数据集已公开发布在 https://github.com/abdullahshamail/BARMC 上。实验使用 Python 3.11.9 在一台配备以下配置的 PC 上进行：Intel(R) Xeon(R) CPU E-2124G v5 @3.40GHz 处理器、32 GB RAM、1.5 TB 硬盘存储空间以及 Windows 11 Enterprise 64 位操作系统。用于研究我们提出方法性能的原始数据集（D1）包含了原子（和分子）运动信息，这些信息以四元组（x, y, z, t）的形式表示，其中 (x, y, z) 是给定原子在时间 t 时的 3D 坐标，数据来源于 MDS [73, 74]。该数据集包含 10 个黄酮类药物分子和 4 个聚合物基底（总计有 {\bf n} = 6126 个原子）。我们从原始数据中提取了 5 个随机数据集（分别记为 D1_1、D1_2……D1_5），每个数据集包含 {\bf n} = 6126 个原子的轨迹，时间跨度为 \(T = 500\) 个时间帧，因为实际上黄酮类药物中的氢键（HB）持续时间预计不会超过这个范围。随机化是在原始数据集中的 \(T = 500\) 个时间帧中进行选择，而原始数据集包含 800,000 个时间帧。确保所有 500 个时间帧都是唯一的（没有重叠）。此外，为了展示更大 n 值的效果，我们使用领域专家所称的“超胞”[48]方法从当前数据集中合成了一个分子动力学（MD）模拟。其思想是创建模拟盒的副本，并将它们扩展到一个 \(x \times y \times z\) 的网格中，同时保持与原始模拟相同的化学性质，并对坐标添加抖动以创建新的模拟。例如，从 D1 中生成一个 n=12252 = (2×6126) 的数据集，我们会创建一个 \(2 \times 1 \times 1\) 的网格。根据这一原则，我们生成了以下具有给定 n 值的数据集：—D0, n = 3063, T = 5000—D2, n = 12252, T = 5000—D3, n = 24504, T = 5000—D4, n = 49008, T = 5000—D5, n = 98016, T = 5000。

5.1 性能评估
我们注意到这里的参数值设置为 \(\varepsilon = 3.5\) ? 和 \(m = MinPts = 25\) 个原子。从全局角度来看，如表 1 所示，BARMC-Miner 在不同数据集 \(D1_1 - D1_5\) 上的一致性优于朴素方法，优势几乎相同。

表 1. 数据集 平朴素方法（s）BARMC-Miner（s）
\(D1_1\) 35.24 21.46
\(D1_2\) 35.88 21.29
\(D1_3\) 35.13 21.54
\(D1_4\) 38.00 21.04
\(D1_5\) 34.90 21.77

朴素方法和 BARMC-Miner 的计算时间（s）（k=1）：
朴素方法检测：我们现在讨论朴素方法，我们对输入数据集应用车队算法，随后检查输出车队中的氢键（HB），并在计算出 BAMCs 后执行 BARMC 检测。对于 \(D1_1\)，传统的车队查询给出了七个车队；然而，在进行氢键检查后，我们观察到只有一个车队含有 HB 实例。我们还观察到该车队中存在两种不同类型的 HB（分别表示为 HB 1 和 HB 2）。然后，我们计算该特定车队中 HB 1 和 HB 2 的连续存在情况，如图 6 所示。

图 6. 检测到的 BAMCs（\(D1_1\)）。

接下来，我们考虑时间松弛参数（\(\tau _1\) 和 \(\tau _2\) 来计算 BARMCs。我们选择 \(\tau _1 = 2\) 时间单位（两个 HB 实例之间的最大允许时间间隔）和 \(\tau _2 = 0.25\)（允许每个 BARMC 持续时间内有 25% 的实例是非 HB 实例），这些参数是领域专家合理估计的。图 7 显示了在给定 \(\tau _1\) 和 \(\tau _2\) 条件下计算的 BARMC 实例。

图 7. 检测到的 BAMCs（\(D1_1\)）。

我们观察到，相对较大的 \(\tau _1\) 值（例如，\(\tau _1 = 4\) 时间单位）可以在 \(D1_1\) 中产生 0-499 个 HB 1 的 BARMC 实例。然而，允许过大的值——例如，\(\tau _1 = 10\)——可能对于实际的分子动力学（MDS）设置来说过于宽松。进一步的讨论在第 5.2 节中提出。

使用 BARMC-Miner 检测 BARMCs：我们现在讨论相同的数据集的 BARMC-Miner 算法。回想一下，在第 4.2.1 节中，使用了 \(d_{\delta }\) 参数来移除没有机会形成 HB 的不必要数据部分。由于 HB 临近阈值 (\(d_{\theta }\)) 是 \(\le 3.5\) ?，我们选择 \(d_{\delta }\) 值为 4 ? 以避免意外修剪数据的重要部分。在这个实验中，我们保持了朴素检测相同的超参数设置，除了 \(d_{\delta }\)。

从图 6、图 7 和表 1 中，我们观察到 BARMC-Miner 发现的 BARMCs 与朴素方法相同，但在计算上效率要高得多——例如，对于 \(D1_1\)，时间是 21.46 秒对比 35.24 秒。基于领域语义的早期修剪使 BARMC-Miner 获得了更好的性能（参见第 4.3 节中的复杂性分析）。对于 \(D1_2\) 子集的图 8 和图 9（以及表 1）也有类似的观察结果。效率：有两个参数显著影响检测 BARMCs 的效率：数据集的大小（时间帧数 T）和输入数据中的原子数（n）。我们在下面介绍了它们的影响。

图 8. 检测到的 BAMCs（D2）。

图 9. 检测到的 BAMCs（D2）。

数据大小（T）：我们通过改变输入数据长度（T）来比较朴素 BARMC 方法和 BARMC-Miner 的计算时间，并在图 10 和图 11 中展示结果。

图 10. 朴素方法 vs. BARMC-Miner（在 \(D1 = n = 6126\) 上）。

图 11. 朴素方法 vs. BARMC-Miner（在 \(D3 = n = 24504\) 上）。

从图 10（来自数据集 D1）和图 11（来自数据集 D3）可以看出，当 T 的值较大时，BARMC-Miner 的优势更加明显，这说明了 \(\bar{n}\) 与 n 的实际影响（参见第 4.3 节中的复杂性讨论）。作为补充说明，朴素方法和 BARMC-Miner 的计算时间都随着数据大小（以时间单位 T 计）的增加而呈相对线性增长。此外，与朴素方法相比，BARMC-Miner 在改变 k 值方面具有更大的灵活性（在第 5.2 节中进一步讨论）。在图 12（针对数据集 \(D1_5\)）中，我们观察到对于 \(T \ge 150\)，BARMC-Miner 的计算时间几乎保持稳定。

输入中的原子数（n）：
图 12. 朴素方法 vs. BARMC-Miner（在 \(D1_1\) 上），对于不同的 k 值）。

从另一个角度来看，我们还分析了改变输入原子总数（n）对检测 BARMCs 的计算时间的影响，并比较了朴素方法和 BARMC-Miner 的效率。在图 13 中，对于朴素方法，随着 n 的增加，处理的原子数也在增加。由于该方法不使用任何修剪，主要的计算开销来自 DBSCAN 和车队检测过程中的簇存活跟踪，以及 BARMC 检测期间的 HB 计算。

图 13. 随着 n 的变化，BARMC 计算时间：朴素方法 vs. BARMC-Miner，\(T = 5000\)。

如图 12 所示，随着 n 的增加，被修剪的数据大小（\(\bar{n}\) 也在增加。这是因为能够形成 HB 的原子比例的增长远慢于原子总数，导致更多的修剪，从而提高了速度。BARMC-Miner 跟踪 BARMCs 的语义信息的能力使其在较大的 n 值下运行得更快，如图 13 和表 2 所示。

表 2. 不同数据集的加速百分比和修剪百分比(\(\bar{n}:n\)
\(D0 \ (n=3063)\) 16.26 51.45 0.49
\(D1 \ (n=6126)\) 51.13 75.30 0.25
\(D2 \ (n=12252)\) 49.02 87.19 0.13
\(D3 \ (n=24504)\) 57.97 87.23 0.13
\(D4 \ (n=49008)\) 72.98 89.70 0.10
\(D5 \ (n=98016)\) 77.36 93.42 0.07

对于所有 n 值，BARMC-Miner 一致性地优于朴素方法。如表 2 所示，对于 \(D1 = n = 6126\)，BARMC-Miner 比朴素方法快 \(51.13\%\)。同样，对于 \(D5 = n = 98016\)，它快 \(77.36\%\)。这种效率的提升是因为修剪后的数据大小 \(\bar{n}\) 显著小于 n，使得 BARMC-Miner 能够最小化不必要的计算，只关注相关的数据子集。这种计算时间的明显增长与图 10 和图 11 中显示的早期结果一致，是 BARMC-Miner 相对于朴素方法所提供改进的另一个量化观察。

如图 13 所示，朴素算法的增长速度比 BARMC-Miner 快，而在所有测试的数据集中，BARMC-Miner 一直优于朴素方法。这表明修剪策略大大扩展了实际应用的范围。虽然最坏情况下的复杂度包含一个立方项（参见第 4.3 节），但在实践中，修剪确保了有效成本的增长要慢得多，推迟了不切实际运行时间的出现。因此，我们再次强调，与朴素方法相比，BARMC-Miner 使得 BARMCs 的检测更加实用和高效。

5.2 参数的影响
Epsilon (\(\varepsilon\))：作为 DBSCAN 算法的一部分，选择合适的 \(\varepsilon\) 值非常重要，因为它直接影响将形成簇的数据点。在我们的用例中，原子非常密集，平均原子间距为 1.54? [10]。因此，\(\varepsilon\) 的微小变化可以显著改变输出。例如，较大的 \(\varepsilon\) 值几乎可以将所有原子放入同一个簇中。相反，较小的 \(\varepsilon\) 值可能会错过那些具有形成键接近性的原子。

我们在图 14 中看到了改变 \(\varepsilon\) 值对生成的簇数量的影响。如图所示，\(\varepsilon\) 从 \(\varepsilon = 2\) ? 变到 \(\varepsilon = 2.25\) ? 时，簇的数量从 607 降低到 356。此外，当我们从 \(\varepsilon = 2.25\) ? 变到 \(\varepsilon = 2.5\) ? 时，簇的数量急剧减少，因为 \(\varepsilon\) 现在远大于平均原子间距值，导致原子属于同一个更大的簇。由于 HB 形成的空间约束是 \(d_{\theta } \le 3.5\) ?（参见第 4.1.2 节），我们在其余实验中谨慎地使用了 \(\varepsilon = 3.5\) ?，认为任何对于 \(\varepsilon \lt 3.5\) ? 创建的簇在领域中没有意义（即，没有形成 HB 的潜力）。例如，对于 \(\varepsilon = 2\) ? 创建的 607 个簇包含的原子没有形成 HB 的潜力。因此，这些簇不能被考虑用于 BAMC 或 BARMC。

图 14. 改变 Epsilon (?) 对簇形成的影响。

时间间隔松弛（\(\tau _1\) 和 \(\tau _2\)：我们在表 3 和表 4 中展示了 \(\tau _1\) 和 \(\tau _2\) 对 BARMCs 的影响，同时保持其他参数不变：\(\varepsilon = 3.5\) ?、\(m = \mathit {MinPts} = 25\) 个原子和 \(k = 3\) 时间单位。在表 5 中，我们展示了 \(k = 1\) 的 BAMCs（可用于构建 BARMCs）。需要注意的是，提供的表格包含了选择性截断的数据，以有效地展示改变 \(\tau _1\) 和 \(\tau _2\) 值的影响。虽然只展示了一种类型的 BAMC 和 BARMC（就 HB 而言），但重要的是要理解在这些相同的时间间隔内可能存在其他类型的 BAMC 和 BARMC。表 3、表 4 和表 5 的数据是 \(D1_1\) 的子集，可以在图 6 和图 7 中（前 50 个时间单位）中可视化 HB 1 的情况。

表 3. \(\tau _1\) 对 BARMCs 的影响
开始 结束 1127 3048
2148

表 4. \(\tau _2\) 对 BARMCs 的影响
开始 结束 0.21 270.25
1273048

表 5. \(\tau _2\) 对 BAMC 的影响
开始 结束 1113 2152
733030
43232534
4364548

在表 3 中，我们将 \(\tau _1\) 从 1 时间单位变化到 2 时间单位，同时保持 \(\tau _2\) 为 0.25。对于 \(\tau _1 = 1\)，从表 5 中我们看到 BAMC 1 和 BAMC 2 之间的间隔是 \(t = 1\) 和 \(t = 2\)。因此，我们将 BAMC 1 和 BAMC 2 合并为一个 BARMC，区间为 \((start, end) = (1,27)\)，因为也满足了 \(\tau _2\) 的条件（\(\frac{1}{27 - 1 + 1} \le 0.25\)）。对于 BAMC 3、4、5 和 6，计算相同，以形成区间 \((start, end) = (30,48)\) 的 BARMC。

对于 \(\tau _1 = 2\)，从表 5 中我们看到所有 BAMC 之间的间隔 \(\le 2\)。总HB间隙也在\(\tau _2\)的范围内（\(\frac{6}{48 - 1 + 1} \le 0.25\)）。因此，所有6个BAMC结合起来构成了一个单一的BARMC，用于区间\((start,end) = (1,48)\)和\(\tau _1 = 2\)。表4显示了\(\tau _2\)变化的影响（\(\tau _1\)被设置为2个时间单位）。请注意，当\(\tau _2\)从0.25增加到0.35时，根据新设定的\(\tau _2 = 0.35\)，BAMC 4和BAMC 5变成了有效的BARMC。连续时间单位的最小长度（k）：在这里，我们解释了k对BAMC和BARMC检测的影响。对于任何k个连续时间单位，我们忽略了\(P = \lbrace p_1, p_2, p_i, ... \rbrace\)中的BAMC模式，如果\(length(p_i) \lt k\)个时间单位。因此，在使用朴素方法构建BARMC时，长度小于k的模式将会被忽略。为了说明这一现象，我们详细讨论了表5中呈现的BAMCs（计算的是\(k = 1\)的情况）。对于\(k = 2\)，BAMCs 3和4将不会被检测为BAMCs，从而输出BAMCs \(1, 2, 5\)和6。这将影响表3和表4中显示的BARMC结果，因为这些结果是基于朴素BARMC方法计算得出的（参见第4.1节）。例如，在表3中，从\(30 - 48\)时间单位的BARMC将变为\(34 - 48\)时间单位的BARMC，而\(\tau _1\)和\(\tau _2\)参数保持不变。因此，为了比较朴素方法和BARMC-Miner的结果和效率，我们选择\(k = 1\)（参见表1）。相比之下（如第5.1节简要讨论的），提出的BARMC-Miner不依赖于BAMCs，因此不受k值的限制。它可以成功检测到任何\(k\le (T_{end} - T_{start} + 1)\)的BARMC，如果它们存在的话。为了进一步说明k的敏感性，我们介绍了召回率的定义：\(\begin{equation*} Recall = \frac{Found Instances}{Total Expected Instances}, \end{equation*}\)，其中TotalExpectedInstances = FoundInstances + MissedInstances\)。根据这个定义，MissedInstances代表BARMC的假阴性结果。例如，对于\(k = 3\)，BARMC-Miner正确检测到的BARMC范围是\([start, end] = [10, 21]\)，而朴素方法输出的是\([start, end] = [14, 21]\)。对于这个例子，\(Found Instances = 8\)而\(Total Expected Instances = 12\)，因此召回率为\(\frac{8}{12}\)。表6展示了在参数值\(k = [1, 10]\)、\(\tau _1 = 2\)、\(\tau _2 = 0.25\)、\(\varepsilon = 3.5\)和\(T = 500\)时间单位（针对\(D1_1\)数据集）的整体召回率。如表所示，随着k值的增加，朴素方法的召回率开始下降，表明无法正确检测到所有BARMC，从而引入了假阴性结果。相比之下，BARMC-Miner的召回率保持为1，显示了该算法的强大性和对k值的不变性。

关于参数选择的讨论：如上所述，每个参数对结果的影响不同，因此选择应基于领域专家认为有意义的标准。对于\(\varepsilon\)，因为在当前设置中识别HB需要\(\varepsilon \ge 3.5\)，我们将\(\varepsilon = 3.5\)固定为我们的实验值。然而，如果领域专家修改了HB的标准，这个值可能会被调整。间隙参数\(\tau _1\)和\(\tau _2\)同样取决于专家认为HB持续性中可接受的中断程度。设置\(\tau _1 = 2\)允许最多两个连续的非HB帧，而\(\tau _2 = 0.25\)允许整个BARMC中最多有\(25\%\)的非HB帧（即，至少有\(75\%)必须是HB帧）。这些选择可以根据应用进行调整；例如，[69, 72]讨论了“连续”与“间歇性”HB寿命，这可以为\(\tau _1\)和\(\tau _2\)提供适当的值。最后，k反映了我们感兴趣的最小HB寿命，并且可能会根据分析标准而变化。BARMC-Miner的一个实际优势是它支持变化k值而不会丢失信息。

我们以对实验评估的更广泛讨论来结束这一节。我们使用了一个非常具体的MDS数据集（并为部分实验生成了新的数据集），并将朴素版本的解决方案与上下文感知的解决方案进行了比较。鉴于相关文献的丰富性（参见第6节），人们可能会质疑为什么不使用更多的数据集和基线。首先，正如引言中所述，据我们所知，这项工作是将连续共位模式应用于化学相互作用领域的第一步，在这里：（i）运动数据被赋予了语义属性；（ii）在簇内有一个额外的标准（针对HBs）；（iii）运动是三维的。来自时空文献的相关工作主要集中在二维运动上，而这些数据集不包含这里研究领域的相关标准。即使是较新的研究[38]，它允许队列中的时间间隙，并且只比较了精确解（ES-ECMC）和近似解（CS-ACMC）。此外，许多工作使用了特定的数据结构（例如[38]中的R树和[20]中的网格）或压缩方法（例如[29]），这些方法：（a）不能直接扩展到三维，也不能轻易地添加适当的语义特征，因为它们会包含大量的“死区”，并可能产生大量的假阳性结果；（b）特别是对于近似解——不能保证没有假阴性结果。尽管确实有报道了包含更多原子的MDS数据集，例如大型生物分子组装、病毒衣壳或在领导级超级计算机上的材料系统[53, 65, 67]，但这些研究通常在不同的环境中进行（例如，粗粒度模型、专用硬件或大规模并行HPC代码），并且与我们解决的问题（氢键和持久性）不匹配。然而，在我们的案例中，数据集实际上并不“小”，因为它们的复杂性来自于原子数量（n）和时间帧数量（T）的结合。例如，对于\(D5 = n = 98016\)和\(T = 5000\)，我们得到了490,080,000（约4.9亿）个原子位置，这使得高效分析成为一项计算上具有挑战性的任务。因此，BARMC-Miner中提出的剪枝策略和效率提升对于使此类分析变得可行至关重要，即使n本身看起来可能“小”。

5.3 讨论
我们以对实验评估的更广泛讨论来结束这一节。我们使用了一个来自MDS的非常具体的数据集（并且为部分实验生成了新的数据集），并将朴素版本的解决方案与上下文感知的解决方案进行了比较。鉴于相关文献的丰富性（参见第6节），人们可能会质疑为什么不再使用其他数据集和基线。首先，正如引言中所述，据我们所知，这项工作是将连续共位模式应用于化学相互作用领域的首步，在这里：（i）运动数据被赋予了语义属性；（ii）在簇内有一个额外的标准（针对HBs）；（iii）运动是三维的。来自时空文献的相关工作集中在二维运动上，而这些数据集不包含与这里研究的领域相关的标准。即使是较新的研究[38]，它允许队列中的时间间隙，也仅比较了精确解（ES-ECMC）和近似解（CS-ACMC）。接下来，许多工作使用了特定的数据结构（例如[38]中的R树和[20]中的网格）或压缩方法（例如[29]），这些方法：（a）不能直接扩展到三维，也不能轻易地添加适当的语义特征，因为它们会包含大量的“死区”，并可能产生大量的假阳性结果；（b）特别是对于近似解——不能保证没有假阴性结果。尽管确实有报道了包含更多原子的MDS数据集，例如大型生物分子组装、病毒衣壳或在领导级超级计算机上的材料系统[53, 65, 67]，但这些研究通常在不同的环境中进行（例如，粗粒度模型、专用硬件或大规模并行HPC代码），并且与我们解决的具体问题（氢键和持久性）不符。然而，在我们的案例中，数据集在实践中并不是“小”的，因为它们的复杂性来源于原子数量（n）和时间帧数量（T）的结合。例如，对于\(D5 = n = 98016\)和\(T = 5000\)，我们得到了490,080,000（约4.9亿）个原子位置，这使得高效分析成为一项计算上具有挑战性的任务。因此，BARMC-Miner中提出的剪枝策略和效率提升对于使此类分析变得可行至关重要。

相关工作可以分为三大类：
时空数据和共位运动：在多篇工作中研究了在特定时间内一起移动的对象群体，这些问题设置有很多变体。
历史上，移动对象的相对运动在REMO框架[35]中首次被引入，是从运动方向的角度来研究地理空间生命线的。随后，[36]通过引入位置的概念扩展了这项工作，并识别了诸如群体、领导、聚合和相遇等时空模式。随后出现了更严格的算法方法——例如，计算群体（及其最长持续时间）[6, 19]以及领导、聚合和相遇[20]——无论是从精确的角度还是近似的角度。大约在同一时间，移动簇在[31]中被引入，定义为在连续时间瞬间持续存在的空间簇序列。这与群体略有不同，群体指的是一组移动的实体，它们始终在固定（用户指定的参数）大小的圆盘内移动一段时间\[6\]。另一种变体是车队模式，它不同于群体，它们放宽了基于圆盘的邻近性约束，利用了基于密度的聚类概念[29]。具体来说，车队被定义为一组一起移动的移动对象，它们始终属于相同的基于密度的簇。然而，群体和车队模式都要求移动实体至少在k个连续的时间戳内保持在一起。
我们工作的主要区别在于：（1）我们基于语义标准在簇内要求了进一步的约束；（2）我们放宽了连续时间实例的要求（即，我们允许结构在某些短时间内的“中断”。
与传统的车队类似，我们的工作允许个别实体（原子）动态地离开/加入移动簇——这可能会影响该移动簇内的HB。一些考虑共位运动概念的工作也允许时间域中的中断。例如，[85, 86]关注的是在至少k个连续时间帧内持续的簇序列，其中相邻簇之间的距离阈值d是指定的。每个聚集模式簇必须包含至少\(m_{p}\)个参与者，这些参与者至少存在于\(k_{p}\)个簇中（无论是连续的还是非连续的）。群体模式也基于基于圆盘的聚类概念，捕捉了一定时间帧内对象的移动，这些时间帧可以是非连续的\[75\]。类似于群体模式，[41]中引入了群体的概念，它允许移动对象在一系列非连续的时间帧内一起移动。群体可以被视为车队模式的一个变体，它允许成员暂时离开群体。然而，群体模式没有考虑非连续簇中的时间限制。在我们的工作中，这可能会导致错误地识别移动对象簇的序列，从而产生有用的交互。
[60]中提出了一种更广泛的调查共移动模式群体的方法论，并在SECONDO中实现为一个通用查询。另一种类似的方法在[9]中提出，称为“轨迹分组结构”，它讨论了可能在时间上允许多样中断的共移动簇。我们的工作在基于距离的关系方面不太通用——然而，我们有两个独特的新约束：（1）我们关注满足某些距离标准（\(d_{\theta }\) = 3.5 ?）的原子类型；（2）我们结合了角度标准（\(135 ^\circ \le \alpha \le 180 ^\circ\)）。我们还包括了对HB短暂断裂（以及随后的重新建立）的容忍阈值（\(\tau _1\)和\(\tau _2\)），这是问题领域的一个结果——这对于问题领域来说是一个相当重要的属性\[8, 44, 45\]。作为我们未来工作的一部分，我们计划扩展语义约束的范围，以便可以研究不同类型的键（及其持久性），例如离子键、\(\pi\)-键[32, 63]等。
队列模式[39]通过引入“局部连续”的标准克服了群体模式的这一缺点。它检测在某些时间内保持在一起的共移动对象模式，这些模式具有时间间隙，其中连续时间段必须具有最小长度，该长度应用于队列。作为补充，[38]中的伴生群组提出了一个移动对象簇的通用版本，其中至少有m个共移动对象在\(\varepsilon\)的距离内至少保持k个时间瞬间，并且该工作提出了精确解和近似解。
我们工作的主要区别在于：（1）我们同时考虑了簇内的语义上下文和特定原子之间的邻近性；（2）除了考虑间隙之外，我们还对间隙的总持续时间进行了限制；（3）我们使用语义上下文进行剪枝，这显著提高了BARMC-Miner的效率。
语义轨迹：另一组相关的工作基于语义轨迹的概念（参见[51]的综述）。研究人员意识到了他们的分析需要多个方面的考虑[57]，并在这些设置中处理了查询处理[78]以及聚类[81]和总结[54]。例如，MAT-Sum [54]采用了一种以位置为中心的增强方法来总结大量移动数据，同时保留了重要的语义信息。在[81]中提出了一个任务感知的特征选择和使用它们的压缩表示来聚类轨迹的方法，适用于运动伴随着多个特征的情景。
作为这些工作的补充，我们关注了类似车队的查询，这些查询结合了对HB寿命中时间间隙的容忍度。此外，这项研究并没有聚焦于动作（例如“行走”和“停留”）或地点（例如“咖啡馆”和“博物馆”）的相似语义描述符，而是关注来自不同分子的不同原子之间的关联。在分子动力学中，首先我们注意到，在处理键的连续性时，通常需要检查所有粒子之间的所有相互作用，这是一个非常耗时的过程。为了提高查询处理的效率，文献[1]提出了一种方法，即通过使用特定的截止距离来避免对短程非键合相互作用（如氢键[50]）中的所有原子对进行距离计算。然而，该研究仅考虑了分子动力学（MDS）设置中的（连续）窗口查询。从更广泛的角度来看，近年来人们已经在化学领域的各种问题上积极应用机器学习技术[30]，主要集中在对大型数据库中的数据实例进行分类，并基于数据的组织和/或结构进行预测。例如，文献[58]提出了一种基于图的框架来检测（并可视化）相互作用事件；[80]提出了一种基于图神经网络（GNN）的分子表示学习方法。还有一些研究致力于识别模式[14]并提供用于分析相互作用的可视化工具[27, 49]。然而，据我们所知，现有的工作尚未以正式的方式处理结构的持久性问题（包括容忍间隙的情况）以及时空共位模式。

我们在这个部分的最后指出，在流式数据的环境中也研究过移动模式的问题——例如，从流式中找到旅行伙伴[55, 70]，以及使用滑动窗口来挖掘演变模式[34, 79]。在分子动力学的背景下研究流式变体是我们未来工作的方向，因为这可能会通过新颖的“提前终止”标准加快模拟过程。

**7 结论**
我们解决了在分子动力学数据中检测持久性氢键（HBs）这一新颖问题，改进了将共同移动纯粹视为基于邻近性的传统认知（具体来说是车队）。我们提出了BARMC这一新方法，该方法允许对HBs的持久性有一定的容忍度（即时间间隔）。我们还开发了一种高效的BARMC检测算法BARMC-Miner，与朴素方法相比，它具有某种程度的上下文意识。我们的实验表明，先过滤HBs然后构建BARMCs可以显著提高处理效率。对于领域专家来说，我们检测BARMCs的应用起到了语义过滤的作用，将复杂的原子运动简化为具有化学解释意义的事件，从而建立了微观相互作用与宏观化学功能之间的联系。具体来说，在我们的工作中，我们讨论了氢键，这些氢键被认为是地球上生命存在的关键[24]。我们的工作通过帮助领域专家分析寿命、占据率和持久性，有助于他们理解从酶催化到长距离别构通讯等各种过程[8]。在药物发现中，氢键动态和水介导的氢键网络已被直接关联到配体选择性、结合亲和力和停留时间[37, 62]。我们计划在未来解决我们工作的多个扩展问题。在化学领域，我们将在个体时间点引入其他上下文维度，例如分子环平面之间的角度。进一步加速预处理的一个可能方法是构建分子周围的边界结构（参见[3]），并探索用于更大数据集的分布式系统[5]。我们还计划解决流式环境中共同移动簇的“结构维持”问题，借鉴[66]的研究思路，并研究其他类型的键（例如离子键和π-π相互作用）。我们注意到，结合更智能的聚类技术（如[82]中的技术），利用三元自连接来定位单个时间帧中的HB实例是一个有前景的方法，我们将在未来的工作中将其作为可能的扩展内容。从更广泛的角度来看，我们计划研究BARMCs在不同领域的适用性，例如天体物理学[16]和考虑移动性的社交网络[17]，以及各种有趣的度量方法[83]。