Get imputed contact map

The RWR algorithm is a variant of the traditional random walk technique. It is designed to explore the graph by randomly walking through its nodes, with the added feature that at each step, there is a probability the walk will β€œrestart” and return to a predefined starting node. We implement this algorithm, as referenced in previous research, for the interpolation of single-cell 3D genome data.

First, we construct a probability transition matrix by normalizing the single-cell contact matrix (A) such that each row sums to 1. The walk restarts at the starting node with a probability \(π‘Ÿ\), and with the probability \(1βˆ’π‘Ÿ\), it proceeds to a neighboring node. The goal is to find the steady-state Ο€ which represents the matrix given the restart probability \(π‘Ÿ\). The RWR is solved iteratively through the following steps:

  1. Initialization: Start with an initial probability vector \(πœ‹0 = A\).

  2. Iteration: Update πœ‹ using the formula: \(πœ‹π‘‘+1 = (1βˆ’π‘Ÿ)𝑃 πœ‹π‘‘ + π‘ŸA\). \(P\) is XXX.

  3. Convergence: Repeat the iteration until Ο€ converges, when \(|| πœ‹π‘‘+1 - πœ‹π‘‘ ||< 10^{-6}\).

Upon completion of the iterations, we obtain πœ‹π‘‘+1 which serves as the imputated single-cell contact matrix.

stark impute --mcool-path/absolute/path/to/data/gini/dipC_GSE117874_hum \
--resolution 1000000 \
--output/absolute/path/to/result/impute \
--nthread 2

The result like this:

_images/impute.png