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.