Non negative matrix factorization for Global Network Alignment

Nov 18^th 2021

BMI 826-23 Computational Network Biology�Fall 2021

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Goals for today

• Introduction to matrix factorization
• FUSE: A matrix factorization based approach for graph alignment

​

Algorithms for global network alignment

​

• IsoRank:
• R. Singh, J. Xu, and B. Berger, "Global alignment of multiple protein interaction networks with application to functional orthology detection," Proceedings of the National Academy of Sciences, vol. 105, no. 35, pp. 12 763-12 768, Sep. 2008. [Online]. Available: http://dx.doi.org/10.1073/pnas.0806627105
• FUSE:
• V. Gligorijević, N. Malod-Dognin, and N. Pržulj, "Fuse: multiple network alignment via data fusion," Bioinformatics, vol. 32, no. 8, pp. 1195-1203, Apr. 2016. [Online]. Available: http://dx.doi.org/10.1093/bioinformatics/btv731

Goals for today

• Introduction to the matrix factorization
• FUSE: A matrix factorization based approach for graph alignment

​

Matrix factorization

• A popular data analysis technique used for high-dimensional datasets
• Decomposition and factorization used interchangeably
• Many applications:
• visualization, pattern extraction, interpretation and imputation, smoothing

​

​

Stein-O’Brien et al, Trends in Genetics 2018

R

W

H

Many different variants of MF

• Singular value decomposition

​

• Penalized matrix factorization

​

​

• Non-negative matrix factorization

​

​

​

• Matrix tri-factorization

​

Non-negative matrix factorization (NMF)

7

Minimize

Lee and Seung Adv. Neur. In. 2001

•

Slide credit Erika Da-Inn Lee

Non-negative matrix factorization (NMF)

8

X = ℝ^n×m

Slide credit Erika Da-Inn Lee

Non-negative matrix factorization (NMF)

9

X = ℝ^n×m

W = ℝ^n×k

H = ℝ^k×m

k << n, m

Slide credit Erika Da-Inn Lee

NMF multiplicative update rules

• Input X, the data matrix and k, the number of factors
• Initialize W and H to non-negative random entries
• Repeat until convergence
• Update W

​

​

​

• Update H

​

Lee and Seung Adv. Neur. In. 2001

Cluster indicator matrix

• Let k be the total number of clusters
• Let G be a cluster indicator matrix
• G is an nXk matrix which specifies the cluster ID for each entity

​

​

​

​

​

Objects

Clusters

Example for 5 objects in 2 clusters

Clustering as matrix factorization

Membership vector

Semi-Supervised Clustering via Matrix Factorization, Wang et al, 2008

NMF can be used for bi-clustering

H = ℝ^k×m

W = ℝ^n×k

Row clusters

Column clusters

Constrained MF: Clustering with guidance

Incorporating prior knowledge to constrain the factorization

15

Slide credit Erika Da-Inn Lee

Non-negative matrix tri-factorization (NMTF)

• Extends the constrained matrix factorization from one type of entity to two types of entities represented by X₁ and X₂
• A co-clustering (simultaneously clustering) of different types of entities based on the relationship of within and between entity types
• Cluster X₁ into G₁ and X₂ into G₂
• The intra-type relationships provide constraints into what objects can (must-link) and cannot be grouped together

Example of NMTF

Semi-Supervised Clustering via Matrix Factorization, Wang et al, 2008

Two types of objects: people and movies

​

Movies can be grouped based on actors, characters, titles

​

People can be grouped based on their hobbies and jobs

R₁₂

X₁

X₂

Blue: Must link

Red: Cannot link

NMTF for two entity types

• The objective is

​

​

​

​

​

• Here P(V_i) and P(V_j) are penalties one pays, if the clustering of the objects do not obey the intra-type constraints
• How to define this?
• We will use the Graph Laplacian for this

​

​

Constraints based on the intra-type graphs

Matrix tri-factorization

Non-negativity

Defining the penalty function with the graph Laplacian

• Recall the Laplacian L can be defined as

