Adaptation is the central evolutionary process and is at the core of some of the greatest challenges facing humanity. HIV would likely cause nothing more than a harmless fever without the ability of the virus to adapt and eventually destroy the immune system. Cancer would be much more straightforward to treat if not for its ability to adapt to anti-cancer drugs. Malaria could be treated with cheap drugs such as Quinine instead of being one of the world's worst killers. In disease and health, we are in an arms race without fully understanding the rules of engagement. Humans have also adapted to live in harsh ecological niches, allowing them for example to digest milk sugars in adulthood, and to live at high altitudes with debilitating lack of Oxygen.

Over 83 million people live at altitudes above 2,500 meters (8,200 ft) where the oxygen levels are 25% lower than at sea level. If not adapted, residing for a long time at such a harsh environment with low oxygen level can be fatal. One of the most striking example of high-altitude adaptation is the adaptation of Tibetan highlanders, where the favored genetic material is introgressed from archaic humans similar to Denisovans. Introgression is the introduction of genetic material into a population via interspecies mating. The complex pathways involved in hypoxia tolerance also inform upon our ability to understand ischemic diseases (stroke, cardiovascular diseases), and new molecular targets for these diseases. Therefore, this natural human experiment is a wonderful system to work with.

When adaptation is genetic (inherited by offspring of adapted individuals), it leaves a variety of detectable signatures in genomes. Together with recent developments in DNA sequencing technologies in past decades, methods for detecting genomic regions under selection from population genomic data, have been actively developed. In contrast, little work has been done to identify the favored mutation in a selective sweep. Pinpointing the favored mutation among tens of thousands of other, hitchhiking, mutations is like a needle in a haystack problem.

Identifying the favored mutation can provide a more precise picture of the origin of the selection; and allows people to do functional studies to improve the overall understanding of diseases. For example, adaptation to chronic hypoxia at high altitude can suggest targets for cardiovascular and other ischemic diseases. Also, identifying the favored mutation gives a high resolution picture revealing complicated evolutionary scenarios like multiple favored mutations and adaptive introgression.

Here in this dissertation, we address the challenging but important problem of pinpointing the favored mutation in a selective sweep. We break the problem into smaller parts and very carefully craft them to accurately identify the favored mutation in a selective sweep, and also distinguish adaptively introgressed haplotypes from other models of selection.

A central goal in genomics is to identify genetic variations and their impact on underlying molecular changes that lead to disease. With the advances in whole genome sequencing, many studies have been able to identify thousands of genetic loci associated with human traits. These studies mainly focus on single-nucleotide variants (SNVs) and novel insertion and deletions in the genome, while ignoring more complex variants. Here, I consider the problem of genotyping Variable Number Tandem Repeats (VNTRs), composed of inexact tandem duplications of short (6-100 bp) repeating units that span 3% of the human genome.While some VNTRs are known to play a role in complex disorders (e.g. Alzheimer’s, Myoclonus epilepsy, and Diabetes), the majority of them have not been studied well due to computational difficulty in genotyping VNTRs on a large scale. Here, I will present our progress on developing efficient computational algorithms to profile VNTRs from high throughput sequencing data and identify possible variations within them. I applied our method to generate the largest catalog of VNTR genotypes to this date, which provides insights into the landscape of VNTR variations in different populations. I show the contribution of tandem repeats in mediating expression levels of key genes with known associations to neurological disorders and familial cancers, and argue the causality of this relation. Finally, I will describe our efforts to directly understand the impact of these variations on human phenotypes, which improves our understanding of genetic architecture of complex diseases.

