Graph alignment: Applications to scRNA-seq data integration

Nov 29^th 2022s

BMI/CS 775 Computational Network Biology�Fall 2022

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Plan for this section

​

• Global alignment of protein-interaction networks
• Spectral method: IsoRank (Nov 22^nd)
• Matrix factorization: FUSE (Nov 22^nd)

​

• Graph-based alignment for single cell omic datasets (Nov 29^th)

Goals for today

• Aligning different datasets
• Dimensionality reduction techniques
• Singular Value Decomposition
• Non-negative matrix factorization and extensions
• Canonical Correlation Analysis
• Approaches to align datasets
• Mutual nearest neighbor alignment
• Seurat
• Scanorama
• CONOS
• LIGER

​

Applications of network alignment

Alignment of scRNA-seq datasets

Alignment of molecular networks

• PathBLAST
• IsoRank
• FUSE

• SCANORAMA
• CONOS
• LIGER
• scPopcorn

Aligning high-dimensional datasets

• Often high-dimensional datasets have a low-dimensional structure
• Such low-dimensional structure can be approximated by a graph
• Dataset alignment can be considered as an instance of graph alignment
• Broadly speaking, this aims to construct low dimensional mappings between two or more datasets by aligning their low-dimensional spaces

Adapted from “Manifold alignment”, Wang et al 2010

Single cell omics

Slide credit: 10x genomics

A single cell RNA-seq dataset

scRNA-seq dataset

genes (6k-20k)

cells (5k-1million)

Computational problems with scRNA-seq data

1. Pre-processing and normalization
2. Visualization
3. Cell type identification
4. Trajectory inference:
1. Single cell ordering: pseudo time
2. Cell population structure relationships
5. Network inference
6. Data integration

Computational tools for single cell omic datasets

Zappia, L. & Theis, F. J. Over 1000 tools reveal trends in the single-cell RNA-seq analysis landscape. Genome Biol 22, 301 (2021).

Flavors of data integration

• Integrate multiple scRNA-seq datasets, each representing a time point or treatment condition
• Integrate multi-modal single cell datasets
• scRNA-seq
• scATAC-seq
• spatial RNA-seq
• Query new dataset with an existing tissue atlas

Overall Problem Definition

• Given N single cell RNA-seq datasets, E₁, .. E_N

​

• Do
• Find a correspondence of the cells and cell types in one dataset to cells and cell types in another dataset

​

​

What makes integration of scRNA-seq datasets difficult?

• Presence of batch effects

​

• Unknown number of cell types

​

• Varying number of cell types across datasets

​

• ..

General approach to aligning datasets

1. Define k-nearest neighbor graphs
1. Often accompanied with dimensionality reduction
2. Correct/align cells

​

• (Optional) cluster

Goals for today

• Aligning different datasets
• Dimensionality reduction techniques
• Singular Value Decomposition
• Non-negative matrix factorization and extensions
• Canonical Correlation Analysis
• Approaches to align datasets
• Mutual nearest neighbor alignment
• Seurat
• Scanorama
• CONOS
• LIGER

​

Singular Value Decomposition

By Cmglee - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=67853297

Non-negative matrix factorization

Minimize

Lee and Seung Adv. Neur. In. 2001

•

Slide credit Erika Da-Inn Lee

Cells

Genes

H

E

W

s.t, H>=0, W>=0

Using NMF factors for clustering

• Cell i is in cluster k if

​

Cells

H

• Gene j is in cluster k if

​

W

Applying NMF to a single cell RNA-seq dataset

Extensions to NMF

• Joint NMF

​

​

• Integrative NMF

Joint NMF

E₁

H₁

H₂

W

genes

W

E₂

=

cells

cells

Integrative NMF

X

+

genes

X

+

X

+

W

cells

cells

cells

W

W

E₁

H₁

H₂

E₂

E₃

H₃

V₁

V₂

V₃

Canonical Correlation Analysis

Canonical correlation analysis

• u and v are called the first correlation vectors
• We can keep finding subsequent vectors that are orthogonal to the ones before
• We can get the canonical correlations by performing SVD on the cross-correlation matrix

​

Goals for today

• Dimensionality reduction techniques
• Singular Value Decomposition
• Non-negative matrix factorization and extensions
• Canonical Correlation Analysis
• Approaches to align datasets
• Mutual nearest neighbor alignment
• Seurat
• Scanorama
• CONOS
• LIGER

​

Batch effect correction of scRNA-seq data using mutual nearest neighbors

• L. Haghverdi, A. T. L. Lun, M. D. Morgan, and J. C. Marioni, “Batch effects in single-cell RNA-sequencing data are corrected by matching mutual nearest neighbors,” Nat. Biotechnol., vol. 36, no. 5, pp. 421–427, 2018, doi: 10.1038/nbt.4091.
• Previous approaches relied on methods for bulk methods
• This approach aimed to find “mutual nearest neighbors” (MNN) that it will use to align different datasets
• Assumes there is at least one cell population that is present in both batches

MNN for batch correction

1. Two batches of data

​

• Find mutual nearest neighbors

​

• Find correction vectors

​

• Shift one dataset to another

​

• Repeat for new batches

Comparing MNN to other methods

Simulated dataset

Real dataset

SEURAT

• Stuart T, Butler A, Hoffman P, et al. Comprehensive Integration of Single-Cell Data. Cell. 2019;177(7):1888-1902.e21. doi:10.1016/j.cell.2019.05.031
• Dimensionality reduction uses Canonical correlation analysis
• Find anchor points based on k mutual nearest neighbors on the reduced space.

