STRIDE

Spatial Topological Representation of Interaction Distance Evaluation

---

Introduction

STRIDE is a computational framework for robust analysis of chromatin conformation capture data (Hi-C, HiChIP, and single-cell Hi-C) based on the mean first passage time (MFPT) representation from Markov chain theory. The MFPT transformation converts chromatin contact matrices into a graph-based distance representation that is empirically robust to sequencing-depth reduction, preserving key topological features such as TADs and chromatin loops even under extreme sparsity.

STRIDE provides the following functionalities:

• MFPT representation — Transform a contact matrix into its MFPT representation.
• STRIDE metric — Compute a sequencing-depth-robust dissimilarity score between two Hi-C libraries.
• Differential chromatin contact (DCC) analysis — Identify biologically meaningful differential contacts between two conditions (testing).
• Single-cell Hi-C analysis — Impute and embed sparse single-cell Hi-C data within the scHiCluster framework (testing).

---

Installation

System Requirements

The STRIDE package requires only a standard computer running a typica Linux distribution with enough RAM to support the in-memory operations. A GPU device with CUDA support is required if any GPU accelerated computation is needed.

From PyPI (recommended)

pip install hicstride

From source

git clone https://gitee.com/matrix_evolution/STRIDE.git
cd STRIDE
pip install -e .

---

Dependencies

STRIDE requires the following Python packages:

Package	Version	Purpose
numpy	≥1.20.0	Core numerical operations
scipy	≥1.7.0	Matrix operations and linear algebra
h5py	≥3.0.0	HDF5 I/O for MFPT storage
pandas	≥1.3.0	Data I/O and manipulation
joblib	≥1.1.0	Parallel processing
hicstraw	≥0.4.0	Reading .hic files
torch (optional)	≥1.10.0	GPU acceleration (if available)
tqdm	≥4.67.3	Displaying the progress bar

All dependencies will be installed automatically when installing via pip.

---

Command-line Usage

STRIDE provides four subcommands: mfpt, stride, dcc, and sc.

Global Options

The following options are available for all subcommands:

Option	Type	Default	Description
resolution	int	(required)	Resolution (bin size) in base pairs
-o, --output-dir	str	.	Output directory (created if not exist)
-n, --name	str	STRIDE	Project name used for output file naming
-d, --device	str	cpu	Computing device (cpu or cuda)

Additional options specific to certain subcommands are described below.

---

Subcommand: mfpt

Calculate the MFPT representation for a single Hi-C contact map.

Syntax

stride mfpt [-c MIN_COVERAGE] [-k KR_TOLERANCE] [--ch CH] [-d DEVICE] [-o OUTPUT_DIR] [-n NAME] resolution input

Positional Arguments

Argument	Description
resolution	Resolution in base pairs
input	Path to the input .hic file

Specific Options

Option	Type	Default	Description
-c, --min-coverage	float	0.02	Proportion of low-coverage bins to mask before KR normalization
-k, --KR-tolerance	float	1e-12	Convergence tolerance for KR normalization
--ch	str	^chr(?:\d+|X)	Regular expression for chromosome selection

Output

The MFPT representation for each chromosome is stored in an HDF5 file:

{output_dir}/{name}.hdf
  └── {input_basename}/
        └── {chr_name}/
              ├── cm_norm   — ICE-normalized contact matrix
              └── cm_mfpt   — Symmetric MFPT representation

Example

stride mfpt 50000 GM12878.hic -o ./output -n GM12878_mfpt --ch "^chr1$"

---

Subcommand: stride

Compute the STRIDE dissimilarity score between two Hi-C libraries.

Syntax

stride stride [-c MIN_COVERAGE] [-k KR_TOLERANCE] [--ch CH] [-d DEVICE] [-o OUTPUT_DIR] [-n NAME] [--norm NORM] [--store-mfpt] resolution input1 input2

Positional Arguments

Argument	Description
resolution	Resolution in base pairs
input1	Path to the first .hic file
input2	Path to the second .hic file

Specific Options

