Metadata-Version: 2.4
Name: hicstride
Version: 2.0.3
Summary: STRIDE: A Robust Dissimilarity Measurement for Chromatin Conformation Capture Data Based on Sequencing Depth-Insensitive Representation.
Home-page: https://gitee.com/matrix_evolution/STRIDE
Author: Bingxiang Xu
Author-email: xubingxiang@sus.edu.cn
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.23.4
Requires-Dist: scipy>=1.12.0
Requires-Dist: pandas>=2.2.1
Requires-Dist: joblib>=1.3.2
Requires-Dist: h5py>=3.10.0
Requires-Dist: torch>=2.10.0
Requires-Dist: scikit-learn>=1.9.0
Requires-Dist: tqdm>=4.67.3
Requires-Dist: hic-straw>=1.3.1
Dynamic: author
Dynamic: author-email
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: license-file
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

# STRIDE

**Spatial Topological Representation of Interaction Distance Evaluation**

[![Python](https://img.shields.io/badge/Python-3.8%2B-blue)](https://www.python.org/)
[![License](https://img.shields.io/badge/License-GPL--3.0-green.svg)](https://www.gnu.org/licenses/gpl-3.0)
[![PyPI](https://img.shields.io/badge/PyPI-hicstride-orange)](https://pypi.org/project/hicstride/)

---

## 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).

![logo](https://gitee.com/matrix_evolution/STRIDE/raw/master/images/logo.jpg)

---

## 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)

```bash
pip install hicstride
```

### From source

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

---

### Dependencies

STRIDE is developed and tested on Python 3.11.11 with the following Python packages required:

| Package            | Version | Purpose                              |
| ------------------ | ------- | ------------------------------------ |
| `python`           | ≥3.11   | --                                   |
| `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          |
| `scikit-learn`     | ≥1.9.0  | Performing the SVD decomposition     |

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

```bash
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

```bash
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

```bash
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

```bash
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

```bash
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

```bash
# 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

```bash
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

```bash
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](https://github.com/aidenlab/juicer/wiki)) 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`:

```python
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](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.
