calc_graph_dist: Compute graph-based distance among cells or locations

In lambdamoses/novoSpaRc: Spatial Reconstruction of Tissues from scRNA-seq Data

Description

Since Euclidean distance and Pearson correlation cannot capture the true geometry of non-linear low dimensional manifolds, a graph-based distance is used instead in novoSpaRc. This function first computes a k-nearest neighbor graph among cells or locations. Then it infers the shortest pairwise path lengths on the graph for cells and locations, resulting in a graph-based distance matrix, which is then used for the optimal transport reconstruction of locations of gene expression.

Usage

calc_graph_dist(X, k, BNINDEX, BNPARAM, BPPARAM = SerialParam(),
  transposed = FALSE, ...)

Arguments

X	Numeric matrix (can be sparse) with genes in rows and cells in columns. If genes are in columns, then set transposed = TRUE.
k	Number of nearest neighbor when constructing k-nearest neighbor graph.
BNINDEX	A BiocNeighborIndex object, or NULL.
BNPARAM	A BiocNeighborParam object, or NULL if BININDEX is supplied.
BPPARAM	An object of BiocParallelParam class for parallelization. See details.
transposed	Logical, whether the matrix has cells in rows rather than in columns. Defaults to FALSE.
...	Further arguments to pass to findKNN.

Details

Whlie the Python implementation of this package uses the Floyd Warshall algorithm to find the shortest path between vertices in the graph, this function uses the Johnson algorithm, which is more efficient for sparse graphs. Let V denote the number of vertices in the graph, and E number of edges. The Floyd Warshall algorithm has complexity O(V^3), while the Johnson algorithm has complexity O(V^2 \log(V) + VE). We expect k-nearest neighbor graphs to be sparse since k is usually much smaller than the number of vertices, so the number of edges is much smaller than in the complete graph, which is V(V-1) in directed graphs.

The BPPARAM argument is used for parallel computing in k-nearrest neighbor search. For instance, use BPPARAM = MulticoreParam(3) for using 3 threads in shared memory computing.

The BNINDEX argument is for precomputed index information for different algorithms to find k-nearests neighbors. Using a pre-computed index will save when multiple KNN search are performed on the same x. If BNINDEX is to be specified, then x should be missing.

The BNPARAM argument is used for setting parameters for KNN search algorithms, such as the kind of distance metric used.

Only one of BNINDEX and BNPARAM is needed to determine the algorithm used, and if both are supplied, they must specify the same algorithm. If both are missing, then the KmKNN algorithm will be used.

Value

A dense square numeric matrix with n cells columns and rows. The entry at ith row and jth column represents the normalized shortest path length between vertex i and vertex j.

lambdamoses/novoSpaRc documentation built on May 12, 2019, 3:14 p.m.