Accurate prediction and classification of orthologous genes

该计划的高级目标是开发一种统一的，系统的和自动化的方法来重建受重要进化事件影响的基因中的生物功能的进化。具体的目标是：(1)发展快速和准确的方法来检测同源基因，即通过物种形成事件分离的基因；(2)根据它们自最后一个共同祖先以来的功能演变来分类基因关系。为了实现这些目标，我们将探索固定参数可追溯性（FPT），近似算法和结构图论方面的新颖和最先进的技术。这项研究将使人们对生物体如何获得、丧失或传递功能有更深入的了解。研究背景。推断基因之间的进化关系是比较、系统发育和功能分析的一个基本方面。同源关系和同源关系在生物学中特别重要：如果两个基因是从经历了物种形成事件的祖先基因中派生出来的，那么它们就是同源基因；如果它们是由复制产生的，那么它们就是同源基因。物种形成被认为是保存DNA序列和功能，而复制则倾向于引入分化。基于这一思想，区分同源物和相似物在生物学上有许多应用，包括基因功能注释、药物靶向基因预测、物种新基因发现和进化历史重建。在过去的十年里，已经有几十种正畸预测方法被发表，但是这些方法都面临着两个困难的挑战。首先，更多的基因组被测序，数以百万计的DNA序列需要分析，而当前的方法必须牺牲准确性来获得合理的可扩展性。然而，最近已经发现了新的图论特征的正交关系，它只剩下利用这些性质来设计快速和准确的专门算法。其次，最近的几篇论文已经确定，正畸学与谬误学的二分法过于严格，需要进一步分类才能做出与生物学相关的预测。目前的方法给最终用户留下了解释推断的成对关系的问题，而有大量的数据可以自动完成这项任务（例如，基因序列、蛋白质相互作用网络等）。在这个研究项目中，我们将解决这两个挑战。我们将通过设计适合于同源预测的算法来实现准确性和可扩展性，并提出一种基于影响它们的祖先事件的新的基因关系分类。一些预期的结果包括加速所有对所有DNA序列的比较，多色聚类问题的参数化算法和预测重复的功能影响。该项目还将在计算生物学、高级算法和大数据分析方面培养3名硕士和2名博士。

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.