Analysis and applications of k-mer based methods in bioinformatics

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Greenberg, Grant C

Contributors dc:contributor

• Shomorony, Ilan
• Milenkovic, Olgica
• Veeravalli, Venugopal V
• El-Kebir, Mohammed

• Bioinformatics
• Metagenomics
• Genome Assembly
• Sequence Alignment
• Information Theory

Statement dc:rights

• Copyright 2023 Grant Greenberg

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121999

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121999