Today, as the world is stricken by the proliferation of novel infectious pathogens, we are faced with the urgent need for new anti-infective therapeutic agents. Natural products, also known as specialized metabolites, are chemical compounds produced by living organisms and have served as an excellent source for drug discovery. Many clinically used small molecules including various antimicrobial, anticancer, antiviral, and immunosuppressant drugs, are either natural products or are inspired by them. Traditionally, natural products were discovered mostly through slow and laborious experiments that often lead to rediscovering previously known compounds.

Over the past decade, advancements in short/long-read (meta)genomics and tandem mass spectrometry (MS/MS) technologies provided an unprecedented resource for large-scale natural product discovery. In accordance with these advancements, scalable bioinformatics algorithms are required to leverage this massive data and enable analyses of natural products across thousands of samples. In this dissertation, I present several scalable computational methods for discovering novel natural products using the (MS/MS-based) metabolomics and/or (meta)genomics data.

In the first chapter, I present CycloNovo, the first algorithm for scalable de novo sequencing of MS/MS data to discover cyclic and branch cyclic peptides (referred to as cyclopeptides). Cyclopeptides constitute a diverse and biomedically important class of natural products. CycloNovo employs de Bruijn graphs, the workhorse of DNA sequencing algorithms, for efficient cyclopeptide sequencing and revealed a wealth of novel cyclopeptides, including a large hidden cyclopeptidome in the human gut.

In the following chapters, I discuss bioinformatics methods for discovering Non-Ribosomal Peptides (NRPs) that include a multitude of antibiotics and other clinically used drugs. NRPs are produced by metabolic pathways partially encoded by Biosynthetic Gene Clusters (BGCs). In the second chapter, I present NRPminer, a modification-tolerant and scalable algorithm for NRP discovery by integrating (meta)genomic and MS/MS data. NRPminer identified many novel NRPs from different origins, including novel NRPs produced by soil-associated microbes and human microbiota. Finally, I discuss the problem of identifying NRP-producing BGCs in the human gut microbiome and I show long-read metagenomic assemblies can be used to reveal many BGCs that synthesize previously unknown NRPs in the human gut microbiome.

MinHash is a popular method for genome distance estimation. However, its requirement for input data quality is relatively strict, and its performance deteriorates if the input sequences are generated from sequencers with high sequencing error rates, especially from long-read sequencers. To solve this problem, in this thesis, we use solid (frequently occurring) k-mers as input to feed MinHash, and prove the effectiveness of this solid k-mer powered MinHash by comparing its performance in genome distance estimation with regular MinHash. In addition, we also discuss how to select the optimal threshold for solid k-mers in order to make the most of our solid k-mer powered MinHash.

The recently introduced long-read sequencing technologies (such as Pacific Biosciences or Oxford Nanopore) have substantially improved genome assemblies of many organisms, including the human reference genome. The technologies are, however, facing the challenge of high read errors. In this dissertation, we describe multiple algorithms for assembly and analysis of long-read sequencing data. First, we introduce the ABruijn algorithm for long-read assembly that bypasses the expensive read error-correction step by identifying reliable k-mers in reads. We then describe the Flye package, that combines ABruijn with a new repeat graph approach that accurately resolves the genomic structure. Finally, we extend Flye to the assembly of complex metagenomic communities using long reads.

Recent advances in long-read sequencing technologies allowed generation of the first complete assembly of a human genome. They revealed previously inaccessible sequences of human centromeres and allowed analysis of their structure and evolution. We introduce centroFlye — the first algorithm for automated assembly of centromeres from error-prone long reads. We then describe TandemTools and VerityMap algorithms for quality assessment of the newly assembled regions. Afterwards, we present StringDecomposer, CentromereArchitect, and HORmon algorithms for structural and evolutionary analysis of human centromeres. We introduce LJA — the first de Bruijn-based genome assembler for accurate long reads. Finally, we describe TandemAligner —– the first parameter-free sequence alignment algorithm that introduces a sequence-dependent scoring that automatically changes for any pair of compared sequences.

Phylogenetic trees can be used to study the evolution of any sequence that evolves, including viruses. In a viral epidemic, the history of transmission events defines constraints on the evolutionary history of the viral population. The spread of many viruses is driven by social and sexual networks, and because of the relationship between their evolutionary and transmission histories, phylogenetic inference from viral sequences can be used to improve the inference of patterns of the epidemic, which in turn may be able to enhance epidemiological intervention. The simultaneous simulation of viral transmission networks, phylogenetic trees, and sequences can provide a method to observe the effects of virus model parameters on the epidemic as well as to study the accuracies and errors of transmission inference tools, but the success of such simulations relies on the existence of appropriate models. Further, the development of massively-scalable tools to analyze ultra-large datasets of viral sequences can aid epidemiologists in the real-time surveillance of the spread of disease. To enable viral epidemic simulation analyses, I developed FAVITES: a novel framework to simulate viral transmission networks, phylogenetic trees, and sequences, and I used FAVITES to study the effects of model parameters on epidemic outcomes. In an effort to better capture the unbalanced topologies commonly observed in retroviral phylogenies, I developed a novel evolutionary model (dual-birth), derived probabilistic distributions and theoretical expectations of trees sampled under the model, developed an approach to estimate model parameters given real data, and used the model to analyze Alu retrotransposons in the human genome. In order to potentially aid public health officials, I developed a scalable and non-parametric phylogenetic method of viral transmission risk prioritization, which I evaluated against current best-practice methods via simulation and real data. Lastly, I contributed to Bioinformatics education by developing multiple publicly-accessible adaptive online interactive texts.

