{"id":{"repo_id":"calpoly","oai_identifier":"oai:digitalcommons.calpoly.edu:theses-5027"},"canonical_url":"https://search.ndltd.org/etd/calpoly/oai:digitalcommons.calpoly.edu:theses-5027","repository":{"repo_id":"calpoly","name":"Cal Poly","base_url":"https://digitalcommons.calpoly.edu/do/oai/"},"display":{"title":"Large Scale Kmer-Based Proteomic Analysis: An Application Towards Evolutionary Constraint Discovery","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Chak, Matthew"],"institution":null,"degree_name":"MS in Computer Science","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Paul Anderson","Computer Science","College of Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:12:58Z","subjects":["k-mer counting","direct addressing","protein sequence analysis","Gigaref","ProteinMPNN","Bioinformatics","Computational Biology","Computational Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/3378","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.calpoly.edu/theses/3378","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.calpoly.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.calpoly.edu%3Atheses-5027","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Paul Anderson","Computer Science","College of Engineering"]},{"key":"dc:creator","label":"Author","values":["Chak, Matthew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2026-06-12T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2026-06-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["k-mer counting","direct addressing","protein sequence analysis","Gigaref","ProteinMPNN","Bioinformatics","Computational Biology","Computational Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/3378"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Large Scale Kmer-Based Proteomic Analysis: An Application Towards Evolutionary Constraint Discovery"]}]}],"canonical_facts":{"dc:contributor":["Paul Anderson","Computer Science","College of Engineering"],"dc:creator":["Chak, Matthew"],"dc:date.available":["2026-06-12T07:00:00Z"],"dc:date.created":["2026-06-01T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/3378"],"dc:subject":["k-mer counting","direct addressing","protein sequence analysis","Gigaref","ProteinMPNN","Bioinformatics","Computational Biology","Computational Engineering"],"dc:title":["Large Scale Kmer-Based Proteomic Analysis: An Application Towards Evolutionary Constraint Discovery"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["MS in Computer Science"]},"updated_at":"2026-11-19T07:12:58Z"}