The Anthropocene is broadly defined as the geologic epoch where Earth’s ecosystems have been deeply impacted by humans. This impact is especially notorious on the phenotypes of plants and animals that were domesticated in the last 10,000 years, so much so that it is sometimes difficult to identify their corresponding wild ancestors. Strong selection for traits of interest to humans has left deep marks in the genomes of these species, which has allowed the identification of mutations associated with particular phenotypes. Furthermore, DNA extracted from archaeological samples opens a window into the past and can reveal early farming and cultural preferences. I will present examples of the traces of human activity in genomes of both domesticated species and wild species of commercial interest, and suggest how this information can be used in conservation efforts.

Gene duplication is one of the main drivers of evolution. It is well-known that copies arising from duplication can undergo multiple evolutionary fates, but little is known on their relative frequency, and on how environmental conditions affect it. In this paper we provide a general framework to characterize the fate of duplicated genes and formally differentiate the different fates. To test our framework, we simulate the evolution of populations using aevol, an in silico experimental evolution platform. When classifying the resulting duplications, we observe several patterns that, in addition to confirming previous studies, exhibit new tendencies that may open up new avenues for a better understanding the role of duplications.

The alternative processing of eukaryote genes allows the production of multiple distinct transcripts from a single gene, thereby contributing to transcriptome diversity. Recent studies suggest that more than 90% of human genes are concerned, and the transcripts resulting from alternative processing are highly conserved between orthologous genes.

In this paper, we present a model to define orthology and paralogy relationships at the transcriptome level, and an algorithm to infer clusters of orthologous and paralogous transcripts. Gene-level homology relationships are used to define different types of homology relationships between transcripts and a Reciprocal Best Hits approach is used as a basis to infer clusters of isoorthologous and recent paralogous transcripts.

The method was applied to transcripts of gene families from the Ensembl-Compara database. The results are consistent with the results of previous studies on the comparison of orthologous gene transcripts. The results also provide evidence that searching for conserved transcripts beyond orthologous genes is likely to be informative. The results obtained on the Ensembl-Compara gene families are available in the TranscriptDB database accessible at https://github.com/UdeS-CoBIUS/TranscriptOrthology.

This work is about comparing two genomes S and D over the same set of gene families, such that S is singular (has one gene per family), while D is duplicated (has two genes per family). Considering some underlying model, that can be simply the minimization of breakpoints or finding the smallest sequence of mutations mimicked by the double-cut-and-join (DCJ) operation, the double distance of S and D aims to find the smallest distance between D and any element from the set 2S, that contains all possible genome configurations obtained by doubling the chromosomes of S. The breakpoint double distance of S and D is an easy problem that can be greedily solved in linear time. In contrast, the DCJ double distance of S and D was proven to be NP-hard. The complexity space between these two extremes can be explored with the help of an intermediate family of problems, the sigma_k distances, defined for each k ∈ {2, 4, 6, ..., ∞}, in a way such that the sigma_2 distance equals the breakpoint distance and the sigma_∞ distance equals the DCJ distance. With this class of problems it is possible to investigate the complexity of the double distance under the sigma_k distance, increasing the value k in an attempt to identify the smallest value for which the double distance becomes NP-hard, indicating the point in which the complexity changes. In our more recent work we have proven that, for the particular case in which genomes can only be composed of circular chromosomes, both sigma_4 and sigma_6 double distances can be solved in linear time. Here we present a non-trivial extension of these results to genomes including linear chromosomes.

The Double Cut and Join (DCJ) model is a simple and powerful model for the analysis of large structural rearrangements. After being extended to the DCJ-indel model, capable of handling gains and losses of genetic material, research has shifted in recent years toward enabling it to handle natural genomes, for which no assumption about the distribution of markers has to be made. Whole Genome Duplications (WGD) are events that double the content and structure of a genome. In some organisms, multiple WGD events have been observed while loss of genetic material is a typical occurrence following a WGD event. Natural genomes are therefore the ideal framework, under which to study this event. The traditional theoretical framework for studying WGD events is the Genome Halving Problem (GHP). While the GHP is solved for the DCJ model for genomes without losses, there are currently no exact algorithms utilizing the DCJ-indel model, nor algorithms that are capable of handling natural genomes. In this work, we address this issue and present a simple and general view on the DCJ-indel model that we apply to derive an exact polynomial time and space solution for the GHP on genomes with a bounded number of genes per family. We then generalize this solution as an integer linear program (ILP) to an exact solution for the NP-hard GHP for natural genomes.