Option	Type	Default	Description
--norm	str / int	fro	Matrix norm type (supported by scipy.linalg.norm): fro, nuc, inf, integer, or None
--store-mfpt	flag	False	Store MFPT matrices to HDF5 for downstream DCC analysis
-c, --min-coverage	float	0.02	Proportion of low-coverage bins to mask
-k, --KR-tolerance	float	1e-12	Convergence tolerance for KR normalization
--ch	str	^chr(?:\d+|X)	Regular expression for chromosome selection

Output

• STRIDE score file: {output_dir}/{name}_scores.txt, tab-delimited with chromosome names and corresponding STRIDE distances.
• MFPT HDF5 file (if --store-mfpt is enabled): {output_dir}/{name}.hdf, storing the MFPT matrices of both libraries for downstream DCC analysis. The HDF5 file contains the following datasets for each chromosome:
  • {input1_basename}/{chr_name}/cm_norm — Normalized contact matrix of library 1
  • {input2_basename}/{chr_name}/cm_norm — Normalized contact matrix of library 2
  • {input1_basename}/{chr_name}/cm_mfpt — MFPT matrix of library 1
  • {input2_basename}/{chr_name}/cm_mfpt — MFPT matrix of library 2

Example

stride stride 50000 GM12878_full.hic GM12878_downsampled.hic \
    -o ./output -n GM12878_vs_downsampled --norm fro --store-mfpt

---

Subcommand: dcc

Perform differential chromatin contact (DCC) analysis between two conditions based on MFPT representations.

Note: The dcc subcommand is an experimental feature, provided primarily to demonstrate the feasibility of the MFPT representation in differential chromatin conformation analysis. Users are advised to interpret the results with caution and to treat them as exploratory rather than as validated biological findings.

Syntax

stride dcc [-d DEVICE] [-o OUTPUT_DIR] [-n NAME] [--loop-p-value LOOP_PVALUE] [--diff-p-value DIFF_PVALUE] [--raw-enrich-pvalue RAWENRICHP] [--raw-unenrich-pvalue RAWUNENRICHP] [--min-dist MIN_DIST] [--max-dist MAX_DIST] [--batch-size BATCH_SIZE] resolution cond1 cond2 hdfFile

Positional Arguments

Argument	Description
resolution	Resolution in base pairs
cond1	Name of the first condition (must match the key in the HDF5 file, e.g., K562)
cond2	Name of the second condition (must match the key in the HDF5 file, e.g., GM12878)
hdfFile	Path to the HDF5 file containing MFPT representations (generated by stride --store-mfpt)

Specific Options

Option	Type	Default	Description
--loop-p-value	float	0.05	P-value threshold for significant loop enrichment within a condition in MFPT representation
--diff-p-value	float	0.05	P-value threshold for significant difference between conditions in MFPT representation
--raw-enrich-pvalue	float	0.001	P-value threshold for raw contact enrichment in the condition-specific region
--raw-unenrich-pvalue	float	0.1	P-value threshold for raw contact absence in the opposite condition
--min-dist	int	7	Minimum genomic distance for DCC candidates (in bins; e.g., 7 bins = 70 kb at 10-kb resolution)
--max-dist	int	500	Maximum genomic distance for DCC candidates (in bins; e.g., 500 bins = 5 Mb at 10-kb resolution)
--batch-size	int	3000	Batch size for z-score calculation (memory vs. speed trade-off)
-c, --min-coverage	float	0.02	Proportion of low-coverage bins to mask (inherited from MFPT computation)
-k, --KR-tolerance	float	1e-12	Convergence tolerance for KR normalization (inherited from MFPT computation)
--ch	str	^chr(?:\d+|X)	Regular expression for chromosome selection

Output

• DCC result file: {output_dir}/{name}_dcc.txt, tab-delimited with a header row and the following columns:

Column	Description
chr1	Chromosome name
x1, x2	Start and end coordinates of the first anchor
chr2	Chromosome name (identical to chr1)
y1, y2	Start and end coordinates of the second anchor
p	Mann–Whitney U p-value for contact enrichment in the condition-specific region
p_bg	Mann–Whitney U p-value for contact absence in the opposite condition
{cond1_name}	MFPT-derived Z-score in condition 1
{cond2_name}	MFPT-derived Z-score in condition 2
z	Difference in Z-scores (condition1 - condition2)

