用于随机化加权网络的模拟退火算法

连接组学的科学发现依赖于网络零模型。通常，根据使用随机网络估计的空分布来评估网络要素的突出性。现代成像技术提供了越来越丰富的具有生物学意义的边缘权重。尽管加权图分析在连接组学中很普遍，但仅保留二元节点度数的随机化模型仍然使用最广泛。在这里，我们提出了一个模拟退火程序，用于生成保留加权度（强度）序列的随机化网络。我们表明，该过程优于其他重新布线算法，并推广到多种网络格式，包括有向网络和签名网络，以及各种现实世界的网络。在整个过程中，我们使用形态空间表示来评估算法的采样行为和结果融合的可变性。最后，我们表明准确的强度保持会产生关于大脑网络组织的不同推论。总的来说，这项工作提供了一种简单而强大的方法来分析细节丰富的下一代连接组学数据集。

其他人正在查看类似内容

网络神经科学中的空模型

报道 2022-5-31

DotMotif：用于连接组子图同构搜索和图形查询的开源工具

文章 开放获取 22 六月 2021

迈向生物注释的大脑连接组

报道 2023-10-17

主要

连接组是一个复杂的网络，它构成了大脑神经元件及其连接的综合目录1.已经确定了结构脑网络的许多拓扑特征，包括高聚类、短特征路径长度2,3,4,5,6以及一个由高度互连的枢纽节点组成的丰富俱乐部7、8、9、10.这些网络特征在物种之间一致地表达11、空间尺度、神经影像学模式和区域追踪技术12.

为了量化大脑网络特征的意外性，通常将基于网络的统计数据与在保留经验网络特定属性的随机网络总体中计算的零特征进行比较13.然后，与随机网络的比较可用于统计推断或基准测试。在统计推断的情况下，可以通过计算该特征具有比经验网络更极端的随机网络的比例来估计特定网络特征的 P 值。在基准测试的情况下，可以根据该特征在随机网络总体中的分布对网络特征进行标准化。例如，经常研究的小世界系数2、14、15和 Rich-Club 系数16,17 元根据定义，以这种方式进行规范化。应用最广泛的网络零模型是度数保持重连线（通常称为 Maslov-Sneppen 重连线18），它使用边交换来破坏经验网络的拓扑，但保留其大小（即节点数）、密度（即表达边的比例）和二进制度数序列（即入射到每个节点的边数）。重要的是，通过选择性地控制低阶特征，可以使用零模型来排除高阶结构反映简单特征的随机装配的可能性13.

然而，随着富加权网络的出现——跨越多达六个数量级的权重量级19,20,21 元— 以及它们越来越多地使用于更简单的二进制对应项，因此需要容纳加权网络统计数据的 Null 模型。例如，在弥散加权磁共振成像 （MRI） 牵引力测定法中，边缘权重通常使用流线数量或分数各向异性来估计22.最近，已经开发了许多指标来更直接地量化网络边缘的微观结构属性23，包括神经突密度24髓 鞘25,26,27 元、轴突直径28,29 元和轴突横截面积30,31 元.动物模型中的侵入性方法也会产生加权网络，包括使用荧光标记物的区域追踪32、33、34 元、 遗传标记35和电子显微镜36,37 元.此外，通过比较区域间相似性，大脑网络越来越多地被重建38,39 元，例如基因共表达40,41 元、层状轮廓协方差42或受体相似性43，再次产生具有生物学意义的边缘权重分布。因此，下一代连接组学需要考虑边缘权重的新随机化算法。

已经开发了几种网络零模型，除了它们的二进制度数序列外，还保留了经验网络的加权度数序列（以下简称强度序列）票价：17,44,45,46,47,48,49,50 元.这些模型中的大多数是基于网络概率分布的最大似然估计的抽样方法44、45、51.在这里，我们不考虑这些模型，原因有两个。首先，它们只满足整个网络集合的平均度数序列约束，而不满足每个单独的采样网络52,53 元.其次，这些模型没有保持经验网络的权重分布53.此外，由于这些原因，它们很少实际用于网络神经科学。

在这里，我们提出了一种算法，通过为每个随机网络实例保留经验网络的权重分布、度数序列和强度序列来解决这些限制。与其他强度守恒模型相反，该程序不需要任何分析推导，而是建立在网络神经科学和更普遍的网络科学领域已经很常见的经典重新布线技术之上。这种随机化技术使用模拟退火（一种近似给定函数的全局最小值的概率算法）重新配置重新布线网络的二进制脚手架上的权重放置，以匹配经验网络的强度序列54,55 元.模拟退火是一种功能强大且用途广泛的优化技术。此外，它在处理大型组合搜索空间时特别有利，使其成为解决网络建模问题的主要候选者6,52,53,56,57,58,59,60,61,62,63,64.

在这项研究中，我们将模拟退火程序的性能与另一种用于强度序列保留随机化的重新布线算法（以下简称 Rubinov-Sporns 算法）进行了基准测试65）以及经典的 Maslov-Sneppen 守度重连模型18.同时，我们使用形态空间表示来评估零网络变异性，这是一个很少被考虑的46,61,66,67,68但在比较网络 NULL 模型时，重要的评估步骤。

结果

模型概述