Reconstructing the complete phased sequences in human and non-human species is important in medical, biosustainability, and comparative genetics, for understanding the genetic basis of complex traits. The unprecedented advancements in sequencing technologies have opened up new avenues to reconstruct these phased sequences that would enable a deeper understanding of molecular, cellular, and developmental processes underlying complex diseases and bio-based chemical production. Despite these interesting sequencing innovations, the reference genomes of humans and microbes like fungi are unphased, and thus annotating novel expression and methylation results are incomplete and inaccurate, which affects the interpretation of molecular genetics and epigenetics of diseases and bio-based chemical production. There is a pressing need for streamlined, production-level, easy-to-use computational approaches that can reconstruct high-quality chromosome-scale phased sequences, and that can be applied to human genomes and microbes at scale.

In this talk, first, I will present an efficient combinatorial phasing model that leverages new long-range Strand-specific technology and long reads to generate chromosome-scale phasing. Second, I present an efficient algorithm to perform accurate haplotype-resolved assembly of human individuals. This method takes advantage of new long accurate data types (PacBio HiFi) and long-range Hi-C data. We for the first time can generate accurate chromosome-scale phased assemblies with base-level-accuracy of Q50 and continuity of 25Mb within 24 hours per sample, therefore, setting up a milestone in the genomic community. Third, I will present the generalized graph-based method for phased assembly of cancer genomics that produced the first precise somatic and germline structural variant landscape required for better drug therapeutics.

In summary, my works efficiently and robustly combine data from a variety of sequencing technologies to produce high-quality phased assemblies. These computational methods will enable high-quality precision medicine and facilitate new and unbiased studies of human (and non-human) haplotype variation which are currently goals of the Human Genome Reference Project, the European Reference genome atlas, and the Global Alliance of biofoundries.

The recombination problem is inspired by genome rearrangement events that occur in bacteriophage populations. Its goal is to explain how to transform a bacteriophage population into another using the minimum number of recombinations. Here we show that the general combinatorial problem is NP-Complete, both when the target population contains only one genome of unbounded length. and when the size of the genomes is bounded by a constant. In the first case, the existence of a minimum solution is shown to be equivalent to a 3D-matching problem, and in the second case, to a satisfiability problem. These results imply that the comparison of bacteriophage populations using recombinations will have to rely on heuristics that exploit biological constraints.

Chromosomal inversions play an important role in genome evolution, speciation and adaptation of organisms to diverse environments. Mapping and characterization of inversion breakpoints can be useful for describing mechanisms of rearrangements and identification of genes involved in diversification of species. Mosquito species of the Maculipennis Subgroup include dominant malaria vectors and nonvectors in Eurasia but breakpoint regions of inversions fixed between species have not been mapped to the genomes. Here, we use the physical genome mapping approach to identify breakpoint regions of X chromosome inversions fixed between Anopheles atroparvus and the most widely spread sibling species An. messeae. We mapped breakpoint regions of two nested fixed inversions (~13 Mb and ~10 Mb) using fluorescence in situ hybridization of 53 gene markers with polytene chromosomes of An. messeae. The DNA probes were designed based on gene sequences of the annotated An. atroparvus genome. The two inversions resulted in five syntenic blocks, of which only two syntenic blocks (encompassing at least 179 annotated genes in the An. atroparvus genome) changed their position and orientation in the genome. Analysis of the An. atroparvus genome revealed enrichment of DNA transposons in sequences homologous to three of four breakpoint regions suggesting the presence of “hot spots” for rearrangements in mosquito genomes. Our study demonstrated that the physical genome mapping approach can be successfully applied to identification of inversion breakpoint regions in insect species with polytene chromosomes.

We present a proof of principle for an new kind of stepwise algorithm for unrooted binary gene-order phylogenies. This method incorporates a simple look-ahead inspired by Dollo's law, while simultaneously reconstructing each ancestor (HTU). We first present a generic version of the algorithm illustrating a necessary consequence of Dollo characters. In a concrete application we use generalized oriented gene adjacencies and maximum weight matching (MWM) to reconstruct fragments of monoploid ancestral genomes as HTUs. This is applied to three flowering plant orders while estimating phylogenies for these orders in the process. We discuss how to improve on the extensive computing times that would be necessary for this method to handle larger trees.

