软件X 14（2021）100676原始软件出版物CycFlowDec：使用简单循环Austen Bernardi，Jessica M.J. Swanson犹他大学化学系，1400 E，盐湖城，UT，84112，美国ar t i cl e i nf o文章历史记录：收到2020年2021年2月4日收到修订版，2021年保留字：CycFlowDec循环流分解动力学网络动力学建模a b st ra ct本文提出了一种确定封闭网络中通过简单环的期望流的新算法。目前的网络分析软件没有实现预期的循环流分解的算法，尽管它的潜在价值。将网络分解为预期的循环流提供了网络循环的定量表征，可以进一步分析其敏感性和相关行为。一个高效的通用算法已经被编码到CycFlowDec中，CycFlowDec是一个开源的Python模块，可以在https://github.com/austenb28/CycFlowDec上找到。版权所有2021作者。由爱思唯尔公司出版这是CC BY-NC-ND下的开放获取文章许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。代码元数据当前代码版本v1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-20-00084Code Ocean compute capsule N/A法律代码许可证GPL 3.0使用Git的代码版本控制系统使用Python 3的软件代码语言、工具和服务编译要求，操作环境依赖性Python 3，NumPy如果可用，链接到开发人员文档/手册https://github.com/austenb28/CycFlowDec问题支持电子邮件a. utah.edu1. 动机和意义网络分析是一种涉及所有科学领域的实践，从生物学[1]到计算机科学[2]，再到交通流[3]。对于一些分析，一个中心目标是描述网络中某些循环的预期流[1，4，5]。然而，量化通过复杂网络的路径的相对概率通常是不平凡的。已经开发了许多图论算法来表征网络流[6-这些方法通常量化最大流或最小成本路径。然而，在确定复杂网络的期望流分解方面进展有限以往关于预期周期流量的*通讯作者。电子邮件地址：j.swanson@ utah.edu（Jessica M.J. Swanson）。https://doi.org/10.1016/j.softx.2021.100676在很大程度上是理论性的[16，17]，并且专注于对相关系统属性（如熵产生率[18]）或特定网络类型（如量子马尔可夫半群[19]）的数学描述进行去模糊化。这项工作的主要动机涉及在动力学马尔可夫状态模型的相关离子传输途径的分析 [1，20，21]这是一种Cl−/H+反向转运蛋白，对预期的简单循环流的研究是必要的。这些周期可以进一步研究，以确定它们对特定跃迁的敏感性，揭示子系综性质，并为机械洞察开辟新的途径。除了这个特定的应用程序，Python模块CycFlowDec，在这项工作中描述，已被设计为分解一个给定的流网络到 预期的简 单循环流 。任何 化学反应 网络都可 以使用CycFlowDec进行分析，以定量确定相关反应循环的预期流量。这一特性对于分析催化领域的网络特别有价值，例如酶网络或多相催化的研究。精确2352-7110/©2021作者。由爱思唯尔公司出版。这是一篇开放获取的文章，使用CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006762C⎝∑⎞）∑N→∞cFig. 1. 三节点流网络N3.对反应网络中的预期循环流的了解为规定反应网络的功能性的基础机制的重要性提供了定量度量以类似的方式，CycFlowDec可以应用于任何涉及流网络的应用的例如，可以使用CycFlowDec来确定通信网络[22]、交通网络[23]、迁移网络[24]或货币网络[25]中的预期循环流2. 理论背景本文提出了将闭流网络分解成简单回路的新算法。请注意，一个简单的循环是任何节点最多包含一个实例的循环因此，在本发明中，表1基于行走的简单循环提取例子.W上的当前节点以粗体显示W访问抽取循环{A，B，A，C，B，A，B，C，B，C，A}{A}{A，B，A，C，B，A，B，C，B，C，A}{A，B}{A，C，B，A，B，C，B，C，A}{A}（A，B）{A，C，B，A，B，C，B，C，A}{A，C}{A，C，B，A，B，C，B，C，A}{A，C，B}{A，B，C，B，C，A}{A}（A，C，B）{A，B，C，B，C，A}{A，B}{A，B，C，B，C，A}{A，B，C}{A，B，C，A}{A，B}（B，C）{A，B，C，A}{A，B，C}{A}{A}（A，B，C）使用通过马尔可夫转移概率生成的随机游走在网络N上执行，我们可以定义发散极限[27]limwN=wcC∈C，（ 1）其中N是行走的长度，C是N上所有简单循环的集合，并且wN是长度为N的行走上提取的循环c的数量。当量（1）代表了本工作中描述的所有算法的主要基础。循环的期望概率pc由[27]期望简单循环流分解将期望流分配给网络中的所有简单循环，使得当循环流被加在一起时恢复原始流网络。算法的数学框架pc= wcn∈C−1wjc ∈ C。（二）本文提出的算法是基于[26]，并在参考文献[27]的第3章中进行了扩展。本节概述了以前开发的 框架，而附录描述了新开发的算法。重要的是，pc是有限的，并且无论行走的起始节点如何，都取相同的值。循环c的预期流量，给定为fc，可以计算为：最有效的通用算法已在CycFlowDec Python模块中实现，可在https：//github上获得。com/CycFlowDec，包含示例和附加文档-fc= wc（<$∑k∈Cnkwk−1j∈EeJC∈C，（3）论证。虽然所提出的算法被设计为将封闭流网络分解为简单的循环流，但是通过将开放网络转换为有效的封闭网络，该框架可以直接扩展到开放网络。这是通过包括一个附加的虚拟节点来实现的，该虚拟节点将网络接收器连接到源。附录A中依次列出了四种算法，最后是最快的算法，该算法已纳入Cy- cFlowDec中。我们首先简要概述基本理论[26，27]。 考虑图3中的三节点流网络N3。1.一、设N3上的一个典型循环游动W为W={A，B，A，C，B，A，B，C，B，C，A}。[27]可以用下面的步骤将WalkW分解成简单的循环1. 从W的第一个节点开始。标记为已访问。2. 走到下一个节点。3. 如果当前节点已标记为已访问，则提取从其先前访问到前一个节点的所有节点。记录由提取的节点组成的循环。将提取的节点标记为除当前节点外未访问。否则，将当前节点标记为已访问。4. 重复2和3，直到行走结束请注意，简单循环是包含任何节点的不超过一个实例表1示出了使用所描述的过程的W的分解通过q个节点 n1，n2 ， . ， nn的循环。. . ，n q，. . . 表示为（n1，n2，. . . ，n q）。使用此程序提取循环有几个好处。如果过程其中E是N上所有边的集合，ej是边j的流，并且nk是循环k中的边的数量。合并等式（2）和（3）证明了fc也是有限的，并且取相同的值而不依赖于游动的起始结点.当量（3）是CycFlowDec中用于计算循环流量的公式。3. 软件描述CycFlowDec是一个开源的Python模块，可以实现封闭网络的预期简单循环流分解。流分解是通过使用附录A.4中描述的老化和最小贡献容差来完成的，从而在复杂网络上实现快速高效的性能1.软件构架CycFlowDec完全包含在一个紧凑的Python 3脚本中，需要NumPy 作 为 其 唯 一 的 外 部 库 。 面 向 对 象 的 结 构 使 用CycFlowDec主类，采用各种方法进行分解和分析。还使用了一个辅助Walk类，它可以有效跟踪算法中的重复行走CycFlowDec的架构图见图1。二、类和方法的详细描述以及示例可以在https：//github.com/austenb28/CycFlowDec网站。奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006763==−∑1<$ej−∑fk<$，（4）⏐⏐图二. CycFlowDec架构图。面向一般用户的类和方法显示为绿色。(For对本图图例中所指颜色的解释，读者可参考本文的网络版表2通过算法循环N3的流量对于随机和非随机，N=2×105，N=300，适用于老化的灭菌。循环随机渗流渗流，燃烧=N−2（A、B）36.9002936.7742436.77419（A、C）2.742822.774202.77419（B、C）1.782291.774181.77419（A、B、C）3.182063.225793.22581（A、C、B）1.201011.225801.225814. 说明性实例1.算法性能为了评估附录A中描述的循环流分解算法的性能，计算了来自循环的重构流网络的边缘与原始流网络的边缘之间的平均相对误差（MRE）。也就是说，图三. Log–log plot of MRE vs. algorithm steps for the stochastic, percolating, 随机指标和预测指标的趋势线形式为y=ax−b，而预测指标和预烧指标的趋势线形式为y=ae−bx。见图4。 七节点流网络N7.MRE1NEeJj∈E<$k∈Cj ⏐网络N7和N64在图1A和1B中示出。分别为4和5其中NE是N中的边数，Cj是包含边j的简单圈的集合。图图3示出了针对图3中指定的三节点网络N 3的前三个所描述的算法的MRE与步骤。1.一、烧成用的碳化钨N2，其中N是步骤的总数。附录B中讨论了烧伤选择的优化。N3网络足够小，可以使用零的最小贡献容差. 老化算法的迭代速度明显快于随机算法和迭代算法，表现出几何收敛而不是代数收敛。CycFlowDec采用老化和最小贡献容差算法，允许闭合网络的快速循环流分解。N3循环流分解为先前描述的算法报告在表2中。所有三种算法都出现在它们会收敛到相同的分解，这与它们基于相同的基本理论这一事实相一致。与图中的最终数据点一致。3.随机确定的周期流与高精度算法至少一致一位数，而预烧周期流与预烧周期流至少一致四位数。2.附加网络由于N3是一个小型网络，因此七节点网络N7和还使用64节点网络N64来验证CycFlowDec。网络N64表示Cl−/H+的马尔可夫状态模型反转运蛋白[1，20，21]，这在很大程度上推动了这项工作。网络的MRE收敛如图所示。六、直觉上，N64比其他网络需要更多的步骤来收敛;然而，N7实际上比N3收敛得更快。这意味着除了网络中的节点和边的数量之外，还有另一个影响收敛的因素这第三个因素很可能与网络的相对流量平衡有关：具有相似幅度的边缘流的网络网络N3的边缘流相差10倍，而N7的边缘流都是O（1）。网络N64具有相差超过103的边缘流。算法的收敛速度可能是一个复杂的函数的节点和边缘的数量，5. 影响CycFlowDec将封闭流网络分解为预期的简单循环流。据我们所知，没有其他网络分析工具被设计来完成这项任务。该工具具有广泛的潜在用途，因为在涉及流网络的任何科学领域中，循环流在封闭流网络中具有潜在的重要作用，例如化学反应网络，通信网络等[1，4，5，22确定奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006764图五、6 4 节点流网络N64. 使用igraph [10]使用大图布局算法生成边表示双向流。流网络中的预期循环流产生构成网络功能的基础循环的重要性的直接度量。这些信息对于定量确定决定功能性生物学的基本机制特别有价值网络中的路由器。示例网络N64代表Cl−/H+反向转运蛋白的酶促离子转运网络，其可以直接用CycFlowDec进行分析[1，20，21]。今后工作将扩大这一分析，包括评估的cy-对特定跃迁的敏感性，以及在复杂生物系统中获得机械洞察力的适用性。CycFlowDec是一个在GNU通用公共许可证下发布的开源Python模块。这种透明度确保了所有相关方的直接访问，并允许进一步修改CycFlowDec。此外，轻量级的设计和简单的Python界面可以直接纳入一般的研究项目和计划。简单的Python模块格式非常适合CycFlowDec，因为它具有广泛的网络分析适用性CycFlowDec是为将封闭流网络分解为简单的循环流而设计的，但它也可以应用于开放网络的分析，无需内部修改。这可以通过为开放网络定义有效的封闭流网络来实现，其中源节点连接到开放网络。汇聚节点经由中间虚拟节点。使用CycFlowDec对有效闭合网络进行分解，将产生简单的循环流，其中一些循环流包括虚拟节点。包含虚拟节点的简单循环表示瞬态路径流，其中瞬态路径通过移除虚拟节点来给出。CycFlowDec在开放流网络中的这种额外应用进一步增加了适用范围。例如，CycFlowDec仅适用于涉及由N64表示的Cl−/H+反向转运蛋白的稳态网络，而中间瞬态网络可以使用前面提到的开放网络分析进行分析。6. 结论本文提出了一种新的确定封闭网络循环流分解的有效算法。该算法被合并到开源Python模块CycFlowDec中。虽然CycFlowDec是为封闭网络设计的，但它通过定义一个类似的有效封闭网络而适用于开放网络，其中源和汇流被发送到虚拟节点。CycFlowDec可以更全面地分析循环流网络，这在许多科学领域都存在奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006765−−===≤−[ ]+=⎝∑[03 8/436/9]⎞=其中V是N上所有节点的集合，ej，k是从节点j到节点k的边流，并且Ej是从节点j发出的所有边的集合。对于图中的N3， 一、M40/4403/9。4/ 44 5/ 43 0当量（A.1）用于计算本工作中所有算法的M堆栈数据结构适用于存储遍历，因为循环总是从遍历的末尾提取。Roll（0， 1）在0和1之间滚动一个随机的均匀实数，用于随机选择M遍历中的下一个节点。堆栈方法pop_cycle（k）根据前面定义的过程提取并返回从节点k开始遇到的循环。由循环c键控的所得到的循环计数wc存储在散列表C中，其可以用于利用等式（1）计算循环流。（三）、见图6。使用老化算法的N 3、N 7和N 64的MRE与步骤的对数-对数图。趋势线的形式为yae-bx。N 3和N7的老化和最小贡献容限分别为N2和零。网络N64使用N 4和10−7。N 3、N 7的起始节点分别为A、G和51， 第64话分别竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢作者感谢Heather Mayes博士、Sangun Lee博士、Zhi Yue博士和Vadhana Varadarajan博士的激励性研究，并感谢Andrew Ralph在测试中的协助。作者还感谢Dionisios Vlachos博士和Udit Gupta博士 进 行 了 富 有 洞 察 力 的 讨 论 。这 项 工 作 的 部 分 资 金 来 自CHEETAH 中心颁发的合作发展奖美国犹他大学（NIH P50AI150464）。犹他大学高性能计算中心的支持和资源也得到了感谢。附录A. 算法CycFlowDec Python模块基于已建立的马尔可夫循环理论[26，27]实现了一个有效该算法是一个产品的三个顺序修改的简单算法，首先描述。A.1. 随机算法所描述的第一个算法直接从基础理论中获得。算法1中提供了伪代码。左随机矩阵M计算如下：算法一： 随机循环流分解生成随机矩阵M初始化一个空栈S初始化一个空哈希表C在S对于j1到N，rRoll（0，1）对于行（M）中的k，如果M[k，S[end]]r，则如果结束，则结束如果 k在S中，则c=S.pop_cycle（k）Cc 1其他S.push（k）end if端A.2. 逾渗算法该算法将随机算法扩展到从起始点出发的无限次行走的极限。从这个意义上说，无限次行走从起始节点开始确定性地渗透网络，并且在遇到循环时提取和计数循环。算法2中提供了伪代码，用于变量burn和tol（分别在附录A.3和A.4中定义）被初始化为零的情况。代替显式地计数简单循环的出现次数，每个循环相对于所有循环的分数贡献是：walk用于wwc。例如，如果在给定的迭代中有3%的遍历经过循环c，则wc递增0.03。两个哈希表H1和H1的关键字是遍历堆栈，渗透步骤和进步的步行。循环算法利用循环提取后将相同堆栈的行走合并的能力，允许跟踪无限循环行走而不会出现组合爆炸。类似于随机算法，所得到的循环贡献w。。被存储在哈希表C中，并且可以用于利用等式（1）计算循环（三）、随后描述的两种算法都以相同的方式产生CA.3. 使用老化算法M[k，j]=ej，kl∈Ej−1埃勒河k∈V，（A.1）在较早的迭代中，迭代算法受到初始化偏差的影响，因为行走完全过滤和平衡需要时间。一个简单的想法来缓解这一点奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006766−===B1−[ ]=[]个字符[]−=QS+=[ ]=[]个字符[ ]=[]个字符[ ]+== −[ ]+=图B.7. N3、N7和N64的MRE与老化步骤的半对数图。对于三个、七个和64个节点的网络，总步长分别固定为150、50图B.8. M R E 与对于类似于N3的网络的老化步骤，未被重命名的贡献将被折叠回原始步中。算法2：使用老化和最小贡献容限算法的渗滤循环流分解生成随机矩阵M初始化空哈希表H1初始化空哈希表H1初始化空哈希表C初始化包含起始节点的堆栈SH−1[S] =1对于j1到N，for S in Hb.keys（）do HbS 0端在H中的Sb.keys（）dor10 的对于行（M）中的k，F =H−b[S]<$M[k，S[end]]如果HbS>tol或kin S则如果j>burn且kin S则c=Q.pop_cycle（k）C[c] +=f−⇀−⇀−⇀−⇀−⇀−⇀其中AB=BC=CA=40，AC=CB=BA=1。 总步骤固定为问题是避免对初始迭代的一些数目燃烧的循环进行计数。对于变量tol被初始化为零的情况，在算法2A.4. 具有老化和最小贡献容差对于高度连通的大型网络，由于收敛速度随可行简单圈数线性下降，因此该算法将遭受组合爆炸。以最大可实现的准确度为代价，可以通过仅增加对超过分数容差tol的总行走次数有贡献的新行走堆栈来缓解该问题。 该修改在算法2中示出。贡献低于tol但不产生新的遍历堆栈的遍历仍然会被删除，因为它们不会增加遍历堆栈的总数。其他Q.push（k）end if如果Q在Hb.keys（）中，则HbQf其他HbQf结束，如果否则R f如果结束，则结束如果S in Hb.keys（），则HbSr其他HbSrend ifend forb1端500.奥斯汀·贝尔纳迪和杰西卡·M·J·斯旺森软件X 14（2021）1006767=−- -+图C.9. N64不同最小贡献容差的MRE与步长的半对数图。低于0.1的边缘流从MRE计算中省略附录B. 老化选择老化是算法效率的关键组成部分，如图所示。3 .第三章。为了研究老化选择的影响，对所有三个验证网络的相同总步骤测试了不同的老化，如图所示。B.7.从这些数据中产生了一个有趣的模式：所有三个网络都显示出偶数和奇数老化步骤的双重行为。在进一步测试时，行为实际上取决于循环记录步骤log N burn的数量是偶数还是奇数。具体地说，偶数对数阶跃通常表现出下降的、较低的MRE，而奇数对数阶跃表现出较高的MRE，对数接近零时向上。网络N7显示偶数和奇数对数步长之间的差异最小，可能是因为它包含最平衡的边缘流。N 2的老化比NN64可能是4 因为N64需要非零的最小贡献容限来加速其计算。碰巧的是，N3、N7和N64都有主导气流长度为2的周期为了测试老化行为是否对此敏感，测试了与N3结果见图 B.8. 老化行为似乎对主导流动周期长度敏感，因为在长度为三个周期的主导网络中观察到三元老化行为。对于计算效率是限制因素的复杂网络，应测试老化行为，因为在没有循环流的先验知识的情况下，老化的简单、通用选择是显而易见的。附录C. 最小贡献容差选择对于N64，需要最小贡献容差tol以允许易处理的计算时间。给出了N64的循环流网络关于tol图C.9.对于tol的所有值，MRE呈指数下降，直到达到某个步数，然后趋于平稳。此行为与以下概念一致：并入最小贡献容差会降低循环流分解的最大可实现精度。可获得较低的MRE以增加计算费用为代价使用较低的容差。引用[1]Mayes HB，Lee S，White AD，Voth GA，Swanson JM.多尺度动力学模型揭示 了 ClC-ec 1 反 向 转 运 蛋 白 中 Cl-/H+ 交 换 途 径 的 集 合 。 J Am ChemSoc2018;140（5）：1793-804。[2]作者：RawatW，Wang Z.用于图像分类的深度卷积神经网络一是全面审查。神经计算2017;29（9）：2352[3]杨燕，张S，唐军，王晓.从复杂网络结构理解多变量交通流时间序列的特征.Physica A2017;477：149-60.[4]ManikD，蒂默 M、维托 D. 周期 流动 和多稳态振荡网络 混沌2017;27（8）：083123。[5]王G，杜春，陈华，辛哈R，荣Y，肖Y，曾春。基于过程的网络分解揭示了主干基序结构。Proc Natl AcadSci2010;107（23）：10478-83.[6]作者：DantzigG.关于网络的最大流最小割定理线性 不相等Relat Syst2003;38：225-31.[7]弗龙切克湾完全图到生成树的循环分解。讨论数学图论2004;24（2）：345-53.[8]罗莎A. 关于完全图的（4m）循环分解 2）-β-淀粉样蛋白。Mat-fyz Časopis1966;16（4）：349[9]伍德豪斯FG，Forrow A，Fawcett JB，Dunkel J.随机周期选择在流动的网络中。Proc Natl Acad Sci2016;113（29）：8200-5.[10]张文，张文，等.复杂网络research. 国际复杂系统杂志2006;1695（5）：1[11]作 者 ： J. P. WGCNA ： 一 个 用 于 加 权 相 关 网 络 分 析 的 R 软 件 包 。 BMCBioinformatics2008;9（1）：559.[12]HandcockMS， Hunter DR， Butts CT， Goodreau SM ， Morris M.国 家信 息网：用于网络数据表示、可视化、分析和模拟的软件工具。统计软件杂志2008;24（1）：1548.[13]DeNooy W，Mrvar A，Batagelj V.探索性社会网络分析与pajek：更新软件的修订和扩展版，第46卷。剑桥大学出版社;2018.[14]ThomasS，Bonchev D.当前网络分析软件综述在分子生物学中。 Genom2010;4（5）：353.[15]Hoops S，Sahle S，计R，李C、对帕勒J，SimusN、SinghalM、徐L，Mendes P，Kummer U. COPASI-一个复杂的通路模拟器。生物信息学2006;22（24）：3067-74.[16]BanischR，Conrad ND.基于循环流递归网络《欧洲物理快报》2015;108（6）：68008。[17]杨伟，王伟，王伟. 复杂网络上随机游动的反应流和非生产环。Eur Phys JSpec Top2015;224（12）：2369-87。[18]贾春，姜德强，钱民平，等.循环对称性与循环离散时间和连续时间马尔可夫链的波动。 AnnAppl Probab2016;26（4）：2454-93.[19]FagnolaF，Umanita V.一般量子马尔可夫半群，循环decom-位置和偏离平衡。因芬迪门斯Anal.量子概率相对Top. 2012;15（03）：1250016.[20]Lee S，Swanson JM，Voth GA. 多尺度模拟揭示了ClC-ec 1反向转运蛋白的质子转运机制。Biophys J2016;110（6）：1334-45。[21]LeeS，Mayes HB，Swanson JM，Voth GA.偶联氯的起源Cl-/H+反向转运蛋白中的Ride和质子转运。J Am Chem Soc2016;138（45）：14923-30.[22][10]杨文，杨文.危机-社交媒体时代的沟通：Zika相关推文的网络分析。Soc Sci Comput Rev2018;36（5）：523-41。[23]丁R，Ujang N，bin Hamid H，Abd Manan MS，He Y，Li R，Wu J.检测通过对多层网络的生长和分析，研究城市交通网络结构的动态变化。PhysicaA2018;503：800-17.[24]MyersOM，Reyier E，Ahr B，Cook GS.条纹鲻鱼的迁徙模式印度河泻湖：空间渔业管理的网络分析方法。海岸三月鱼. 2020;12（6）：423-40.[25]IosifidisG，沙雷特是的，AiroldiEM，利特拉G，塔休拉什我，克里斯-takis NA。Sardex货币网络中的循环图案。Nat Behav2018;2（11）：822-9。[26]民平Q，MinQ.循环为复发性马尔可夫店Z.Wahrscheinlichkeitstheor. 韦尔万特山1982;59（2）：203-10.[27]Kalpazidou SL.马尔可夫过程的循环表示，第28卷。SpringerScience&Business Media;2007.
我的内容管理
展开
