{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121999"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121999","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Analysis and applications of k-mer based methods in bioinformatics","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_has_math":false,"creators":["Greenberg, Grant C"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Shomorony, Ilan","Milenkovic, Olgica","Veeravalli, Venugopal V","El-Kebir, Mohammed"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-12","date_published":"2023-12","updated_at":"2026-07-22T22:25:00Z","subjects":["Bioinformatics","Metagenomics","Genome Assembly","Sequence Alignment","Information Theory"],"languages":["en","eng"],"rights":["Copyright 2023 Grant Greenberg"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121999","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shomorony, Ilan","Milenkovic, Olgica","Veeravalli, Venugopal V","El-Kebir, Mohammed"]},{"key":"dc:creator","label":"Author","values":["Greenberg, Grant C"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-12","2023-11-28"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bioinformatics","Metagenomics","Genome Assembly","Sequence Alignment","Information Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Grant Greenberg"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121999"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","The student, Grant Greenberg, accepted the attached license on 2023-11-18 at 10:56.","The student, Grant Greenberg, submitted this Dissertation for approval on 2023-11-18 at 11:02.","This Dissertation was approved for publication on 2023-11-28 at 15:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19959 on 2024-03-01 at 13:14:47","Sequence data is ubiquitous in various fields of biology including genomics, transcriptomics, and proteomics. Breaking down sequences into length-k substrings (k-mers) is often useful in many analyses. In this proposal, we discuss several applications of k-mer based methods in bioinformatics, including 1) metagenomics, the study of the genomic composition of microbial communities, 2) genome assembly, the process of reconstructing a full genome from DNA sequencing reads, and 3) sequence similarity estimation. Methods that use a small k-value often consider only the overall k-mer composition of a sequence, since all possible k-mers are likely to be well represented. Interestingly, researchers have empirically observed that genomes of different bacterial species can be distinguished based on their distribution of 4-mers, or tetranucleotide frequency (TNF). Based on this phenomenon, we present an application of information theory to metagenomics binning, in which we aim to cluster many sequences (called “contigs”) from a metagenomic sample according to their genome of origin. By modeling each species as a distinct Markov process, we show that, to achieve perfect binning, the length of the contigs must scale with the inverse of the Chernoff divergence rate between the two most similar species. Furthermore, our result implies that contigs should be binned using the KL divergence rate, as opposed to the Euclidean distance often used in practice. The metagenomic binning model turns out to be useful for a new application improving bacterial genome assembly. The complexity of genome assembly is largely due to large repeats. To detect misassemblies due to reverse-complemented repeats, we propose a statistical test based on the Markov model, that predicts whether two segments come from the same strand on genome. In most cases, the test neatly partitions the genome into two segments of roughly equal length, corresponding to the segments between the DNA replication origin and terminus. We show that, in several cases where this balanced partition is not observed, the test identifies a potential inverted misassembly, which is validated by the presence of a reverse-complemented repeat at the boundaries of the inversion. Our method identifies 32 potential misassemblies in NCBI’s GenBank database, several of which are further supported by a reassembly of the read data. Methods that use a larger k-value treat each k-mer as a distinct entity, for instance in sequence similarity estimation, where exact matching k-mers are used to comparing sequences. However, the choice of the parameter k controls an important tradeoff in the task of identifying alignments: larger k-values give greater confidence in the identification of alignments but can lead to many missing alignments, particularly in the presence of significant noise. In our third application of k-mers, we introduce a new similarity estimation method that is effectively independent of the choice of k, thereby obviating the tradeoff. When estimating the similarity between two reads, instead of simply checking whether k-mers match, one checks how “lexicographically similar” the LexicHash hashes are. In our experiments on 40 PacBio datasets, the area under the Precision-Recall Curves obtained by LexicHash had an average improvement of 20.9% over MinHash, a popular method used in many sequence alignment tools."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Analysis and applications of k-mer based methods in bioinformatics"]}]}],"canonical_facts":{"dc:contributor":["Shomorony, Ilan","Milenkovic, Olgica","Veeravalli, Venugopal V","El-Kebir, Mohammed"],"dc:creator":["Greenberg, Grant C"],"dc:date":["2023-12","2023-11-28"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","The student, Grant Greenberg, accepted the attached license on 2023-11-18 at 10:56.","The student, Grant Greenberg, submitted this Dissertation for approval on 2023-11-18 at 11:02.","This Dissertation was approved for publication on 2023-11-28 at 15:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19959 on 2024-03-01 at 13:14:47","Sequence data is ubiquitous in various fields of biology including genomics, transcriptomics, and proteomics. Breaking down sequences into length-k substrings (k-mers) is often useful in many analyses. In this proposal, we discuss several applications of k-mer based methods in bioinformatics, including 1) metagenomics, the study of the genomic composition of microbial communities, 2) genome assembly, the process of reconstructing a full genome from DNA sequencing reads, and 3) sequence similarity estimation. Methods that use a small k-value often consider only the overall k-mer composition of a sequence, since all possible k-mers are likely to be well represented. Interestingly, researchers have empirically observed that genomes of different bacterial species can be distinguished based on their distribution of 4-mers, or tetranucleotide frequency (TNF). Based on this phenomenon, we present an application of information theory to metagenomics binning, in which we aim to cluster many sequences (called “contigs”) from a metagenomic sample according to their genome of origin. By modeling each species as a distinct Markov process, we show that, to achieve perfect binning, the length of the contigs must scale with the inverse of the Chernoff divergence rate between the two most similar species. Furthermore, our result implies that contigs should be binned using the KL divergence rate, as opposed to the Euclidean distance often used in practice. The metagenomic binning model turns out to be useful for a new application improving bacterial genome assembly. The complexity of genome assembly is largely due to large repeats. To detect misassemblies due to reverse-complemented repeats, we propose a statistical test based on the Markov model, that predicts whether two segments come from the same strand on genome. In most cases, the test neatly partitions the genome into two segments of roughly equal length, corresponding to the segments between the DNA replication origin and terminus. We show that, in several cases where this balanced partition is not observed, the test identifies a potential inverted misassembly, which is validated by the presence of a reverse-complemented repeat at the boundaries of the inversion. Our method identifies 32 potential misassemblies in NCBI’s GenBank database, several of which are further supported by a reassembly of the read data. Methods that use a larger k-value treat each k-mer as a distinct entity, for instance in sequence similarity estimation, where exact matching k-mers are used to comparing sequences. However, the choice of the parameter k controls an important tradeoff in the task of identifying alignments: larger k-values give greater confidence in the identification of alignments but can lead to many missing alignments, particularly in the presence of significant noise. In our third application of k-mers, we introduce a new similarity estimation method that is effectively independent of the choice of k, thereby obviating the tradeoff. When estimating the similarity between two reads, instead of simply checking whether k-mers match, one checks how “lexicographically similar” the LexicHash hashes are. In our experiments on 40 PacBio datasets, the area under the Precision-Recall Curves obtained by LexicHash had an average improvement of 20.9% over MinHash, a popular method used in many sequence alignment tools."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121999"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Grant Greenberg"],"dc:subject":["Bioinformatics","Metagenomics","Genome Assembly","Sequence Alignment","Information Theory"],"dc:title":["Analysis and applications of k-mer based methods in bioinformatics"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:00Z"}