The advances in variational inference are providing promising paths in Bayesian estimation problems. These advances make variational phylogenetic inference an alternative approach to Markov Chain Monte Carlo methods for approximating the phylogenetic posterior. However, one of the main drawbacks of such approaches is the modelling of the prior through fixed distributions, which could bias the posterior approximation if they are distant from the current data distribution. In this paper, we propose an approach and an implementation framework to relax the rigidity of the prior densities by learning their parameters using a gradient-based method and a neural network-based parameterization. We applied this approach for branch lengths and evolutionary parameters estimation under several Markov chain substitution models. The results of performed simulations show that the approach is powerful in estimating branch lengths and evolutionary model parameters. They also show that a flexible prior model could provide better results than a predefined prior model. Finally, the results highlight that using neural networks improves the initialization of the optimization of the prior density parameters.

It is widely known that cancer drug resistance inevitably leads to treatment failure through clonal selection. Therefore, quantifying the clonal evolution using experimental model systems can hold a great promise in designing evolutionarily informed therapies, and thus, in predicting drug response. In this talk, I will present our quantitative experimental model system that contributed to the understanding of collateral drug sensitivity with its direct link to overcome the drug resistance in cancer. More specifically, high-complexity cellular barcoding allowed us the identification of the resistance mechanisms that was ultimately driven by the presence and emergence of multiple pre-existing and de novo resistant barcodes. Overall, our work highlighted evolutionary trade-offs and provided an opportunity to exploit the tumour’s vulnerabilities. Finally, I will present establishment of molecularly characterized Patient-Derived Organoids (PDOs) from metastatic colorectal cancer patients.

Ancient genomes have become a major source of information on human history as well as biological evolution. Over the last decade, work from our group and others using human palaeogenomes has discovered diverse interregional mobility patterns in West Eurasia since the Neolithic period, some of which align with archaeological data while others are novel. Genetic estimates of kinship among co-buried individuals in archaeological sites are likewise revealing yet unknown social practices in prehistoric societies, underscoring the diversity of human social organizations. We have been further using palaeogenomes to study copy number variations and negative selection in ancient populations, as well as pathogens infecting ancient humans. Meanwhile, the majority of the published 3,000 ancient shotgun genomes are of low quality (<0.5x coverage) and susceptible to diverse technical issues, from reference allele biases to coverage variability that limit reliable inference. I will be presenting some simple computational approaches we have been developing to mitigate these biases and to increase the information extracted from palaeogenomes.

Tree comparison costs are sophisticated tools used to compare the results of different phylogenetic hypotheses and reconstruction methods and to evaluate the robustness of a tree to data perturbations. The Robinson-Foulds distance is a widely used measure for comparing the topologies of two trees, but it is highly sensitive to tree error. Consequently, tree differences may be over-estimated, leading to incorrect inference. An approach to overcome this shortcoming is the Cluster Affinity distance, which is a refinement of the Robinson-Foulds distance. These distances are symmetric and thus designed to compare the same type of trees. However, it is more common to compare different types of trees, such as gene trees compared with species trees, or the integration of different datasets into a supertree: these comparisons are inherently asymmetric. Here, we introduce the asymmetric Cluster Affinity cost, a relaxation of the original Affinity cost to compare heterogeneous trees. We demonstrate that the characteristics of this cost are similar to the symmetric Cluster Affinity distance. Further, for the asymmetric affinity cost we describe efficient algorithms, derive the exact diameters, and use these to standardize the cost to be applicable in practice.

Investigating the mutational history of tumor cells is important for understanding the underlying mechanisms of cancer and its evolution. Now that the evolution of tumor cells is modeled using labeled trees, researchers are motivated to propose different measures for the comparison of mutation trees and other labeled trees. While the Robinson-Foulds distance is widely used for the comparison of phylogenetic trees, it has weaknesses when it is applied to labeled trees. Here, k-Robinson-Foulds dissimilarity measures are introduced for labeled tree comparison.

