Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Department of Computer Science, Brown University, RI 02912, ECK Institute for Global Health, University of Notre Dame, IN 46556 and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame, IN 46556, USA Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Department of Computer Science, Brown University, RI 02912, ECK Institute for Global Health, University of Notre Dame, IN 46556 and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame, IN 46556, USA.
Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Department of Computer Science, Brown University, RI 02912, ECK Institute for Global Health, University of Notre Dame, IN 46556 and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame, IN 46556, USA Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Department of Computer Science, Brown University, RI 02912, ECK Institute for Global Health, University of Notre Dame, IN 46556 and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame, IN 46556, USA Department of Computer Science and Engineering, University of Notre Dame, IN 46556, Department of Computer Science, Brown University, RI 02912, ECK Institute for Global Health, University of Notre Dame, IN 46556 and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame, IN 46556, USA.
Bioinformatics. 2014 Oct 15;30(20):2931-40. doi: 10.1093/bioinformatics/btu409. Epub 2014 Jul 10.
Biological network alignment aims to identify similar regions between networks of different species. Existing methods compute node similarities to rapidly identify from possible alignments the high-scoring alignments with respect to the overall node similarity. But, the accuracy of the alignments is then evaluated with some other measure that is different than the node similarity used to construct the alignments. Typically, one measures the amount of conserved edges. Thus, the existing methods align similar nodes between networks hoping to conserve many edges (after the alignment is constructed!).
Instead, we introduce MAGNA to directly 'optimize' edge conservation while the alignment is constructed, without decreasing the quality of node mapping. MAGNA uses a genetic algorithm and our novel function for 'crossover' of two 'parent' alignments into a superior 'child' alignment to simulate a 'population' of alignments that 'evolves' over time; the 'fittest' alignments survive and proceed to the next 'generation', until the alignment accuracy cannot be optimized further. While we optimize our new and superior measure of the amount of conserved edges, MAGNA can optimize any alignment accuracy measure, including a combined measure of both node and edge conservation. In systematic evaluations against state-of-the-art methods (IsoRank, MI-GRAAL and GHOST), on both synthetic networks and real-world biological data, MAGNA outperforms all of the existing methods, in terms of both node and edge conservation as well as both topological and biological alignment accuracy.
Software: http://nd.edu/∼cone/MAGNA CONTACT: : tmilenko@nd.edu
Supplementary data are available at Bioinformatics online.
生物网络比对旨在识别不同物种网络之间的相似区域。现有的方法计算节点相似度，以便快速识别出可能的比对中，相对于整体节点相似度得分较高的比对。但是，比对的准确性随后会用不同于用于构建比对的节点相似度的其他度量来评估。通常，人们会衡量保留边的数量。因此，现有的方法在构建比对时，希望对齐网络中的相似节点，以保留尽可能多的边（在构建比对后！）。
相反，我们引入 MAGNA 来直接在构建比对时“优化”边的保留，而不会降低节点映射的质量。MAGNA 使用遗传算法和我们新的用于两个“父”比对的“交叉”的函数，将其转化为一个优越的“子”比对，以模拟随着时间推移而“进化”的比对“种群”；“适应性”最强的比对得以生存并进入下一个“世代”，直到无法进一步优化比对准确性为止。当我们优化新的和优越的保留边数量度量时，MAGNA 可以优化任何比对准确性度量，包括节点和边保留的综合度量。在针对最先进的方法（IsoRank、MI-GRAAL 和 GHOST）的系统评估中，无论是在合成网络还是真实生物数据上，MAGNA 在节点和边保留以及拓扑和生物学比对准确性方面都优于所有现有的方法。
软件：http://nd.edu/∼cone/MAGNA 联系人：tmilenko@nd.edu
补充数据可在 Bioinformatics 在线获取。
