MethylScan

MethylScan is a high-performance pipeline designed for the rapid extraction, hashing, and clustering of DNA methylation signatures directly from raw bisulfite sequencing reads. By utilizing localized k-mer entropy filtering and ultra-fast directional bisulfite hashing (BsHash), MethylScan entirely bypasses the need for traditional alignment, allowing for massive-scale downstream single-cell clustering.

The pipeline is split into two distinct stages: a C++ feature extractor (methyl_clus) and a unified Python clustering tool (MethylCluster_Public.py).

---

1. Feature Extraction (methyl_clus)

methyl_clus is a C++ utility that processes raw FASTQ/FASTA reads. Leveraging BsHash from btllib, it rapidly hashes bisulfite-converted sequences (C->T and G->A) into memory-efficient Bloom filters.

After parsing the raw data, it dumps the extracted methylation statuses into partitioned, sparse CSV matrices (e.g., methylation_top_20M_split_*.csv). These chunked matrices are explicitly formatted to be consumed by our downstream memory-efficient Python clustering scripts.

Build Instructions

methyl_clus uses meson and ninja for fast, reproducible builds.

# Setup the build directory
meson setup build

# Compile the binaries
cd build
ninja

Dependencies

• C++17 compliant compiler
• OpenMP (for multithreading)
• zlib (for gzip compressed fastq parsing)
• btllib (Bioinformatics Tool Library for BsHash and sequence parsing)

---

2. Downstream Clustering (MethylCluster_Public.py)

Once the chunked matrices are generated, they are fed into MethylCluster.py. This script is a unified, end-to-end Python clustering suite that utilizes geometry-preserving exact KNN graphs and Spectral Clustering.

Modes of Operation:

• Flat Clustering: (--mode flat) Sweeps through a requested range of clusters (--k-range), calculates exact nearest-neighbor topological graphs via UMAP distances, and selects the optimal k.
• Hierarchical Clustering: (--mode hierarchical) First partitions the data into broad super-clusters, then isolates each sub-population to dynamically discover fine-grained cellular subtypes.

Automated Metric Optimization: When provided a range of $k$ values (e.g. --k-range 2,10), the script automatically evaluates every clustering attempt using a suite of mathematical metrics:

• Silhouette Score (Default Optimizer)
• Graph Modularity
• Calinski-Harabasz Index
• Davies-Bouldin Index

Python Usage

python MethylCluster_Public.py --input methylation_top_20M_split_1.csv \
                               --outdir ./results \
                               --mode flat \
                               --k-range 2,15 \
                               --threads 8