Condition specificity is determined by which condition shows significant enrichment and is reflected in the output context (the file is generated with the specified condition order).

Example

# First, compute STRIDE with MFPT storage
stride stride 10000 K562.hic GM12878.hic \
    -o ./dcc_input -n K562_vs_GM12878 --store-mfpt


# Then, perform DCC analysis
stride dcc 10000 K562 GM12878 ./dcc_input/K562_vs_GM12878.hdf \
    -o ./dcc_results -n DCC_K562_GM12878 \
    --loop-p-value 0.01 --diff-p-value 0.01 \
    --min-dist 7 --max-dist 500 --batch-size 2000

---

Subcommand: sc

Perform single-cell Hi-C imputation and embedding using the MFPT representation within the scHiCluster framework.

Note: The sc subcommand is an experimental feature. It is provided to illustrate the applicability of the MFPT representation to sparse single-cell Hi-C data and serves as a proof-of-concept demonstration. The current implementation has not been extensively optimized for large-scale single-cell datasets, and results should be interpreted with appropriate caution.

Syntax

stride sc [-d DEVICE] [-o OUTPUT_DIR] [-n NAME] [--std STD] [--radius RADIUS] [--n_comp N_COMP] [--n_cpu N_CPU] resolution base_dir chrom_size cell_name

Positional Arguments

Argument	Description
resolution	Resolution in base pairs (recommended: 1000000 for single-cell)
base_dir	Base directory containing cell–chromosome contact maps in COO format (see Input Formats below)
chrom_size	Chromosome length file (see Input Formats below)
cell_name	Cell list file containing one cell identifier per line

Specific Options

Option	Type	Default	Description
--std	float	1.0	Standard deviation of the Gaussian smoothing kernel
--radius	int	3	Radius of the Gaussian kernel (actual kernel size: 2*radius+1; for a 7×7 kernel, set --radius 3)
--n_comp	int	50	Number of SVD components for the embedding of the cells
--n_cpu	int	0	Number of CPU cores for parallel processing (0 = use all physical cores)

Output

• Embedding file: {output_dir}/{name}_embedding.txt, tab-delimited with cell names as row indices and SVD components as columns. Only cells that passed the connectivity check are included.

Example

stride sc 1000000 ./scHiC_data/ chrom_sizes.txt cell_list.txt \
    -o ./sc_output -n mESC_embedding \
    --std 1.0 --radius 3 --n_comp 50 --n_cpu 8

---

Input Formats

Bulk Hi-C: .hic files

For the mfpt and stride subcommands, input files must be in the standard .hic format generated by the [Juicer](Home · aidenlab/juicer Wiki · GitHub) pipeline. STRIDE uses hicstraw to read these files.

Single-cell Hi-C: COO format

For the sc subcommand, contact maps must be stored as plain-text files in COO (coordinate) format, with one file per cell–chromosome combination.

File naming convention

{cell_name}_{chromosome}.txt

For example:

mESC_001_chr1.txt
mESC_001_chr2.txt
...

File content

Each file contains three columns, separated by whitespace:

Column	Description
bin1	Genomic coordinate of the first bin (actual position, not bin index)
bin2	Genomic coordinate of the second bin
count	Contact count between the two bins

Example:

3000000       4000000       2
3000000       45000000      1
4000000       5000000       3
4000000       34000000      1
……

Important: Coordinates should represent the actual genomic positions (start coordinates of bins), not bin indices. STRIDE will automatically convert them to bin indices based on the provided resolution.

Chromosome length file (chrom_size)

A plain-text file with two whitespace-delimited columns:

Column	Description
chr_name	Chromosome name (e.g., chr1, chrX)
length	Total length of the chromosome in base pairs

Example:

chr1    249250621
chr2    243199373
chrX    155270560

Cell list file (cell_name)

A plain-text file containing one cell identifier per line. Each identifier must match the prefix of the COO filenames. Empty lines are ignored.