South American populations have a complex admixture history. The earliest Native Americans are known to have migrated into the Americas as early as 14000 years ago. The region saw large scale migrations from European colonial powers starting early 1500s. In just a couple of centuries the entire Western hemisphere came under the control of these European powers. These colonial powers brought millions of Africans across the Atlantic between the 1500s and 1800s through the slave trade which led to further admixture of African populations into the Americans. Due to multiple migrations events, presence of different colonial powers that followed different slave trade practices, South Americans populations have a highly heterogeneous genetic composition. We investigate the admixture history of one of the South American populations living in Cerro de Pasco, a high altitude mining town in the Andes region of Peru. Studying the admixture history of this population can give us important insights into the origins of several selection forces at play in this population. We found the Andean population to have lesser proportions of European and African ancestry as compared to the other South American populations. The timing of European and African admixture into this population was also found to be significantly different from other populations, which could be a direct result of lower European and African ancestry proportion. These results indicate a higher level of segregation between the Native Americans and the European/African populations in Peru as compared to other regions.

Circular extrachromosomal DNA (ecDNA) are a genomic lesion occurring in tumors, and represent a foundational, growing frontier in cancer biology. The discovery that focal amplifications exist in multiple topologies and arise by different mechanisms has enabled cancer researchers to study the consequences of different types of focal amplification – revealing that focal amplifications like ecDNA lead to worse patient survival. Consequently, there is an urgent need for bioinformatic methods and tools to study these focal amplifications, particularly ecDNA. This thesis describes novel tools and methods which can be used to study ecDNA, and other focal amplifications. It also demonstrates how those tools and methods can be used to profile focal amplifications across different cancer types, ultimately revealing novel biology about the structure, function and genesis of ecDNA in different contexts.

I first present two methods, AmpliconReconstructor (AR) and FaNDOM, which incorporate optical mapping data to resolve the structures of ecDNA and other focal amplifications. AR incorporates both optical mapping and NGS data and builds upon a prior method for ecDNA detection with NGS data, AmpliconArchitect (AA). FaNDOM utilizes optical mapping solely and enables the rapid characterization of large structural variants using assembled OM contigs or individual OM molecules.

I also describe the landscape of ecDNA in oropharyngeal squamous cell carcinoma, demonstrating that both human and hybrid human-viral ecDNA exist and are associated with distinct patterns of transcriptional splicing. Visualizations of the rearranged ecDNA structures and overlaid transcription-level data reveal the overexpression of genes carried on ecDNA.

Lastly, I describe the genesis of ecDNA in Barrett’s esophagus, the precursor tissue of esophageal adenocarcinoma. We utilized methods for profiling ecDNA, such as AmpliconClassifier, to demonstrate that ecDNA exist in pre-cancerous tissue, are associated with worse histology, that they are subsequently found again in cancer, and that they tend to undergo positive selection during the malignant transformation. These findings solidify ecDNA as a potent driver of cancer, and not an opportunistic passenger.

Next Generation Sequencing (NGS) and other deep sequencing technologies provide information on transcribed regions, splicing events, and single nucleotide variants in a variety of cellular conditions. The advances of this genomic technologies lead us to have better understanding about the cancer including molecular subtype, cancer progression, and biomarker discovery, but

the complexity, redundancy, and errors in genomic data make it difficult to investigate aberrant genes using only genomic approaches. Combination of proteomic and genomic technologies called proteogenomics are increasingly being employed. Various strategies have been employed to allow the usage of large-scale NGS data, however, serious methodological challenges remain, especially in

the identification of multiple mutational variants, structural variations, or immune system genes even if they play an important role in cancer. This dissertation introduce the integrative proteogenomic method that extends the limit of proteogenomic searches to identify multiple variant peptides as well as immunoglobulin gene variations using advanced RNA-seq read assembly method. The result

provide thousands of aberrant peptides observed in colorectal cancer and extensive characterization of tumor immune response. The result demonstrate the presence of co-expressed pair of antibody and aberrant peptides, and show that these pairs are correlated with survival time of the individuals.