简而言之，我们考虑三种重新布线算法（图 D）。1;有关详细说明，请参阅 Methods ）。在经典的 Maslov-Sneppen 算法中，边对随机交换，权重与各自的边一起“携带”18（图 .Rubinov-Sporns 算法建立在 Maslov-Sneppen 算法的输出之上，试图通过使用等级匹配程序以伪随机顺序从原始边缘权重分布中对每个边缘权重进行采样来保留强度序列65（图 .最后，在模拟退火过程中，同样基于 Maslov-Sneppen 算法的输出，如果随机选择的边权重对降低系统的能量（经验和随机网络的强度序列之间的均方误差）或满足概率接受标准，则随机选择的边权重对将被置换。这允许排列，这可以增加系统的能量，但防止它卡在局部最小值（图 D）。重要的是，该程序也适用于 Maslov-Sneppen rewired 网络。

图 1： 用于生成强度序列保留随机零网络的重新连接算法。

图 1

a， Maslov-Sneppen 保度重连18.成对的边（红色）被随机交换，破坏了网络的拓扑结构，但保留了其大小、密度和度数顺序。Edge width 表示权重，node size 表示强度。b， Rubinov-Sporns 强度序列保留随机化算法65.使用 Maslov-Sneppen rewired 网络：（1） 随机网络用零 （\（{\hat{A}}_{ij}=0\）， black） 实例化，（2） 原始边权重 （A我J）按幅度排序（左），（3） 随机网络的边缘按其预期幅度排序（\（{\hat{e}}_{ij}\），中），（4） 在随机网络中选择一个随机边，其权重设置为相同等级的原始边权重（两条边都用红色表示），以及 （5） 边重新排序， 并重复该过程，导致 Maslov-Sneppen 重新连接网络，边权重排列以近似经验网络的强度序列（右）。\（{\hat{e}}_{ij}\propto （{s}_{i}-{\Sigma }_{u}{\hat{A}}_{iu}）（{s}_{j}-{\Sigma }_{u}{\hat{A}}_{ju}）\），其中 s我表示经验网络中节点 i 的强度，\（{\Sigma }_{u}{\hat{A}}_{iu}\） 是随机网络中入射到节点 i 的已分配边的权重之和。在中间网络中，边宽表示预期的权重大小（黑色或红色）或分配的权重（蓝绿色），节点大小表示残余强度（\（{s}_{i}-{\Sigma }_{u}{\hat{A}}_{iu}\））。c，通过模拟退火实现强度序列保留随机化。使用 Maslov-Sneppen rewired 网络，如果随机选择的边权重对（红色）降低了系统的能量（经验网络和随机网络的强度序列之间的均方误差 （m.s.e.）），或者如果它们满足概率 Metropolis 验收标准，则根据系统的温度 （T） 进行排列。

全尺寸图像

实验在两个公开可用的弥散加权 MRI 数据集中进行，使用不同的协议（扩散光谱成像 （DSI） 和高角度分辨率扩散成像）、包裹分辨率（解剖学和功能）和包裹分辨率（每个数据集中的低和高）获得。第一个样本 （LAU） 包含在 n = 70 名参与者（洛桑大学医院69;有关详细过程，请参阅方法）。第二个样本包括在 n = 327 名参与者（人类连接组项目 （HCP）70，请参阅方法了解详细过程）。对于这两个数据集，使用基于距离的共识阈值程序构建了具有组代表性的加权结构网络71,72 元，导致总共四个经验组一致网络（LAU，低分辨率;LAU，高分辨率;HCP，低分辨率;HCP，高分辨率），并在其基础上进行主要分析（参见'单个网络中保持强度随机化'一节，了解单个参与者连接组的分析）。在这里，结果在高分辨率 HCP 数据集中可视化，但详尽的数字作为补充信息提供（补充图7、8、10、12 和 14）。

基准强度序列保留

我们通过为每个经验大脑网络生成 10,000 个空网络来对随机化算法的性能进行基准测试。为了描述零模型在保持强度序列（每个节点与特定强度相关联的有序强度集）下的性能，我们绘制了所有 10,000 个零值的经验网络强度与随机网络强度的关系（图 D）。2a 和补充图7）. 我们还计算了经验强度和“随机”强度之间的 Spearman 秩序相关系数。在所有四个经验大脑网络中，模拟退火算法产生近乎完美的拟合（LAU，低分辨率：平均值 = 0.999，标准差 = 0.001;LAU，高分辨率：平均值 = 0.996，标准差 = 0.002;HCP，低分辨率：平均值≈ 1.0，标准差 = 3.04 × 10−7;HCP，高分辨率：平均值≈ 1.0，标准差 = 1.37 × 10−7).它还导致比 Rubinov-Sporns 算法更大的相关系数（P ≈ 0，所有经验网络的通用语言效应量 （CLES） 为 100%，双尾，Wilcoxon-Mann-Whitney 双样本秩和检验），这本身导致比 Maslov-Sneppen 算法更大的系数（P ≈ 0，所有经验网络的 CLES 为 100%，双尾，Wilcoxon-Mann-Whitney 双样本秩和检验）。这表明模拟退火算法生成了具有最真实强度序列的随机网络。在补充信息中，我们进一步研究了零模型校准（“零模型校准”部分），并提供了敏感性分析，检查了替代目标函数（“替代目标函数”部分）、退火计划（“替代退火计划”部分）和权重对数变换对模拟退火性能的影响（“对数变换”部分）。我们还对模型的计算成本进行了深入分析，描述了它与性能的权衡以及随网络密度和大小的扩展（“计算成本”部