AntNetAlign：开源蚁群优化网络对齐软件包及其性能优越性的研究

软件影响15（2023）100476原始软件出版物AntNetAlign--网络对齐软件包GuillemRodríguez Corominas a，b，Maria J. Blesa b，Christian Blum a，aArtificial Intelligence Research Institute（IIIA-CSIC），Campus of the UAB，Bellaterra，08193，SpainbUniversitat Politècnica de Catalunya（UPC-CatalonaTech），Carrer de Jordi Girona，1-3，Barcelona，08034，CataloniaA R T I C L E I N F O保留字：开源软件优化蚁群优化A B标准在本文中，我们介绍了AntNetAlign，一个开源工具（用C++编写），实现了蚁群优化（ACO）解决网络对齐（NA）问题，一个著名的硬优化问题，在不同领域的重要应用，如生物学或社交网络。 具体来说，给定两个输入网络，该工具会找到它们之间的对齐（即， 各个节点之间的映射），其优化三个主要拓扑测量中的一个。此外，它可以在其构造阶段期间利用节点之间的用户定义的成对相似性，从而允许使用更多的应用程序相关信息以提高其性能。结果表明，AntNetAlign在合理的时间内在上述三个拓扑分数中的两个方面优于其他最先进的算法，并且能够在较大实例的背景下实现有竞争力的结果（Rodríguez Corominas等人，2023年）。此外，利用负学习的算法的新版本能够进一步改善这些结果，特别是在EC评分中（Corominas等人，2022年）。代码元数据当前代码版本v1.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2023-13可再生胶囊的永久链接https://codeocean.com/capsule/6314515/tree/v1GNU通用公共许可证（GPL）使用Git/GitHub的代码版本控制系统使用C++、CPLEX的软件代码语言、工具和服务编译要求，操作环境依赖性g++≥9.4.0，CPLEX≥12.10如果可用，链接到开发人员文档/手册问题支持电子邮件guillem.rodriguez. upc.edu1. 介绍网络对齐（NA）问题需要找到两个（或多个）输入网络的节点之间的映射，以便优化某个质量度量。主要目标是将知识从一个网络转移到另一个网络（例如，从一个生物体到另一个生物体），并在链接预测[1，2]和跨网络推荐[3]中起着至关重要的作用。鉴于NA问题的广泛应用，存在许多不同的方法来解决它们。 然而，其中许多是专为特定领域和应用的问题。原文DOI：https://doi.org/10.1016/j.asoc.2022.109832。此外，虽然近年来受到极大的关注，仍然需要将不同研究领域和大量文献中出现的不同趋势统一起来。 现有的方法主要集中在要么获得一个很好的相似性得分之间的输入网络的节点，然后将它们greenly对齐，或直接优化给定的质量措施，而不考虑底层的拓扑和结构信息。为了处理发散的趋势，我们提出了AntNetAl- ign，这是一种蚁群优化（ACO）算法，它使用从输入网络中提取的相似性度量来指导在以下DOI下发表了一篇关于AnT NET ALIG n实验评估的研究论文：https://doi.org/10.1016/j.asoc.2022.109832。本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。∗ 通讯作者。电子邮件地址：guillem.rodriguez. upc.edu（G.R.Corominas），maria.j. upc.edu（M.J. Blesa），christian. iiia.csic.es（C.Blum）。https://doi.org/10.1016/j.simpa.2023.100476接收于2023年2月1日;接受于2023年2月4日2665-9638/©2023作者。由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表软件影响杂志 首页：www.journals.elsevier.com/software-impactsG.R. Corominas，M.J.Blesa和C.Blum软件影响15（2023）1004762在搜索空间的更有利的区域中的构建过程。AntNetAlign可以接受任何相似度矩阵作为输入，并且能够优化三个主要拓扑质量度量中的任何一个：边缘正确性（EC）得分[4]，诱导保守结构（ICS）得分[5]和对称子结构得分（SSS）[6]。这允许用户为更多的区域相关应用提供更好的网络信息，这可能有助于算法找到更好的解决方案，并选择更适合其目的的分数。给定两个输入网络，在每次迭代中，该算法基于所谓的信息素模型的值和从贪婪函数获得的信息概率地生成解决问题的解。在我们的例子中，贪婪函数考虑了前面提到的相似性矩阵和局部改进分数，这有助于算法根据构造的当前状态探索搜索空间的区域。在当前（或更早）迭代中生成的解用于改变信息素模型的值，这将使后续生成的解偏置，使得解的质量随时间增加。在我们的例子中，我们利用蚁群算法的一个变种，称为MAX-M in蚂蚁系统（MMAS）的超立方体框架。此外，我们提供了第二个版本的算法，所谓的AntNetAlignNL，它扩展了原来的AntNetAlign算法与负学习（NL）过程。该扩展利用了额外的优化方法（在这种情况下，线性规划（ILP））来识别除了正反馈之外还应该接收负反馈的解决方案的组件。更具体地说，在每次迭代中，通过合并在该迭代中生成的所有解决方案来创建所解决问题的子实例。然后，将该子实例建模为ILP问题，并在预定义的时间限制内使用CPLEX求解器进行求解。最后，在子实例中但不在所获得的最佳解中的解分量通过增加它们各自的负信息素值而被给予负反馈。通过这种方式，在后续迭代中，这些组件将不太可能被选中。2. 功能和主要特点该软件是用C++实现的，并在CPLEX20.04作为ILP求解器。请注意，用户必须使用他们的个人版本的CPLEX来编译软件。我们提供了两个源代码，一个是AntNetAlign（标准版本），另一个是包含额外的负学习过程（AntNetAlignNL）。还提供了一个“Makefile”来编译这两个代码。还包括一个给定两个输入网络，AntNetAlign将优化三个预定义度量中的一个用户可以提供自己的两个输入网络之间的相似性矩阵，这可能有助于在特定应用中测试新的用户定义的相似性。如果没有提供相似度矩阵，AntNetAlign将使用NETAL [7]中定义的拓扑相似度3. 影响概述该软件已在以下科学文献中进行了评价：• Guillem Rodríguez Corominas，Christian Blum，Maria J.Blesa：网络对齐的负学习蚁群优化。遗传与进化计算会议论文集（GECCO）：278-286。2022年7月。[8]doi.org/10.1145/3512290.3528795• Guillem Rodríguez Corominasa，Maria J. Blesa，ChristianBlum：AntNetAlign：网络对齐的蚁群优化。应用软计算，第132卷，2023年1月。[9]doi.org/10.1016/j.asoc.2022.109832更具体地说，我们在生物（蛋白质-蛋白质相互作用）网络、社交网络和心理（心理健康）背景下测试了AntNetAlign。AntNetAlign已被证明在合理的时间内在三个测试分数中的两个方面优于其他最先进的方法。此外，它还能够在将网络与自身对齐时实现接近最优的结果，并在较大实例的上下文中与性能最佳的方法竞争。该算法与其他最先进的竞争对手进行了测试，如MAGNA++ [10]，NETAL [7]，HubAlign [11]和L-GRAAL [12]。4. 结论和今后的工作AntNetAlign是一个使用ACO解决网络对齐问题的软件给定两个输入网络，AntNetAlign优化三个主要拓扑度量中的一个。用户还可以提供他们的个人相似性矩阵供AntNetAlign使用，使用户更容易测试他们自定义的相似性度量。此外，还提供了使用消极学习机制的附加版本。该软件是用C++编写的，易于编译和使用。在未来的工作中，我们打算将更多的拓扑措施AntNetAlign优化，甚至结合目前的措施与成对相似性得分的优化。此外，让用户指定他们自己的优化措施将是有用的竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢Guillem Rodríguez Corominas获得加泰罗尼亚政府研究和大学部的支持，通过ESF成立的加泰罗尼亚大学和研究资助机构（AGAUR，加泰罗尼亚，西班牙）的博士前资助，编号为2022 FI_B 00903。Christian Blum获得了MCIN/AEI/10.13039/501100011033资助的两项 资 助 ： AEI ， 西 班 牙 PID 2019 - 104156 GB-I 00 和 TED 2021 -129319 B-I 00。玛丽亚·J 布莱萨来 自 AEI 的 知 识 支 持 ， 西 班 牙 在 授 予 PID-2020- 112581 GB- C21（MOTION）和加泰罗尼亚大学和研究补助金管理机构（AGAUR，加泰罗尼亚，西班牙），在授予2021- SGR-01419（ALBCOM）。引用[1]M.A. 艾 哈 迈 德 ， Z 。 Borbora ， J. Srivastava ， N. Contractor ， Link predictionacrossmultiple 社 交 网 络 ， 在 ： 2010 IEEE International Conference on DataMiningWorkshops，IEEE，2010，pp. 911-918[2] Y. Dong，J. Tang，S. Wu，J.Tian，N.V. Chawla，J.Rao，H. Cao，Link预测和跨异构社交网络的推荐，在：2012年IEEE第12届数据挖掘国际会议，IEEE，2012年，pp. 181-190.[3] L. Hu，J. Cao，G. 许湖，加-地 曹，Z. 古角，澳-地 Zhu，个性化推荐通过跨域三元因子分解，在：第22届万维网国际会议论文集，ACM出版社，2013年，pp. 595-606.[4] O.库恰耶夫Milenković，V. Memišević，W. Hayes，N. Pržulj，拓扑网络对齐揭示了生物功能和遗传学，J.R. Soc. Interface 7（50）（2010）1341-1354.[5]R. 帕特罗， C. 金斯福德 全球 网络 对准 使用 多尺度谱signatures，Bioinformatics 28（23）（2012）3105[6]V.Saraph ， T.Milenković ， MAGNA ： Maximizingaccuracyinglobalnetworkalignment，Bioinformatics 30（20）（2014）2931-2940.[7]B. Neyshabur，A. Khadem，S. Hashemifar，S.S. Arab，NETAL：一种新的基于图的蛋 白质相 互作用 网络全局对齐方法 ，Bioinformatics29（13）（2013）1654[8] G.R. 科 罗 米 纳 斯 角 Blum ， M.J. Blesa ， Negative learning ant colonyoptimizationfor network alignment，in：J.E.菲尔德森，M.瓦格纳（编），GECCO'22：遗传和进化计算会议，美国马萨诸塞州波士顿，7月9日- 13，2022，ACM，2022，pp. 278-286。G.R. Corominas，M.J.Blesa和C.Blum软件影响15（2023）1004763[9]G. Rodríguez Corominas，M.J. Blesa，C. Blum，AntNetAlign：蚁群优化网络对齐，应用。软计算132（2023）109832.[10] V. Vijayan，V. Saraph，T. Milenković，MAGNA++：通过节点和边缘保护最大化全球网络对齐的准确性，生物信息学31（14）（2015）2409-2411。[11] S. Hashemifar ， J. Xu ， HubAlign ： an accurate and efficient method forglobalalignment ofprotein-protein interaction networks ， Bioinformatics 30（17）（2014）438-444.[12] N.Malod-Dognin ， N.Pržulj ， L-GRAAL ： Lagrangiangraphlet-basednetworkaligner，Bioinformatics 31（13）（2015）2182-2189.