Back to search

Cal Poly

Large Scale Kmer-Based Proteomic Analysis: An Application Towards Evolutionary Constraint Discovery

Abstract

dc:description.abstract

Large protein databases now make it possible to study short peptides across natural protein sequence space at unprecedented scale, but exhaustively counting k-mers across billions of protein sequences remains computationally difficult. This thesis develops an exact amino-acid k-mer counting method based on direct addressing, in which fixed-length amino-acid strings are encoded as base-20 integers and updated with a sliding-window recurrence. By avoiding key storage and collision resolution, this approach removes overhead inherent to hash-map-based methods when the k-mer space is sufficiently dense. A memory analysis shows when direct addressing is preferable to open-addressing hash tables, and expected-saturation calculations motivate its use for GigaRef-scale datasets up to k=9. The counting pipeline is applied to more than 557 billion overlapping 8-mers from GigaRef, producing a complete count table over all 25.6 billion possible amino-acid 8-mers. This table enables analysis of missing, rare, and frequent peptides at full sequence-space scale. We find that 6.53 billion possible 8-mers are absent from GigaRef, substantially more than expected under codon-degeneracy and observed amino-acid/dimer-frequency null models. To characterize these deviations, the thesis uses null-model analysis, logistic regression, negative-binomial neural networks, permutation feature importance, and composition-preserving permutation tests. The results show that codon degeneracy is a strong null model, while biological cost-related features explain additional variation in 8-mer occurrence and abundance. A supplementary feature-importance analysis shows that negative-binomial models with similar predictive performance can produce different feature rankings, suggesting that individual biological feature rankings should be interpreted cautiously. Finally, comparison with ProteinMPNN-generated sequences shows how exact natural k-mer counts can be used to evaluate biases in protein sequence design models. Together, these results provide evidence for structured constraints in protein sequence space and show how large-scale k-mer analysis can be used to diagnose biases in generative protein models.

Degree

thesis:*
Name thesis:degree_name
MS in Computer Science
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chak, Matthew
Contributors dc:contributor
  • Paul Anderson
  • Computer Science
  • College of Engineering

Subjects

dc:subject × 8

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.calpoly.edu/theses/3378

Chain of custody

source
Harvested from
Cal Poly
Base URL
digitalcommons.calpoly.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chak, Matthew. Large Scale Kmer-Based Proteomic Analysis: An Application Towards Evolutionary Constraint Discovery. https://digitalcommons.calpoly.edu/theses/3378