Simultaneous optimization of both node and edge conservation in network alignment via WAVE

DOI10.1007/978-3-662-48221-6_2zbMATH Open1367.92039arXiv1410.3301OpenAlexW1488296747MaRDI QIDQ5283816FDOQ5283816

Authors: Yihan Sun, Joseph Crawford, Jie Tang, Tijana Milenković 

Publication date: 25 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Network alignment can be used to transfer functional knowledge between conserved regions of different networks. Typically, existing methods use a node cost function (NCF) to compute similarity between nodes in different networks and an alignment strategy (AS) to find high-scoring alignments with respect to the total NCF over all aligned nodes (or node conservation). But, they then evaluate quality of their alignments via some other measure that is different than the node conservation measure used to guide the alignment construction process. Typically, one measures the amount of conserved edges, but only after alignments are produced. Hence, a recent attempt aimed to directly maximize the amount of conserved edges while constructing alignments, which improved alignment accuracy. Here, we aim to directly maximize both node and edge conservation during alignment construction to further improve alignment accuracy. For this, we design a novel measure of edge conservation that (unlike existing measures that treat each conserved edge the same) weighs each conserved edge so that edges with highly NCF-similar end nodes are favored. As a result, we introduce a novel AS, Weighted Alignment VotEr (WAVE), which can optimize any measures of node and edge conservation, and which can be used with any NCF or combination of multiple NCFs. Using WAVE on top of established state-of-the-art NCFs leads to superior alignments compared to the existing methods that optimize only node conservation or only edge conservation or that treat each conserved edge the same. And while we evaluate WAVE in the computational biology domain, it is easily applicable in any domain.

Full work available at URL: https://arxiv.org/abs/1410.3301

Recommendations

• ELRUNA: elimination rule-based network alignment
• scientific article; zbMATH DE number 6304438
• Natalie 2.0: sparse global network alignment as a special case of quadratic assignment
• Lagrangian relaxations for multiple network alignment
• scientific article; zbMATH DE number 6262292

zbMATH Keywords

network alignmentnode cost function

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08)

Cites Work

• The complexity of theorem-proving procedures

Cited In (2)

• ELRUNA: elimination rule-based network alignment
• Exact \(p\)-values for global network alignments via combinatorial analysis of shared GO terms. \textit{REFANGO}: \textit{R}igorous \textit{E}valuation of \textit{F}unctional \textit{A}lignments of \textit{N}etworks using \textit{G}ene \textit{O}ntology

This page was built for publication: Simultaneous optimization of both node and edge conservation in network alignment via WAVE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283816)