​

SEURAT key steps

Identifying anchors in Seurat

• Based on a k mutual nearest neighbor step
• Set anchors as mutual nearest neighbors

​

• Score anchors based on the shared neighborhood of anchors in the query and reference dataset

​

• Check to make sure anchors in low dimensional space are found in the high dimensional space

Scanorama

• B. Hie, B. Bryson, and B. Berger, “Efficient integration of heterogeneous single-cell transcriptomes using Scanorama,” Nat. Biotechnol., vol. 37, no. 6, pp. 685–691, 2019, doi: 10.1038/s41587-019-0113-3.
• Does not assume that the datasets we are integrating have a lot in common
• Conceptual idea is like putting together pieces of a puzzle.

​

High level picture of Scanorama

• Given four cell types A, B, C and D that make up three datasets (A, B), (C, D) and (B, C),
• Scanorama automatically finds the correct set of alignments (A, B) to (B, C) to (C, D) by finding mutual nearest neighbors across all three possible pairs of these datasets

​

Scanorama key steps

E1

E2

E3

Concatenate datasets

genes

SVD+ first 100 dimensions

cells

cells

cells

K-mutual nearest neighbors

Panorama

Scanorama Panorama creation

Scanorama “projection step”

• Scanorama has an optional batch correction step similar to the MNN approach
• Compute weights for each cell not in the matching set to a cell in the matching set.
• This is using a Gaussian kernel
• For each cell, compute a translation vector which is then the linear combination of the matching difference and weights of each cell in the matching set.

Scanorama “projection step”

Slide credit Junha Shin

SCANORAMA on artificial mixtures

SCANORAMA

MNN

Seurat CCA

Other methods are sensitive of the order of integration

Using SCANORAMA to integrate 100k cells from 26 datasets

Scanorama clusters by cell type as opposed to other methods

SCANORAMA learns good clusters

LIGER

• Assumes datasets are have a shared and specific lower dimensional representation
• Uses integrative NMF to find this

LIGER key steps

• iNMF to find reduced cell and gene space
• Cluster cells based on iNMF factors
• Refine cell clusters further to handle divergent datasets

LIGER: Defining cell clusters

• Simple max loading is noisy for divergent datasets
• Use H_i to define the k-nearest neighborhood of a cell
• Assign each cell i the cluster based on max factor loading
• Get the histogram of cluster assignments of neighbors of i
• Compute Manhattan Distance between cluster histograms.
• Sum of absolute difference in histograms
• Connect two cells if their distance is less than t
• Louvain graph clustering

Benchmarking LIGER

Applying LIGER to integrate multiple datasets

Cell clusters

Gene markers

Using LIGER to integrate scRNA-seq and spatial transcriptomics data

scRNA-seq: 71,000 cells

spatial: 2500 cells

scRNAseq

spatial

CONOS

• Similar conceptually to Scanorama
• Also able to integrate samples across many different platforms and contexts
• Project pairs of datasets on the same space
• Cluster all cells together in the projected space

​

CONOS key steps

• Perform a pairwise alignment of each pair of datasets to get inter-sample edges
• Common PCA
• Joint NMF
• SVD
• Add edges between pairs of cells between pairs of datasets using the lower dimensional representation
• Add low weight intra sample edges to get a Joint graph (helps preserve local neighborhood of cells)
• Graph clustering with Leiden to define populations across all samples

​

​

Applying CONOS to 16 blood scRNA-seq datasets

Joint embedding of datasets

Visualizing individual datasets

Comparing CONOS to other methods

Summary of algorithms

Take away points

• We talked about two types of alignment problems
• Aligning across species
• Nodes are mismatched, but we have some sequence based mapping that we wish to exploit
• Algorithms:
• FUSE, IsoRank
• Differ based on: Pairwise, global, local, how to define the similarity matrix
• Aligning across datasets
• Nodes might have a substantial mismatch and datasets can only partially overlap
• Algorithms differ based on
• how they project into the shared space
• cluster or not

​

​

References

• Stuart, Tim, Andrew Butler, Paul Hoffman, Christoph Hafemeister, Efthymia Papalexi, William M. Mauck, Yuhan Hao, Marlon Stoeckius, Peter Smibert, and Rahul Satija. 2019. “Comprehensive Integration of Single-Cell Data.” Cell 177 (7): 1888-1902.e21. https://doi.org/10.1016/j.cell.2019.05.031.
• Barkas, Nikolas, Viktor Petukhov, Daria Nikolaeva, Yaroslav Lozinsky, Samuel Demharter, Konstantin Khodosevich, and Peter V. Kharchenko. 2019. “Joint Analysis of Heterogeneous Single-Cell RNA-Seq Dataset Collections.” Nature Methods 16 (8): 695–98. https://doi.org/10.1038/s41592-019-0466-z.
• Hie, Brian, Bryan Bryson, and Bonnie Berger. 2019. “Efficient Integration of Heterogeneous Single-Cell Transcriptomes Using Scanorama.” Nature Biotechnology 37 (6): 685–91. https://doi.org/10.1038/s41587-019-0113-3.
• Welch, Joshua D., Velina Kozareva, Ashley Ferreira, Charles Vanderburg, Carly Martin, and Evan Z. Macosko. 2019. “Single-Cell Multi-Omic Integration Compares and Contrasts Features of Brain Cell Identity.” Cell 177 (7): 1873-1887.e17. https://doi.org/10.1016/j.cell.2019.05.006.

​

​

​