Grant: Discovery Grants Program - Individual

The high-level objective of this program is to develop a unified, systematic and automated approach to reconstruct the evolution of biological functions in genes affected by important evolutionary events. The specific goals are to (1) develop fast and accurate approaches to detect orthologs, which are genes that are separated by speciation events, and (2) to classify gene relationships based on how their function evolved since their last common ancestor. To achieve these goals, we will explore novel and state-of-the-art techniques in fixed-parameter tractability (FPT), approximation algorithms and structural graph theory. This research will lead to a deeper understanding of how organisms acquire, lose or transmit functions. Research context.  Inferring evolutionary relationships between genes is a fundamental aspect of comparative, phylogenetic, and functional analyses. The orthology and paralogy relationships are of particular importance in biology: two genes are orthologs if they descend from an ancestral gene that has undergone an event known as speciation, and paralogs if they result from duplication.  Speciation is expected to conserve DNA sequence and function, whereas duplication tends to introduce divergence. Owing to this idea, distinguishing orthologs from paralogs has many applications in biology, including gene function annotation, predicting genes targeted by drugs, finding novel genes in species, and reconstructing evolutionary histories. Dozens of orthology prediction methods have been published in the last decade, but these approaches are facing two difficult challenges. First, more genomes are being sequenced, millions of DNA sequences need to be analyzed, and current methods must sacrifice accuracy to attain reasonable scalability. However, new graph-theoretic characterizations of orthologous relations have recently been discovered, and it only remains to exploit these properties to devise fast and accurate specialized algorithms. Second, several recent papers have established that the dichotomy of orthology versus paralogy is too strict, and that further classification is needed to make biologically relevant predictions. Current methods leave the end-user with the problem of interpreting inferred pairwise relations, whereas there is plenty of data to automate this task (for instance, gene sequences, protein interaction networks,...). In this research program, we will address both challenges. We will achieve accuracy and scalability by designing algorithms that are tailored for orthology prediction, and propose a new gene relation classification based on the ancestral events that have affected them. Some of the expected outcomes include a speedup of all-vs-all DNA sequence comparison, parameterized algorithms for multicolored clustering problems and prediction of the functional impact of duplications. The program will also train 3 MSc and 2 PhD students in computational biology, advanced algorithms, and big data analytics.