​

​

• Where D is the degree matrix and A is the adjacency matrix
• Furthermore, for every vector f in Rⁿ,

​

​

​

​

​

• If f is a cluster assignment to nodes in the graph, the above function measures how consistent is f wrt to the graph
• The more the cluster assignment obeys the connectivity the smaller this quantity

​

​

​

Edge weight

Defining the penalty function with the graph Laplacian

• Let G_i be a cluster indicator matrix
• We can assess the goodness of G_i with respect to the graph N_i as

Tr: Trace: sum of diagonal elements

NMTF for two entity types

• For two entity types i and j

​

​

​

​

Trade-off between maintaining intra-type constraints and estimating R_ij

Extending to k entity types

• For entities of k different types, we have k different constraint graphs
• We can write the objective as

This objective can be solved using an iterative multiplicative update algorithm from Wang 2008

Goals for today

• Quick RECAP of Global Network Alignment
• Introduction to the matrix factorization
• FUSE: A matrix factorization based approach for graph alignment

​

Motivation of FUSE

• How to do multiple global network alignment?
• In existing approaches the sequence-based node mapping is local, that is one pair at a time.
• Can we improve this mapping by using protein-protein interaction networks in each species?

​

FUSE multiple network alignment

• Given
• Protein-protein interaction networks for k species
• Pairwise sequence similarities for pairs of proteins from each pair of species
• Do
• Find a global one-to-one mapping between network nodes

​

Notation

• N_i =(V_i, E_i) denotes the vertex and edge set for a PPI network for species i
• Let n_i denote the number of proteins in species i
• Let R_ij denote an n_iXn_j sequence similarity matrix (E-values) of proteins from species i and j
• Let G_i and G_j specify the cluster assignments of proteins in i and j
• Let S_ij is a k_iXk_j lower-dimensional approximation of R_ij
• where k_i<<n_i and k_j<<n_j
• k_i and k_j can be thought of as the number of independent groups in N_i and N_j

Overview of FUSE

• Fuse sequence similarities and network wiring patterns over all proteins in all PPI networks being aligned

​

​

• Create a Global Multiple Network Alignment

Fuse step

• Based on Non-negative matrix tri-factorization (NMTF)
• Derives functional scores between pairs of proteins using sequence and network information for k species
• Conceptually similar goal to IsoRank

NMTF for Global network alignment

• Each entity type is a species
• Each entity is a protein from a species
• Constraints are specified by the protein-protein interaction networks N_i
• R_ij is the pairwise functional similarity between proteins of species i and j

NMTF for k entity types

• For entities of k different types, we have k different constraint graphs
• We can write the objective as

This objective can be solved using an iterative multiplicative update algorithm from Wang 2008

Rewriting the objective

• Let L, R, G be defined as follows matrices

​

​

• We can re-write the objective as follows

​

​

​

​

​

• Which is compactly written as

​

F

2

+

−

NMTF for k=5 species

min

G>=0

Sequence similarity for species 1 and 2

Laplacian for PPI network 2

Cluster assignment for proteins in species 2

Low-dimensional representation of R₁₂

Pictorial illustration for five species

Minimizing the objective NMTF

• We need to find S_ij, and G_i for all 1≤i,j≤k entity types
• An iterative algorithm is used that updates each entity one at a time
• Updates are obtained by deriving the J (while accounting for the non-negativity constraints) with respect to S_ij and G_i respectively

Overview of FUSE

• Fuse sequence similarities and network wiring patterns over all proteins in all PPI networks being aligned
• Create a Global Multiple Network Alignment

Global network alignment step

• Find a one-to-one Global Multiple Network Alignment
• Create a k-partite graph, where k is the number of species
• Finding approximately maximum weight k-partite matching

Create a k-partite weighted graph

• Recompute the new similarity based on sequence and network

​

• Select top 5% of the associations of each protein in a species
• Add back entries that were set to 0 by NMTF but have sequence similarity using a weighted sum of sequence and NMTF-based similarity

​

• This produces a weighted k-partite graph