Modeling reticulate evolution is an important problem in evolutionary biology. Phylogenetic network is an evolutionary model that uses a network (instead of a tree) to model an evolutionary history of species with reticulate evolution (e.g., hybrid speciation or horizontal gene transfer). While theoretically interesting, it is often computationally challenging to perform evolutionary analysis using phylogenetic networks. Tree-child network is a kind of phylogenetic network with structural constraints. A main advantage of using tree-child network is that tree-child network often allows more efficient computation than general phylogenetic networks. In this paper, we present several computational approaches for lower bounding the minimum number of reticulations in tree-child networks that display a set of given rooted binary phylogenetic trees. There exists methods for calculating such lower bounds for general phylogenetic networks. But these methods do not scale well for large data. Through simulation, we demonstrate that the new lower bounds on minimum reticulation for tree-child network can be computed practically for large data. Also, these bounds can provide useful information for better understanding reticulate evolution.

Phylogenetic networks are increasingly being considered as better suited to represent the complexity of the evolutionary relationships between species. One class of phylogenetic networks that has received a lot of attention recently is the class of orchard networks, which is composed of networks that can be reduced to a single leaf using cherry reductions. Cherry reductions, also called cherry-picking operations, remove either a leaf of a simple cherry (sibling leaves sharing a parent) or a reticulate edge of a reticulate cherry (two leaves whose parents are connected by a reticulate edge). In this paper, we present a fixed-parameter tractable algorithm to solve the problem of finding a maximum agreement cherry-reduced subnetwork (MACRS) between two rooted binary level-1 networks. This is first exact algorithm proposed to solve the MACRS problem. As proven in earlier work, there is a direct relationship between finding an MACRS and calculating a distance based on cherry operations. As a result, the proposed algorithm also provides a distance that can be used for the comparison of level-1 networks.

Metagenomics is widely used to study the microbiome using environmental samples, and taxonomic classification of reads is a precursor to many analyses of such data. Taxonomic classification requires a comparative analysis of reads against a reference dataset of known organisms. Crucially, the genomes represented in a sample may be phylogenetically distant to their closest match in the reference set. Thus, simply mapping reads to genomes is insufficient; we need to find inexact matches to species with substantial distance. While k-mer-based methods, such as Kraken, have proved popular, they have limited ability to match against distant taxa. In this paper, we use locality sensitive hashing to design a k-mer-based method that can match reads to genomes with higher distance than existing methods. We build on an earlier contamination detection method, CONSULT, to add taxonomic classification abilities. We show in a series of experiments that our method, CONSULT-II, has much higher recall than alternatives when precision is about the same. Its results can also be summarized to obtain a taxonomic profile, which we show outperforms leading methods with respect to some measurement criteria. CONSULT-II is available at https://github.com/bo1929/CONSULT-II.

Metagenomic profiling from sequencing data aims to disentangle a microbial sample at lower ranks of taxonomy, such as species and strains. Deep taxonomic profiling involving accurate estimation of strain level abundances aids in precise quantification of the microbial composition, which plays a crucial role in various downstream analyses. Existing tools primarily focus on strain/subspecies identification and limit abundance estimation to the species level. Abundance quantification of the identified strains is challenging and remains largely unaddressed by the existing approaches. We propose a novel algorithm MAGE (Microbial Abundance GaugE), for accurately identifying constituent strains and quantifying strain level relative abundances. For accurate profiling, MAGE uses read mapping information and performs a novel local search-based profiling guided by a constrained optimization based on maximum likelihood estimation. Unlike the existing approaches that often rely on strain-specific markers and homology information for deep profiling, MAGE works solely with read mapping information, which is the set of target strains from the reference collection for each mapped read. As part of MAGE, we provide an alignment-free and kmer-based read mapper that uses a compact and comprehensive index constructed using FM-index and R-index. We use a variety of evaluation metrics for validating abundances estimation quality. We performed several experiments using a variety of datasets, and MAGE exhibited superior performance compared to the existing tools on a wide range of performance metrics.

With the advent of single-cell DNA sequencing, it is now possible to infer the evolutionary history of thousands of tumor cells obtained from a single patient. This evolutionary history, which takes the shape of a tree, reveals the mode of evolution of the specific cancer under study and, in turn, helps with clinical diagnosis, prognosis, and therapeutic treatment. In this study we focus on the question of determining the mode of evolution of tumor cells from their inferred evolutionary history. In particular, we employ recursive neural networks that capture tree structures to classify the evolutionary history of tumor cells into one of four modes—linear, branching, neutral, and punctuated. We trained our model, MoTERNN, using simulated data in a supervised fashion and applied it to a real phylogenetic tree obtained from single-cell DNA sequencing data. MoTERNN is implemented in Python and is publicly available at https://github.com/NakhlehLab/MoTERNN.