Mathematical words in complete genomes are explained by near-periodic repeats and sequence composition
Code accompanying the paper Mathematical words in complete genomes are explained by near-periodic repeats and sequence composition (citation).
Words generated by mathematical rules (Fibonacci, Tribonacci, Thue–Morse, period-doubling and others) can be found in DNA once each base is read as a bit. This repository tests whether such matches are specific to the generating rule, or whether any word of the same shape (the same length, composition and run structure, or the same near-periodic repeat) occurs just as often.
The analysis runs on seven telomere-to-telomere genomes, the human reference T2T-CHM13v2.0 and the six apes of the T2T Primates project (chimpanzee, bonobo, gorilla, Sumatran orangutan, Bornean orangutan and siamang), and on 100 NCBI RefSeq reference genomes each of bacteria, archaea and viruses (307 genomes in total). Every genome is analysed with the same words, encodings, decoys (matched control words), seeds and settings.
- Only short prefixes occur. Of 111 prefixes from 8 word families, none longer than 81 bits occurs in any of the seven genomes. In the human genome the 81-bit Tribonacci prefix is found once (RY encoding), and the next longest matches are 44 bits. Beyond about 32–44 bits a genome of this size stops producing chance matches.
- Apparent enrichment is large but misleading. In each genome, 36–43 of the 333 word × encoding combinations occur more often than a Markov-1 background predicts (q < 0.05; 40 in the human genome). The largest ratios belong to long, nearly periodic words with few occurrences.
- No word beats its decoys. Compared with decoys of the same shape, no word is enriched after multiple-testing correction, in any genome.
- The hits are repeats. All 3,772 loci of the most enriched words in the human genome were read again from the genome. They lie mostly in short, imperfect tandem repeats (median self-match 0.82) whose period matches the word's own near-period.
- One outlier, explained by its repeat. Tribonacci (isolate_0) T6 (44 bits) sits at the resolution limit of the decoy test (p = 1/101). In all seven genomes it occurs about as often as its own exact period-13 repeat. Its loci are dinucleotide microsatellites interrupted every 11–13 bp.
- Same result in every primate. The outcome for each word is reproduced from human to siamang (Spearman ρ = 0.52–0.84 between the p-values in each ape and in human). Where the genomes differ, the differences follow their repeat content: for example, an excess of short Baum–Sweet and period-doubling prefixes in the African great apes, and of a Tribonacci prefix in the two orangutans.
- Same result in bacteria, archaea and viruses. In 300 compact genomes the Markov-1 background flags up to 21 combinations per genome (1,093 in the bacteria, 975 in the archaea, 42 in the viruses), led by short, overlap-free words such as the 16-bit Thue–Morse prefix in WS (up to 11-fold). Against decoys, none of the 27,000 testable word × encoding tests is significant after correction (smallest q = 0.56, 0.56 and 0.69), and Thue–Morse and period-doubling have fewer loci than their decoys. Words longer than 34 bits are almost absent, and the primate outlier Tribonacci T6 occurs in none of these genomes.
-
Encode each genome as bits. Each base is mapped to 0/1 in three ways:
encoding 1 0 RY (purine/pyrimidine) A, G C, T WS (strong/weak) C, G A, T MK (amino/keto) A, C G, T Every word is searched in four forms (word, complement, reverse and reverse complement), which covers both strands in all three encodings. Matches never cross gaps (N) or chromosome boundaries. Only the assembled chromosomes are analysed. Unplaced and unlocalised scaffolds and the mitochondrion are excluded, and in bacteria and archaea so are plasmids. Viral genomes are analysed with all their segments.
-
Scan (
pattern_genome.py). Count exact occurrences of prefixes of 13–10,000 bits of 8 families. Merge overlapping hits into merged occurrences and compare them with i.i.d. and Markov-1 expectations (Poisson p-values, Benjamini–Hochberg q-values per genome). This step is only a screen, because these background models produce no tandem repeats. -
Sequence context (
loci_context.py). For the enriched combinations, fetch every locus from the genome, check it and measure its tandem-repeat period. In each ape, this is done for the combinations enriched in that ape and also for those enriched in the human genome, so the same words can be compared across species. -
Shape-matched decoys (
count_genome.py). Compare 36 words (13–100 bits) with 100 run-permutation decoys each. A decoy has the same length, composition and run lengths as the real word, but its runs are in a different order. Hits within 1 kb are chained into one locus. -
Periodic decoys (
periodic_decoy.py). Compare each nearly periodic word with other repeats of the same period carrying the same number of defects, and with the word's own exact repeat. This runs under the strict rules and again without the run-length rule. -
Combine (
combine_genomes.py). Collect the results of all genomes into one table per analysis.
Empirical p-values are (1 + k) / (N + 1) (Phipson & Smyth 2010), so with 100 decoys the
smallest possible p is 1/101 ≈ 0.0099.
data/ input genomes (not included, see below)
data/sets/ the genome sets used in the paper (bacteria100, archaea100, viruses100)
src/
seqio.py FASTA reading, ACGT codes, segments between gaps
projections.py RY / WS / MK encodings and the four search forms
pattern_genome.py genome-wide prefix scan, merged occurrences, Markov expectations, p/q-values
loci_context.py DNA and tandem period of every locus of the enriched words
decoy_words.py run-permutation decoys, exact enumeration, empirical p-values
targets.py the words used in the decoy tests, with per-word seeds
count_genome.py genome-wide real-vs-decoy locus counts
periodic_decoy.py nearest period of each word and periodic decoys
split_t2t.sh splits a genome into one FASTA per chromosome (any NCBI assembly)
combine_genomes.py one table per analysis with all genomes
run_all.sh runs the full analysis, step by step, for any genome or genome set
select_genomes.py chooses the 100 bacterial, archaeal and viral genomes (fixed seed)
get_genomes.sh downloads every genome of a set from NCBI (curl)
notebooks/
make_paper_figures.ipynb main figures from the results
results_new/ written by run_all.sh
- Python ≥ 3.10 with NumPy and pandas (the paper used Python 3.13, NumPy 2.1 and pandas 2.2)
- For the figures: matplotlib, seaborn and Jupyter
- About 10 GB of free disk space for the human genome alone, or about 60 GB for all seven primate genomes; the 300 bacterial, archaeal and viral genomes need about 2 GB
- Bash (Linux or macOS);
curlandunzipto download the bacterial, archaeal and viral genomes
pip install numpy pandas matplotlib seaborn jupyterAll seven assemblies are on NCBI. The apes are the primary assemblies, version 2.1, of the T2T Primates project. Each primary assembly holds one haplotype of every chromosome plus X and Y, giving one haploid genome per species, as for T2T-CHM13.
genome (GENOMES name) |
species | NCBI accession | assembly |
|---|---|---|---|
chm13 |
Homo sapiens | GCF_009914755.1 | T2T-CHM13v2.0 |
chimpanzee |
Pan troglodytes | GCF_028858775.2 | NHGRI_mPanTro3-v2.1_pri |
bonobo |
Pan paniscus | GCF_029289425.2 | NHGRI_mPanPan1-v2.1_pri |
gorilla |
Gorilla gorilla gorilla | GCF_029281585.2 | NHGRI_mGorGor1-v2.1_pri |
sumatran_orangutan |
Pongo abelii | GCF_028885655.2 | NHGRI_mPonAbe1-v2.1_pri |
bornean_orangutan |
Pongo pygmaeus | GCF_028885625.2 | NHGRI_mPonPyg2-v2.1_pri |
siamang |
Symphalangus syndactylus | GCF_028878055.3 | NHGRI_mSymSyn1-v2.1_pri |
Place the human genome in data/ and the ape genomes in data/apes/. The file names must
stay as NCBI provides them:
data/GCF_009914755.1_T2T-CHM13v2.0_genomic.fna
data/apes/GCF_028858775.2_NHGRI_mPanTro3-v2.1_pri_genomic.fna
data/apes/GCF_029289425.2_NHGRI_mPanPan1-v2.1_pri_genomic.fna
data/apes/GCF_029281585.2_NHGRI_mGorGor1-v2.1_pri_genomic.fna
data/apes/GCF_028885655.2_NHGRI_mPonAbe1-v2.1_pri_genomic.fna
data/apes/GCF_028885625.2_NHGRI_mPonPyg2-v2.1_pri_genomic.fna
data/apes/GCF_028878055.3_NHGRI_mSymSyn1-v2.1_pri_genomic.fna
To download all seven from the NCBI FTP site:
mkdir -p data/apes
base=https://ftp.ncbi.nlm.nih.gov/genomes/all/GCF
get() { # get <accession> <assembly name> <folder>
local a=$1 n=$2 d=$3 num=${1#GCF_}
local path=$base/${num:0:3}/${num:3:3}/${num:6:3}/${a}_${n}/${a}_${n}_genomic.fna.gz
wget -c -P "$d" "$path" && gunzip -f "$d/${a}_${n}_genomic.fna.gz"
}
get GCF_009914755.1 T2T-CHM13v2.0 data
get GCF_028858775.2 NHGRI_mPanTro3-v2.1_pri data/apes
get GCF_029289425.2 NHGRI_mPanPan1-v2.1_pri data/apes
get GCF_029281585.2 NHGRI_mGorGor1-v2.1_pri data/apes
get GCF_028885655.2 NHGRI_mPonAbe1-v2.1_pri data/apes
get GCF_028885625.2 NHGRI_mPonPyg2-v2.1_pri data/apes
get GCF_028878055.3 NHGRI_mSymSyn1-v2.1_pri data/apesGzipped files also work, and other locations can be set with T2T=/path/to/file and
APES=/path/to/folder.
The split step writes one FASTA per chromosome to data/t2t_chroms/ (human) or
data/apes/chroms/<genome>/ (apes), about 3 GB per genome. Alongside the FASTA files it
writes:
records.tsv, which links NCBI record IDs to chromosome names (e.g.NC_060925.1↔chr1);skipped.tsv, which lists the records left out.
Records whose header matches EXCLUDE (default unlocalized|unplaced|mitochondri) are
left out of every step. In the v2.1 assemblies these are five unplaced scaffolds in the
bonobo, four unlocalised chromosome-18 scaffolds in the Sumatran orangutan, and each
mitochondrion. This leaves 25 chromosomes per great ape and 26 for the siamang.
The 300 genomes are NCBI RefSeq reference genomes at the level of complete genome. The
lists used in the paper are in data/sets/ (bacteria100.tsv, archaea100.tsv,
viruses100.tsv; columns name, accession, organism, length_bp, gc_percent,
assembly_level). They were made with select_genomes.py, seed 1:
- bacteria and archaea: one genome per genus, so that no genus is counted twice. Ten widely used model species of each domain (e.g. E. coli K-12, B. subtilis 168, Haloferax volcanii, Sulfolobus acidocaldarius) are always included, and the other 90 genera are drawn at random;
- viruses: 25 genomes drawn at random from each quartile of genome length, so that large DNA viruses are represented as well as the many small genomes.
To reproduce the selection and download the genomes (one FASTA per genome, as
data/<set>/<accession>.fna):
python3 select_genomes.py # rewrites data/sets/*100.tsv (needs internet access)
bash get_genomes.sh bacteria100 archaea100 viruses100select_genomes.py lists the candidates as they are on NCBI at the time it is run, so a
later run can choose different genomes. To reproduce the paper, keep the lists in
data/sets/ and run only get_genomes.sh, which can be run again to resume an
interrupted download.
In bacteria and archaea, records whose header matches EXCLUDE_BACTERIA or
EXCLUDE_ARCHAEA (default unlocalized|unplaced|plasmid) are left out, so only the
chromosomes are analysed. Viral genomes are analysed with all their segments. Circular
genomes are analysed as the linear sequence deposited.
bash run_all.sh --list # list the steps and genomes
bash run_all.sh # everything, all seven genomes
GENOMES=human bash run_all.sh # the human genome only
GENOMES=apes bash run_all.sh split scan context decoys periodic
GENOMES="chimpanzee gorilla" bash run_all.sh scan # selected genomes and steps
bash run_all.sh combine # all-genome tables at the end
# bacteria, archaea and viruses: 12 genomes at a time, then one table per set
GENOMES="bacteria100 archaea100 viruses100" PARALLEL=12 \
bash run_all.sh split scan context decoys periodic combine
WORKERS=24 bash run_all.sh scan # settings via environment variablesGENOMES takes all (the default, the seven primates), human, apes, the name of a
genome set in data/sets/ (e.g. bacteria100), or a space-separated list of genome names
or accessions. Genome sets run only when named. The per-genome steps run genome by genome: all selected
steps for the first genome, then the next. Separate genomes can also be run at the same
time in different terminals, each with its own GENOMES, or with PARALLEL=n, which
runs n genomes at once and shares the WORKERS between them (one log per genome in
results/logs/run__<genome>.log; failed genomes are listed in
results/logs/parallel_failed.txt). Run combine once all genomes have finished.
| step | what it does | main output | time (12 cores) |
|---|---|---|---|
split |
one FASTA per chromosome | data/…/chroms |
~5–10 min per genome |
scan |
prefix scan, 8 families, 3 encodings, both strands | pattern_scan_*.csv |
several hours per genome |
context |
sequence context of enriched loci (needs scan; apes, bacteria, archaea and viruses also need the human scan) |
enriched_loci_context*.csv |
tens of minutes per genome |
decoys |
real vs run-permutation decoys (needs split, scan) |
decoy_test_genome*.csv |
minutes per genome |
periodic |
real vs periodic decoys, strict and without the run rule (needs split, scan) |
periodic_test_genome*.csv |
~20–40 min per genome |
combine |
one table per analysis with all genomes | all_genomes/*.csv, <set>/all_<set>/*.csv |
seconds |
A bacterial or archaeal genome takes a few minutes for all steps, a viral genome less than
a minute; the 300 genomes take a few hours with PARALLEL=12.
run_all.sh --list also shows two exploratory steps, longest and fibmod4, which run
on other sequence sets (CORPORA) and are not part of the paper. They run only when named.
Results for the human genome are written to results/, those for each ape to
results/apes/<genome>/, and the all-genome tables to results/all_genomes/. For a
genome set they go to results/<set>/<accession>/, and the tables combining the set to
results/<set>/all_<set>/ (e.g. results/bacteria100/all_bacteria100/). Each folder of
combined tables holds:
scan_all_genomes.csvdecoy_test_summary_all_genomes.csvdecoy_test_shared_wide.csvperiodic_test_summary_all_genomes.csvperiodic_test_norunrule_summary_all_genomes.csvcontext_own_summary_all_genomes.csvcontext_shared_summary_all_genomes.csvgenomes.csv
Settings (environment variables, defaults in brackets):
ROOT(repository folder)DATA[$ROOT/data]T2T(human FASTA)APES[$DATA/apes]SETS[$DATA/sets]RESULTS[$ROOT/results]GENOMES[all]WORKERS[12]PARALLEL[1]N_DECOYS[100]EXCLUDE[unlocalized|unplaced|mitochondri]EXCLUDE_BACTERIA,EXCLUDE_ARCHAEA[unlocalized|unplaced|plasmid]DECOY_MAX_LEN[auto: 100 bits, or the longest word observed in that genome if longer]PY[python3]
Each step writes a log to results/logs/<step>__<genome>.log and stops on error. Every
output file has a matching _run.json with its settings and software versions.
For a quick trial run before the full one:
GENOMES=human WORKERS=4 N_DECOYS=20 bash run_all.sh split decoysOn macOS, keep the computer awake during the long scans:
caffeinate -i bash run_all.shAfter the run, open notebooks/make_paper_figures.ipynb and run all cells. Main figures
are written to results_new/paper_figures/.
- All random choices are seeded. Decoys use seed 11 (
count_genome.py) and 23 (periodic_decoy.py), with a separate stream for each word, so adding or removing a word does not change the decoys of the others. The seeds are the same in every genome, so every genome is compared with the same decoys. The bacterial, archaeal and viral genomes were chosen with seed 1 (select_genomes.py), and the lists used are indata/sets/. - Where a word has fewer than 100 possible decoys, all of them are listed, and the smallest
achievable p-value is reported (
testablecolumn). - Benjamini–Hochberg q-values are computed separately in each genome.
If you use this code, please cite:
Kleio Papatheodorou, Michail Patsakis, Grigorios Koulouras, Dimitrios Gavalas, Ilias Georgakopoulos-Soares. Mathematical words in complete genomes are explained by near-periodic repeats and sequence composition*[Journal]*, [year]. doi: [DOI]
Please also cite the genome assemblies: Nurk et al., Science 376, 44–53 (2022) and Rhie et al., Nature 621, 344–354 (2023) for T2T-CHM13v2.0, Yoo et al., Nature 641, 401–418 (2025), doi:10.1038/s41586-025-08816-3, for the ape genomes, and NCBI RefSeq (O'Leary et al., Nucleic Acids Res 44, D733–D745 (2016)) for the bacterial, archaeal and viral genomes.
Ilias Georgakopoulos-Soares - ilias@austin.utexas.edu