Multi-SANA: Comparing Topological Objective Functions for Multiple Network Alignment

All life on Earth is related, so that some molecular interactions are common across almost all living cells, with the number of common interactions increasing as we look at more closely related species. In particular, we expect the {\it protein-protein interaction} (PPI) networks of closely-related species to share high levels of similarity. This similarity may facilitate the transfer of functional knowledge between model species and human. {\it Multiple Network Alignment} is the process of uncovering the connection similarity between 3 or more networks simultaneously. Existing algorithms for multiple network alignment rely on sequence similarities to help drive the alignments, and no comprehensive study has been done to determine the most effective ways to utilize network connectivity---network topology---to drive multiple network alignment. Here we devise and empirically test the efficacy of several measures of topological similarity between three or more networks. To evolve the alignments towards optimal, we use simulated annealing as the search algorithm since it is agnostic to the objective being optimized. We test the measures both on the partially synthetic and highly similar PPI networks from the {\it Integrated Interaction Database}, as well as on real PPI networks from a recent BioGRID release.地球上所有生命均具有亲缘关联，因此几乎所有活细胞中都存在共通的分子相互作用，且亲缘关系越近的物种，其共有的相互作用数量越多。具体而言，亲缘关系相近的物种的蛋白质-蛋白质相互作用（protein-protein interaction, PPI）网络理应具备高度相似性。这种相似性可推动模式物种与人类之间的功能知识迁移。多网络比对（Multiple Network Alignment）指的是同时挖掘3个及以上网络间连接相似性的过程。现有的多网络比对算法均依赖序列相似性来引导比对过程，目前尚无全面研究来明确利用网络连通性——即网络拓扑结构——驱动多网络比对的最有效方式。本研究设计了多种适用于3个及以上网络的拓扑相似性度量方法，并通过实验验证了其有效性。为了将比对结果优化至最优状态，我们采用模拟退火算法作为搜索策略，因其不依赖于特定的优化目标。我们分别基于整合相互作用数据库（Integrated Interaction Database）中的半人工合成且高度相似的PPI网络，以及近期发布的BioGRID真实PPI网络，对上述度量方法进行了测试。