Radu Alex, Charleston Michael
1 School of Information Technologies, The University of Sydney , Sydney, Australia .
2 Centre for Mathematical Biology, The University of Sydney , Sydney, Australia .
J Comput Biol. 2015 Jul;22(7):687-97. doi: 10.1089/cmb.2014.0247. Epub 2015 Feb 19.
Due to recent advancements in high-throughput sequencing technologies, progressively more protein-protein interactions have been identified for a growing number of species. Subsequently, the protein-protein interaction networks for these species have been further refined. The increase in the quality and availability of these networks has in turn brought a demand for efficient methods to analyze such networks. The pairwise alignment of these networks has been moderately investigated, with numerous algorithms available, but there is very little progress in the field of multiple network alignment. Multiple alignment of networks from different organisms is ideal at finding abnormally conserved or disparate subnetworks. We present a fast and accurate algorithmic approach, Node Handprinting (NH), based on our previous work with Node Fingerprinting, which enables quick and accurate alignment of multiple networks. We also propose two new metrics for the analysis of multiple alignments, as the current metrics are not as sophisticated as their pairwise alignment counterparts. To assess the performance of NH, we use previously aligned datasets as well as protein interaction networks generated from the public database BioGRID. Our results indicate that NH compares favorably with current methodologies and is the only algorithm capable of performing the more complex alignments.
由于高通量测序技术的最新进展，越来越多物种的蛋白质-蛋白质相互作用被鉴定出来。随后，这些物种的蛋白质-蛋白质相互作用网络得到了进一步完善。这些网络的质量和可用性的提高反过来又带来了对分析此类网络的高效方法的需求。这些网络的成对比对已经得到了适度研究，有许多可用算法，但在多网络比对领域进展甚微。来自不同生物体的网络的多重比对非常适合发现异常保守或不同的子网。基于我们之前关于节点指纹识别的工作，我们提出了一种快速准确的算法方法——节点手印识别（NH），它能够快速准确地对多个网络进行比对。我们还提出了两个用于分析多重比对的新指标，因为当前的指标不如它们的成对比对对应指标那么完善。为了评估NH的性能，我们使用了先前比对的数据集以及从公共数据库BioGRID生成的蛋白质相互作用网络。我们的结果表明，NH与当前方法相比具有优势，并且是唯一能够执行更复杂比对的算法。