​

​

A 3-partite weighted graph

Species 1

Species 2

Species 3

a

b

c

α

β

γ

δ

W

X

Y

Z

Algorithm to find the best matching

• Matching between two node sets is defined as a one-to-one mapping

​

• Weighted k-partite matching for k>2 is NP-hard

​

• Need a heuristic approach

Heuristic algorithm to find a maximum k-partite matching

K-partite graph

Graph merge step

• Let our k-partite graph be

​

​

• Let F_ij be a matching between nodes in V_i and V_j, where u_i in V_i is mapped to v_j in V_j
• Create new vertices V_ij from the matching, each vertex represented by a pair of nodes one from each graph
• This step is like creating an alignment graph!

Bi-partite matching example

Species i

a

b

α

β

γ

δ

c

Species j

Species i

a

b

α

β

γ

δ

Species j

Find a (maximal) matching (F_ij)

c

Graph merge from matching

a

b

α

β

γ

δ

c

Merged graph of species 1, 2

The merged nodes inherit the edges of the constituent nodes

New graph with all species

a

b

α

β

γ

δ

c

W

X

Y

Z

Note, this is not a matching

Results

• Dataset: Protein-protein interaction networks for five species
• Human (H. sapiens), mouse (M. musculus), fly (D. melanogaster), worm (C. elegans), yeast (S. cerevisiae)
• Experiments
• Assess the inferred functional orthologies based on similarity in annotation
• Compare against other methods

Statistics of PPI networks used

Species

NMTF induces new and reconstructs existing associations between proteins

• Apply PCA to estimate k_i, the number of clusters/factors for each species
• k₁= 80 (human); k₂ = 90 (yeast); k₃= 80 (fly); k₄= 70 (mouse) and k₅=50 (worm)
• 1,477, 372 interactions based on sequence
• 5% edges inferred corresponds to 19, 175, 378
• Covers 60% of the sequence-only edges
• What happens to the 40% edges?
• Compare the reconstructed (60%), predicted and non-reconstructed (40%) pairs
• Count the number of sequence-similar neighbors in each network
• Pairs with reconstructed similarities or new similarities are connected to many more similar neighbors (20.4 on average)
• Pairs with new similarities are also connected to neighbors with high sequence similarity (12.1)
• Pairs that are not reconstructed have much lower sequence similarity in their neighborhood (8.6).

​

​

​

Do the new similarities make sense?

Compute the cumulative number of associations between annotated proteins and the percentage of them sharing GO term (Biological Process (BP) and Molecular Function (MF) annotations separately).

Comparison against other algorithms

• Algorithms compared
• Beams
• Smetana
• CSRW
• NH
• IsoRank
• NetCoffee
• Evaluation metrics
• Coverage
• Good clusters: cover all five PPI networks
• Bad clusters: cover less than five PPIs
• Computed at the cluster and protein level
• Functional consistency
• An annotated cluster is consistent if all of its annotated proteins have at least one common annotation

Did not finish in time

FUSE produces the largest number of good clusters

Fraction of blue is highest for clusters and proteins for FUSE.

Good: inclusion of as many species as possible

FUSE produces functionally consistent clusters

A cluster is said to be functionally consistent, if all its annotated proteins have at least one GO term in common.

Summary

• FUSE is a multiple network alignment algorithm
• It uses multiple graphs simultaneously to redefine the functional similarity among proteins
• Strengths: Compared to existing algorithms it is able to infer higher coverage and functionally consistent protein clusters (orthologous groups)
• Weaknesses:
• One-to-one mapping misses out on gene duplications
• The hyper-parameters might influence the results, and it is not clear how to set them.

​

​

Concluding remarks

• Network alignment seeks to find similarities and differences between molecular networks of different species
• We have seen algorithms for
• Local Alignment
• PathBLAST, Sharan et al 2004
• Used a probabilistic, per edge score but was trying to find paths and modules
• Global pairwise and multiple network alignment
• IsoRank (many-to-many node mappings)
• FUSE (one-to-one mappings)