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.