While genomics approaches are important in studying host phenotype alterations in response to environmental changes or disease, proteomics approaches offer a complementary perspective by providing a direct readout of expressed functional pathways. Proteogenomic strategies utilizing RNA-sequencing data to construct splice graph databases have been used in a variety of applications to identify novel splice junctions and mutated peptides. The work in this dissertation begins with the integration of splice databases into a proteogenomic pipeline for the validation of the recently released annotation of the Atlantic salmon genome, and the validation of primary hepatocytes as in vitro models for salmon toxicity studies. Searching in-house generated LC-MS/MS datasets against splice databases constructed from publicly available and in-house-generated salmon transcriptomics data, our proteogenomic pipeline identified 183 events in support of 71 transcript predictions. These included novel genes, corrections to current annotations, and support for Ensembl transcripts. In addition to host-expressed proteins, microbial-expressed proteins can also alter host phenotype. In the absence of prior taxonomic information, tandem mass spectra would be searched against large pan-microbial databases, requiring heavy computational workload and reducing sensitivity. Using both software and algorithmic methods, we developed ProteoStorm, an efficient database search framework for large-scale metaproteomics studies, that significantly reduced runtime from 22 weeks to 9.7 hours while retaining 96% of peptide identifications when compared to MSGF+. A reanalysis of a urinary tract infection dataset revealed a complex pattern of polymicrobial expression, including previously identified microbes. In the final chapter, we used transcriptomics data from TCGA to identify a set of genes that may be involved in the maintenance of ecDNA amplicons in cancer. Specifically, we applied the Boruta algorithm, which incorporates the Random Forest classifier for feature selection, to a gene expression matrix of samples classified as ecDNA positive or negative, and selected 408 Core genes predictive of ecDNA status. We further extended the list with 235 highly co-expressed genes using hierarchical clustering, resulting in a total of 643 CorEx genes. Subsequent gene set enrichment analysis revealed an up-regulation of biological processes involved in cell cycle, cell division, and DNA damage response, and a down-regulation of immune system processes.

Optical mapping is a DNA physical mapping technique that can measure large-scale structural variation in genomes and enables more accurate completion of genome assemblies. Particularly, we focus on the case where optical mapping is used to complete genome assembly on pre-identified segments such as may be found in a breakpoint graph. In this work we study methods for aligning optical map contigs with reference genome segments. This work introduces a novel method for optical map alignment that outperforms existing methods for aligning breakpoint graph reference segments to assembled optical map contigs. Also discussed are some additional modifications that can be made to the method.

With continuing reductions in the cost of genome sequencing, and the advent of new sequencing technologies, it has become a routine process to sequence genomes in experiments across different fields of biology in order to study the foundations of life. Collecting multi-omics data is now an integral part of studying the human health and underlying genetic cause of diseases. Genome sequencing is extensively used to study the evolution of life and how different species are genetically related, and it is becoming an important tool to monitor the health of ecosystems and study the dynamics of biodiversity in this era of rapid climate change. As large datasets of genomic data become available through worldwide consortia and collaborative efforts, an important challenge is processing and interpreting these massive datasets. In this dissertation, I present a collection of statistical and algorithmic methods to address different computational problems faced in using genome sequencing data to study the function and properties of genome and its variation across species. In the first part of this dissertation, I describe the method we developed to address the problem of statistical significance of overlap between genome annotations--the assignment of function to specific genomic regions, which is a foundational effort of modern biology. To the best of our knowledge, the p-value computation for sets of overlapping intervals has been limited either to permutation tests that do not scale to computation of small p-values or simple parametric tests such as hypergeometric or binomial tests that are based on simplifying assumptions about the length and structure of intervals. Our method, however, formulates a null model where the size of intervals and their relative arrangement are considered when the significance of overlap is evaluated. In the second part, I introduce the idea of using whole genome sequencing reads at low coverage--genome skims--without requiring any genome assembly or alignment. We have developed methods to compute genomic distances between genome skims to use them for sample identification and phylogenetic placement, and to estimate genomic parameters such as genome length and repeat content of the genome to lay the foundation for accurate assessment of genetic biodiversity.