In recent years, we have seen the advent of high-throughput sequencing technologies, providing us with the unprecedented ability to query DNA, RNA, and proteins.

We have witnessed the vast variability of molecules at the level of sequences. Disentangling this molecular variability, and describing the array of changes to molecules, is critical to understanding certain biological processes. This dissertation asks questions about certain functions, e.g., immune response and N-terminal events, and attempts to ascertain any patterns in the data.

While the N-terminus may seem like an innocuous portion of translated proteins, it in fact, harbors great variability. Despite all proteins starting with a methionine (Met), many lose this first residue, to N-terminal methionine excision (NME), exposing the second residue. Additionally, some proteins gain an acetyl group to the N-terminus. These N-terminal post-translational modifications (PTMs) make up the N-terminome.

Another biological process that introduces variability is that of the immune repertoire. B-cells, responding to an antigen, produce heavy and light chain proteins to form an antibody. These antibodies are comprised of three gene-segments, termed V, D, and J. Unlike typical exonic splicing events, VDJ somatic recombination occurs at the genomic level within B-cells. Additionally, somatic hypermutation (SHM) introduces a very large number of mutations. Thus, the population of B-cells will produce a large variety of antibody heavy and light chains, in an attempt to target an antigen. This immunoglobulin repertoire forms part of the immunome that we attempt to characterize in different projects.

Phylogenetics has been widely adopted across biology. Yet, a continuing difficulty in phylogenetics is modeling all biological processes that shape evolution while maintaining computational scalability. My dissertation focuses on several problems, in each case, developing scalable algorithms that advance biological realism. Much of the dissertation focuses on species tree reconstruction confronting discordance among evolutionary histories of genes (gene trees) for biological reasons such as incomplete lineage sorting.

Past work had already developed statistically consistent methods such as ASTRAL for species tree reconstruction given gene trees. However, these methods failed to account for gene tree error (GTE). Contracting low-support branches was a potential solution, but ASTRAL was not efficient in handling polytomies. Here, I introduce ASTRAL-III, which drastically reduces the computational complexity in handling polytomies and improves robustness to GTE. Not satisfied with the need for a contraction threshold, I also introduce weighted ASTRAL, a method that down-weights error-prune gene tree branches and further improves the accuracy. Furthermore, I propose a method called ASTERISK to infer the species tree directly from multi-sequence alignments (MSAs), forgoing the need to infer error-prone gene trees. Having dealt with gene tree errors, I turn to errors in MSAs, which can impact phylogenetic analyses. I introduce TAPER, a novel two-dimensional outlier detection algorithm that looks for errors in small species-specific stretches of MSAs. TAPER can reduce GTE by finding much of the error while removing very little data.

Another shortcoming of ASTRAL was that it failed to model gene duplication and loss (GDL). I present a new algorithm called ASTRAL-Pro to accommodate datasets with high GDL rates, showing that ASTRAL-Pro is more accurate than alternatives.

Finally, I turn to selective pressure, a process that phylogenetics often fails to model. To benchmark the performance of tools under selection, I develop DIMSIM, an efficient simulator for sequence evolution under selection. I apply DIMSIM to the B-cell affinity maturation process that involves somatic hypermutations to B-Cell sequences followed by selective pressure. My study reveals that phylogenetic reconstruction tools fail to capture key features of clonal tree expansion if applied naively but can be easily rescued by contracting short branches.

Genome assembly is the problem of reconstructing genomes from DNA sequence reads. Even the best assemblies are often fragmented due to the presence of repetitive regions in the genome. Using long, single molecule sequencing (SMS) reads can improve the contiguity of these assemblies, but still fail to resolve long repetitive regions. Furthermore, the high error rate of SMS reads poses additional difficulties for assembly, raising the question of whether the popular de Bruijn graph (DBG) approach to genome assembly can be applied to SMS reads.

First, I present ABruijn, the first genome assembler for SMS reads that follows the DBG approach. By modifying the DBG into an A-Bruijn graph, ABruijn is able to produce very polished assemblies for simple genomes such as E. coli and S. cerevisiae. However, ABruijn has some difficulties with processing very repetitive regions and very large genomes.

To address ABruijn’s shortcomings, I helped to develop Flye, a DBG-based assembler for SMS reads that can be applied to large mammalian genomes such as the human genome. Flye features a much more efficient method for resolving highly repetitive regions and also generates a repeat graph, which offers a compact representation of all of the repeats in a genome. Flye further performs steps to resolve those repeats and improve the quality of the assembly, resulting in a more contiguous assembly of the human genome compared to other state-of-the-art assemblers.

Finally, I present diploidFlye, a haplotype-aware extension of Flye that is able to phase the contigs for assemblies of diploid organisms. diploidFlye takes advantage of the repeat graph generated by Flye to efficiently identify heterozygous variants and generate haplocontigs (haplotype-specific contigs) from the reads.

Overall, this dissertation presents several novel algorithms for improving the performance of the de novo genome assembly of long SMS reads, establishing the efficacy of the DBG approach even for error-prone SMS reads and developing a state-of-the-art assembler known as Flye with many novel features for improving the overall assembly.