Probabilistic ancestry inference beyond variant calls
KORUS (K-mer Orthogonal Representation for Unified Stratification of ancestry) is a probabilistic framework for genomic ancestry inference using k-mer signals encoded in Bloom filters. It supports local and genome-wide ancestry inference without requiring explicit variant calling or sequence alignment of query genomes.
Feature Matrix → Probabilistic Decoding Framework for Genomic Ancestry Inference
- Overview
- Key Methodological Features
- Credit
- Methodological Framework
- KORUS Modes
- Installation
- Tested Environment
- Requirements
- Input Files
- Running KORUS using one query sample with the provided reference matrix
- Advanced usage: Generating a custom reference matrix with KORUS
- Advanced usage: Running KORUS using multiple samples
- Interactive Visualizations
- Citing
- License
KORUS is a two-stage computational framework for ancestry inference from sequencing data using k-mer–derived genomic features encoded in Bloom filters.
Rather than relying on alignment or variant calling, KORUS transforms sequencing data into a structured genomic feature space and performs probabilistic decoding to infer ancestry structure across the genome.
The framework consists of:
- MATRIX stage — construction of k-mer–derived genomic feature matrices. KORUS converts k-mer presence in Bloom filters into normalized, per-window ALT–REF scalar signals and aggregates these into a sample-by-window feature matrix.
- DECODE stage — probabilistic inference of ancestry from feature space. The feature space is treated as an orthogonalized ancestry embedding in PCA-reduced coordinates, enabling covariance-aware distance classification. In other words, the feature space is treated as a decorrelated representation in PCA space prior to Mahalanobis distance estimation. Ancestry scores are computed using Mahalanobis distances in this PCA-reduced feature space and transformed via softmax normalization to obtain probabilistic ancestry estimates.
An optional hidden Markov model (HMM), decoded using the Viterbi algorithm, smooths window-wise ancestry paths before genome-wide ancestry fractions are calculated.
- k-mer/Bloom-filter ancestry representation
- Reference-free signal extraction
- Alignment-free local ancestry inference
- Soft-supervised ancestry manifold modeling
Developed by René L Warren
Transforms Bloom filter–encoded sequencing data into a structured genomic feature representation.
Key steps:
- Build per-sample k-mer Bloom filters (ntEdit/ntStat compatible)
- Query per-sample Bloom filters for ancestry-informative SNV k-mer membership
- Compute allele-specific support (REF vs ALT k-mers)
- Derive normalized directional signal per locus
- Aggregate signals into fixed genomic windows
- Construct samples × window feature matrix
Output:
- Continuous genomic feature matrix across samples and windows
Performs probabilistic inference of ancestry from the feature matrix.
Key Steps:
- Standardization of the feature matrix
- Dimensionality reduction (PCA)
- Distance-based classification (Mahalanobis)
- Softmax normalization of ancestry likelihoods (Distance-to-probability transformation)
- Optional unsupervised reference clustering (K-means)
- Spatial smoothing (HMM / Viterbi)
Output:
- Global ancestry fractions
- Local ancestry assignments
- Distance-derived ancestry probability matrices
- Smoothed ancestry trajectories
- Uses discrete reference labels (
--labels) - Performs supervised ancestry classification
- KORUS learns ancestry cluster structure from categorical population labels and performs window-level classification by minimizing Mahalanobis distance to class-specific distributions in PCA space
- This framework assumes each reference genome belongs predominantly to one ancestry class
- Uses fractional ancestry supervision (
--fractions) - Supports admixed reference modeling
- Instead of learning discrete ancestry clusters from hard assignments, KORUS estimates ancestry distributions using weighted contributions from admixed reference genomes
- Partitions the reference panel into
--cK-means clusters and uses the resulting cluster assignments as pseudo-labels for ancestry inference - Operates without explicit ancestry labels
- The inferred clusters represent data-driven ancestry groups rather than predefined ancestry categories
git clone https://github.com/birollab/korus.git
cd korus
# Ensure the KORUS repository is on your PATH
export PATH=$(PWD):$PATH
conda install -c conda-forge -c bioconda numpy pandas scikit-learn matplotlib plotly btllib ntroot snakemake ntcard ntstatKORUS was developed and tested on:
- Rocky Linux 9.6 (Blue Onyx)
- Python 3.12.3
- Python >= 3.9
- btllib >= 1.7
- snakemake
- ntCard >= 1.0.1
- ntStat
- numpy
- pandas
- scikit-learn
- matplotlib
- plotly
- packaging
- ntRoot >= 1.2.2
Input reference/query reads in FASTQ format
See tools/README for instructions for generating this file from a VCF file.
chr pos allele kmer
e.g.,
10 11501 REF CCAGCGGTGTCCGGGAGCCTAGCGGCGCGTGTGCAGCGGCCAGTGCACCTGCTCT
10 11501 ALT CCAGCGGTGTCCGGGAGCCTAGCGGCGAGTGTGCAGCGGCCAGTGCACCTGCTCT
sample ancestry
ERR1 EUR
ERR2 AFR
Can be generated using ntRoot
sample EAS SAS AMR AFR EUR
ERR1 0.1961 0.0105 0.7233 0.0595 0.0105
ERR2 0.0718 0.0298 0.5814 0.2347 0.0823
KORUS provides a single-entry driver script to run all steps in the pipeline for a single query sample:
usage: korus [-h] --reads READS [--report_mode {iframe,embed}] --kmer_file KMER_FILE -k {45,55}
[--window WINDOW] [-t T] [--mode {hard,soft,unsupervised}] [--c C] [--global_pcs GLOBAL_PCS]
[--local_pcs LOCAL_PCS] [--window_radius WINDOW_RADIUS] [--stay_prob STAY_PROB] [--no_hmm]
--outprefix OUTPREFIX [--report_title REPORT_TITLE] [-n] [-V] [--ref REF] [--labels LABELS]
[--fractions FRACTIONS]
End-to-end KORUS ancestry inference pipeline
options:
-h, --help show this help message and exit
--reads READS Input read prefix
--report_mode {iframe,embed}
Report layout mode [default=iframe]
--kmer_file KMER_FILE
SNV k-mer definition file
-k {45,55} Model k-mer size
--window WINDOW Window size [default 500000bp]
-t T Number of threads [default 48]
--mode {hard,soft,unsupervised}
KORUS mode (hard, soft or unsupervised)
--c C KMeans n_clusters (unsupervised mode)
--global_pcs GLOBAL_PCS
Number of PCs used for unsupervised K-means clustering
--local_pcs LOCAL_PCS
Maximum number of PCs used for local Mahalanobis ancestry inference
--window_radius WINDOW_RADIUS
Window radius [default 3]
--stay_prob STAY_PROB
HMM self-transition probability [default 0.98]
--no_hmm Disable HMM smoothing
--outprefix OUTPREFIX
Prefix for output files
--report_title REPORT_TITLE
Title for output report [KORUS Ancestry Predictions]
-n, --dry-run Print commands without executing them
-V, --version show program's version number and exit
--ref REF Override bundled reference matrix
--labels LABELS Override bundled hard-supervised labels
--fractions FRACTIONS
Override bundled soft-supervised fractions
Example command:
korus --reads SAMPLE_PREFIX --kmer_file snv_kmers.tsv -k 55 --outprefix run1 --mode hard- Run
korusEncodefor all input reference samples - runsntCard,ntStatandkorusMatrix.py
usage: korusEncode [-h] --reads READS --kmer_file KMER_FILE -k K [--window_size WINDOW_SIZE] [-t T] [-n] [-f] [-V]
korusEncode: build KORUS feature matrices from sequencing reads
options:
-h, --help show this help message and exit
--reads READS Prefix of input read files (FASTQ/FASTA/gz/bz2 compatible)
--kmer_file KMER_FILE
SNV k-mer definition file used by korusMatrix.py
-k K k-mer size
--window_size WINDOW_SIZE
Window size for matrix aggregation [default=500000]
-t T Number of threads [default=4]
-n, --dry-run Print commands without executing
-f, --force Force rerun of all rules
-V, --version show program's version number and exit
Input reads are identified using a shared prefix.Example command:
korusEncode \
--reads SAMPLE_PREFIX (Prefix of input read files (FASTQ/FASTA/gz/bz2 compatible)) \
--kmer_file snv_kmers.tsv -k 55 -t 48
- Combine all reference matrices to one single reference matrix
usage: korusAggregateMatrices.py [-h] [--matrix-list FILE] [-o FILE]
[matrices [matrices ...]]
Merge single-sample matrices with matching window sizes. Preserve input sample order and first-seen coordinate order; fill missing values with NA.
positional arguments:
matrices Input matrix paths
optional arguments:
-h, --help show this help message and exit
--matrix-list FILE File with input matrices (one per line)
-o FILE, --output FILE
Output TSV path (default: standard output; '-' also
means stdout)
Examples:
python3 korusAggregateMatrices.py sample1.tsv sample2.tsv -o merged.tsv
python3 korusAggregateMatrices.py --matrix-list matrices.txt -o merged.tsv
Each matrix must have a header: chr window_start:<size> <sample>.
This matrix can be input to korus using --ref. For usage with multi-sample KORUS runs, see below.
While the korus script can be used to run all steps using a single sample, these steps can be followed to generate a single sample matrix for analysis using the KORUS pipeline.
-
Follow the same steps as for generating a custom reference matrix (see above for details):
a. Run
korusEncodefor each input sample data, using the same parametersb. Combine all sample matrices to a combined multi-sample matrix
-
Run
korusDecode.pyto generate ancestry fraction predictions for each input sample
usage: korusDecode.py [-h] --ref REF --sample SAMPLE [--labels LABELS] [--fractions FRACTIONS] [--c C] --outprefix OUTPREFIX [--window_radius WINDOW_RADIUS]
[--require_full_window] [--stay_prob STAY_PROB] [--no_hmm] [--global_pcs GLOBAL_PCS] [--local_pcs LOCAL_PCS] [-V]
Ancestry inference with PCA + Mahalanobis window assignment
options:
-h, --help show this help message and exit
--ref REF Reference matrix TSV
--sample SAMPLE Sample matrix TSV
--labels LABELS Discrete ancestry labels TSV
--fractions FRACTIONS
Reference ancestry fractions TSV
--c C KMeans n_clusters [default 5]
--outprefix OUTPREFIX
Output prefix
--window_radius WINDOW_RADIUS
Window radius [default 3]
--require_full_window
--stay_prob STAY_PROB
HMM self-transition probability [default 0.98]
--no_hmm Disable HMM smoothing
--global_pcs GLOBAL_PCS
Number of PCs used for unsupervised K-means clustering [default 10]
--local_pcs LOCAL_PCS
Maximum number of PCs used for local Mahalanobis ancestry inference [default 10]
-V, --version show program's version number and exitFor hard supervision, use --labels, and for soft supervision use --fractions. Omitting both of these parameters will run KORUS in unsupervised mode.
Use --ref to input the reference matrix (available in directory model or use custom-built matrix).
Example command:
korusDecode.py --ref model/korusModelMatrixk55.tsv.gz --sample sampleMatrix.tsv \
--fractions korusModelLabelsFractions.tsv.gz --global_pcs 10 --local_pcs 10 \
--outprefix korus_run --stay_prob 0.98
PCA parameters:
--global_pcs specifies the number of principal components used during unsupervised K-means clustering of the reference panel. --local_pcs specifies the maximum number of principal components retained for the window-level Mahalanobis ancestry inference performed during local ancestry assignment. These parameters control distinct PCA operations and may be adjusted independently.
-
.lai_summary.tsv— ancestry fractions and probabilities for each query sample -
*.lai.tsv— local ancestry inference results per sample -
*.pca3d.html— population context (PCA embedding) -
.reference_clusters.tsv— reference sample IDs and their inferred K-means cluster assignments (unsupervised mode only) -
koruspipeline (single query sample) only:*.lai.html— interactive genome view*.report.html— combined PCA + LAI interactive visualization report (see below examples)
As part of korusDecode.py, KORUS generates interactive PCA visualizations that position the query sample in relation to reference populations in ancestry space. The visualization examples below show sample ERR3988858 from Puerto Rico.
These HTML files (*pca3d.html) allow exploration of population structure under different inference modes:
-
Hard mode: Interactive PCA (hard)
-
Soft mode: Interactive PCA (soft / fractions)
-
Unsupervised mode: Interactive PCA (unsupervised K=5) Interactive PCA (unsupervised K=7)
The end-to-end korus pipeline also produces interactive chromosomal local ancestry inference (LAI) visualizations.
These allow users to explore ancestry assignments along chromosomes or across the genome, with linked interaction to population structure views.
Reference implementation and details: https://github.com/BirolLab/ntRoot/blob/main/README.md#interactive-local-ancestry-lai-visualization-
- LAI visualization (hard mode example): Interactive LAI (hard)
KORUS generates a standalone report that integrates PCA and LAI views into a unified interface.
- KORUS report (hard mode example) Interactive report
- PCA views are produced directly by
korusDecode.py - LAI and report visualizations are generated when running the full
koruspipeline - The report provides synchronized navigation between genome view and population context
TBD
KORUS is released under the GNU General Public License v3 (GPLv3).
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 3.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
A copy of the GPLv3 license (LICENSE) can be found here: https://github.com/BirolLab/korus/LICENSE
See http://www.gnu.org/licenses/ for details.