Example:

mESC_001
mESC_002
mESC_003

Note: Cells that fail the connectivity check during MFPT calculation are automatically excluded from the final embedding; the output file contains only valid cells.

---

Output Formats

HDF5 Files (.hdf)

MFPT representations are stored in HDF5 format with the following hierarchy:

{project_name}.hdf
  └── {library_basename}/
        └── {chromosome}/
              ├── cm_norm   — ICE-normalized contact matrix (2D float array)
              └── cm_mfpt   — Symmetric MFPT representation (2D float array)

These files can be read using h5py:

import h5py
with h5py.File('STRIDE.hdf', 'r') as f:
    mfpt_chr1 = f['GM12878/chr1/cm_mfpt'][:]

STRIDE Score Files

{name}_scores.txt — tab-delimited:

chr1    0.1234
chr2    0.1156
chrX    0.1402

DCC Output Files

{name}_dcc.txt — tab-delimited with a header row:

chr1	x1	x2	chr2	y1	y2	p	p_bg	K562	GM12878	z
chr1	100000	150000	chr1	200000	250000	0.0005	0.15	3.2	0.8	2.4

Single-cell Embedding Files

{name}_embedding.txt — tab-delimited with cells as rows and components as columns:

Cell    SVD1    SVD2    ...    SVD20
mESC_001    -0.234    0.145    ...    0.032
mESC_002    0.112    -0.078    ...    -0.021

---

Performance Considerations

STRIDE involves dense matrix operations, particularly Cholesky decomposition during MFPT computation. Performance benchmarks (based on the paper):

Task	Resolution	Time (wall-clock)	Peak Memory
STRIDE (whole genome)	50 kb	~50 s	~5.2 GB
STRIDE (whole genome)	5 kb (estimated)	~10 h	~40 GB
Single-cell MFPT (~2,000 cells)	1 Mb	<5 min	<1 GB

• For large datasets, we recommend using a machine with at least 128 GB RAM.
• The --device cuda option enables GPU acceleration when PyTorch is installed (though dense matrix operations are primarily CPU-bound due to Cholesky decomposition; GPU acceleration is currently utilized primarily for convolution operations in the single-cell pipeline and z-score calculations in DCC analysis).

---

Test data

There are two .hic files in the "test" directory, derived from the two HindIII-digested hESC libraries in dataset GSE35156. We extracted only the segments with a resolution of 50 Kb. The stride command can be run on this test set using the following command line.

stride stride --store-mfpt -o demo --norm 2 50000 GSM862723.hic GSM892306.hic

A "demo" directory will be created automatically and the STRIDE score of chromosome 1 to 22 and X calculated with all arguments set as defaults will be stored in the file "STRIDE_score.txt". Other subcommands work in a similar way.

In a workstation equipped with dual Intel Xeon Gold 8380 processers (80 cores) and 256GiB RAM, such a calculation will be accomplished in about 5 minutes without using any GPU acceleration.

Citation

If you use STRIDE in your research, please cite our paper:

Xu, B., Gao, X., Tao, W., Zhang, Z., & Li, F. (2026). STRIDE: A sequencing-depth-resilient framework for 3D genome analysis based on mean first passage time representation. [Manuscript in preparation].

---

License

This project is licensed under the GPL v3 License. See the LICENSE file for details.

---

Contact

For questions, bug reports, or feature requests, please contact the corresponding authors:

• Bingxiang Xu: xubingxiang@sus.edu.cn
• Zhihua Zhang: zhangzhihua@big.ac.cn
• Feifei Li: liff@scut.edu.cn

---

Acknowledgments

This work was supported by the National Natural Science Foundation of China (32200515, 32470672, 32341011), the Hebei Natural Science Foundation (C2026202008), the Strategic Priority Research Program of CAS (XDA0460300, XDC0200000), the Biological Breeding-National Science and Technology Major Project (2022ZD04017), and the Natural Science Foundation of Guangdong Province (2025A1515012339).

---

STRIDE — Robust 3D genome analysis, from sparse data to meaningful biology.