Structural variants (SVs) account for a large amount of sequence variability across genomes and play an important role in human evolution and diseases. Despite massive efforts over the years, the discovery of SVs in individuals remains challenging due to the highly repetitive nature of the human genome and the existence of complex SVs. The dominant mapping-based framework for SV discovery has several drawbacks including dependence on resource intensive mapping algorithms and an increased possibility of error in repetitive regions of the genome due to ambiguous read mappings. As a result, new computational methods are needed that can genotype different types of SVs in both short and long read data with high accuracy.

In this thesis, we first propose an ultra-efficient mapping-free approach for genotyping common structural variations on short Illumina reads in Chapter 2. Our method Nebula generates databases of k-mers for catalogs of common SVs and counts these k-mers in unmapped samples to predict SV genotypes using a likelihood model of the k-mer counts. Nebula is the first method known to us that's capable of directly mapping-free SV genotyping from raw FASTQ files. We show that Nebula is not only an order of magnitude faster than mapping-based approaches for genotyping SVs, but it also has comparable accuracy to state-of-the-art approaches. Furthermore, Nebula is a generic framework that is not limited to specific types of SVs.

Next we introduce the concept of substring-free sample-specific strings (SFS) as an effective tool for comparative variant discovery between pairs of accurate long-read sequencing samples (e.g., PacBio HiFi) in Chapter 3. The SFS are sequences specific to a genome (or equivalently its sequencing reads) with regards to another genome that also do not occur as substrings of one another. We then introduce the Ping-Pong algorithm for theoretically and practically efficient extraction of SFS between a pair of target and reference samples by building an FMD index of the reference sample and querying the reads of the target sample against this index. Ping-Pong is a mapping-free method and is therefore not hindered by the shortcomings of the reference genome and mapping algorithms. We show that Ping-Pong is capable of accurately finding SFS representing nearly all variation (>98%) reported across pairs or trios of WGS samples using PacBio HiFi data.

Finally in Chapter 4 we introduce SVDSS, a novel hybrid method for discovery of SVs from PacBio HiFi reads that combines the SFS concept with partial-order alignment (POA) and local assembly to yield highly accurate SV predictions. With experiments on three human samples, we show that SVDSS outperforms state-of-the-art methods for SV discovery on long-read data and achieves significant improvements in recall and precision particularly when discovering SVs in repetitive and traditionally difficult regions of the genome.

Abstract: Neurodevelopmental Disorders (NDDs), including Autism Spectrum Disorder (ASD) and Intellectual Disability (ID) are disorders that are affected by the developing human brain. The brain has hundreds to thousands of unique cell types within it, and by studying the cell types that are critical in NDDs, this will lead to a greater understanding of the mechanisms of NDDs in the developing brain. Single-cell RNA-seq (scRNA-seq) can shed light on the importance of the many cell types involved in NDDs and the normal brain development process, as it can provide more fine-grained details on individual cells in comparison to bulk RNA sequencing. This thesis project proposes a mathematical objective function that identifies critical cell types for a set of genes and a scRNA-seq dataset. Our objective function was able to identify critical cell types previously identified in literature. A set of ASD risk genes were used as module genes, as well as scRNA-seq data taken from the developing human neocortex for input. Excitatory deep layer neurons (glutamatergic neurons) and microglial cells were found to be of interest with these module genes. A second and third set of module genes were tested, with one being composed of genes indicated in ASD and ID, and the other being composed of genes indicated in both disorders but that are also in synaptic function, long-term potentiation, and calcium signaling that are found to be more highly expressed at postnatal time points. For these sets of module genes, excitatory deep layer neurons (glutamatergic neurons), and cycling progenitors in the G2/M and S phases were found to be critical. Additionally, we show that cells within the same defined cell type (here done using tSNE) have a higher average maximum similarity with each other than with cells outside of their cell type. In contrast, for a random selection of cells, there is a higher average maximum similarity of cells between groupings, rather than in the same grouping. This indicates that the cell types utilized in this project are in fact clustered properly together. In conclusion, utilizing scRNA-seq in conjunction with module genes enables us to identify critical cell types applicable to NDDs.

Neurodevelopmental disorders (NDDs), such as autism spectrum disorder (ASD), intellectual disability, and developmental disability are genetically and phenotypically heterogeneous disorders that display high comorbidity and relatively high heritability. Although non-coding and common variation contribute to a substantial proportion of all NDD cases, rare coding genetic variation has proved invaluable to the identification of NDD risk genes. NDD cases possess a significantly larger burden of de novo variation, a form of rare genetic variation that is not inherited from either parent, compared to unaffected controls. The enrichment of non-synonymous de novo coding variation in cases compared to controls enables the discovery of genetic modules, the early prediction of a subset of affected cases at low false positive rates, and the identification of critical cell-types relevant to specific modules. Modules are networks of genes that participate in a certain biological function. The module discovery tools MAGI-S and its extension MAGI-MS are introduced in Chapter 1, which identify modules that can dissect specific phenotypes given ‘seed’ gene(s) that are members of biological pathways of interest. MAGI-S and MAGI-MS provide evidence of the dissection of the epilepsy phenotype from more general NDD phenotypes and the enrichment of non-synonymous de novo mutation in cases compared to controls among module genes. In Chapter 2, a shallow neural network (SNN) with a false positive rate (FPR) minimizing loss function uses non-synonymous de novo mutation and features related to genic constraint and conservation to identify a small subset of NDD cases at very low FPR. Compared to traditional machine learning techniques and heuristics derived from genic constraint metrics and known NDD risk genes, the SNN achieves greater true positive rates (TPR) at near-zero FPR and ranks candidate NDD risk genes. Given modules such as those generated by MAGI-S and MAGI-MS and single-cell expression data, MoToCC identifies groups of cells that selectively express the module genes. MoToCC is a linear programming approach that maximizes the gene co-expression amongst selected cells with consideration of cell-cell similarity and K-nearest neighbor connectivity. By allowing users to vary the number of cells to return as a solution, cell-types relevant to the module and shifting percent composition can be visualized at varied scales, as shown in Chapter 3 for three NDD modules. The described computational tools seek to use the predictive power of de novo coding variation to further characterize the genetic etiology of neurodevelopmental disorders and lead to improvements in the well-being of affected patients.