Codon-Scale k-mer Clustering of Bacterial Genomes

PCA, UMAP, and K-Means applied to k-mer frequencies from two bacterial genomes (Caulobacter crescentus and Escherichia coli K-12 MG1655). The notebook revisits a hands-on case study from the MIT IDSS Applied Data Science Program (Mar–Jun 2024) with quantitative cluster-selection criteria, a second organism, and a UMAP comparison.

Author: Osmanjan Timtura, Ph.D. · LinkedIn

---

TL;DR

The original case study claimed that 3-letter k-mer (codon) frequencies cluster bacterial genome fragments into 6–7 groups corresponding to the 6 reading frames of the genetic code plus non-coding regions. After a quantitative silhouette-score sweep and validation on a second organism, that interpretation does not hold up. The data quantitatively supports 2–3 broad clusters, not 6–7, and the most parsimonious biological drivers are coding vs. non-coding, leading vs. lagging strand, or GC-content variation. The 3-letter k-mer scale does carry meaningfully more signal than k = 1, 2, or 4, so the qualitative claim that "codons matter" is supported; it is the cluster-count claim that needs revising.

---

Results

1 · k = 3 features carry the strongest signal across k = 1..4

PCA on standardized k-mer frequency tables across two organisms and four k values. Both organisms show the cleanest cluster structure at k = 3, consistent with a codon-scale signal.

2 · Quantitative cluster selection: silhouette analysis

Sweeping k_clusters = 2..10 and computing silhouette score on the k = 3 feature space gives a peak at k_clusters = 3 for C. crescentus and k_clusters = 2 for E. coli. The original case study's k_clusters = 7 (chosen visually) does not appear at the peak — neither here nor as a secondary maximum.

3 · K-Means at the silhouette-selected k

Using the silhouette-selected k_clusters, K-Means produces compact clusters in PC space for both organisms. The structure is real but more conservative than the original case study suggested.

4 · UMAP reveals additional structure that PCA misses

Comparing PCA (linear) and UMAP (nonlinear) projections of the same standardized k = 3 feature tables. UMAP's local-structure preservation gives noticeably cleaner separation, especially for E. coli, where PCA shows one diffuse cloud and UMAP cleanly separates two regions.

---

What this analysis does and does not establish

Does establish:

• 3-letter k-mer features carry more signal than 1, 2, or 4-letter features. The qualitative codon-scale claim of the original case study is supported.
• The cluster structure is reproducible across two phylogenetically distinct bacteria, so it is not a one-genome artifact.
• UMAP reveals more structure than PCA on the same features — this is a useful observation about method choice for k-mer biology in general.

Does not establish:

• That the clusters correspond to the 6 reading frames of the genetic code. The data quantitatively supports 2–3 clusters, not 6.
• Which biological driver (coding vs. non-coding, leading vs. lagging strand, GC content) actually produces the observed clusters. That requires aligning fragments back to a RefSeq GFF annotation — the obvious next step.

---

Reproducing the analysis

git clone https://github.com/OsmanjanTimtura/codon-discovery-pca-kmeans.git
cd codon-discovery-pca-kmeans
pip install -r requirements.txt
jupyter notebook notebooks/codon_discovery.ipynb

Or, to regenerate the figures non-interactively:

python smoke_test.py

Both genome FASTA files are committed to data/ (~5 MB total). Each genome is subsampled to 3,000 random 300-bp fragments to keep silhouette and UMAP tractable on a laptop. Full runtime is 1–2 minutes.

Repository layout

codon-discovery-pca-kmeans/
├── README.md                     (this file)
├── requirements.txt              (pinned deps)
├── smoke_test.py                 (regenerate all figures non-interactively)
├── data/
│   ├── ccrescentus.fa            (300 kb fragment, from MIT IDSS bootcamp)
│   └── ecoli_k12.fa              (4.6 Mbp full genome, NC_000913.3 from NCBI)
├── notebooks/
│   └── codon_discovery.ipynb     (analysis notebook)
└── figures/                      (regenerated by smoke_test.py)

Tools

Python 3.10+ · pandas · numpy · scikit-learn · matplotlib · tqdm · umap-learn

Provenance

The original notebook is a hands-on case study from the Making Sense of Unstructured Data module of the MIT Institute for Data, Systems and Society (IDSS) Applied Data Science Program: Data Science & Machine Learning (March–June 2024). The portfolio version in this repository adds:

• Modular, reusable functions (the original was a linear script).
• Quantitative cluster-selection via silhouette score.
• Cross-organism validation on the E. coli K-12 MG1655 reference genome (NC_000913.3, fetched via NCBI Entrez E-utilities).
• UMAP comparison alongside PCA.
• A more conservative biological interpretation supported by the quantitative findings, plus a candid limitations section.

License

MIT License — feel free to reuse for teaching, research, or any portfolio purpose.