An algorithmic framework for gene family evolution

这是一个计算生物学项目，旨在开发适当的算法工具来推断基因的进化。*基因是遗传的基本分子单位，是理解生物机制的关键。大多数遗传学研究的第一步是根据序列相似性将基因分成不同的家族，其基本思想是相似的序列反映了来自共同祖先的差异。在一个基因家族中，起源于物种形成事件的“正基因”比起源于复制或水平基因转移(HGT)的“平行基因”或“异种基因”更有可能保留祖先的功能。这是推断基因进化的一个主要动机，因为它是功能预测目的的先决条件。*基于树的基因关系预测方法包括重建基因家族的系统发育树，然后根据“协调”，即将基因树嵌入物种树，推断内部节点的性质(物种形成、复制或HGT)。这些方法的准确性很大程度上取决于所考虑的基因树的准确性。然而，由于各种原因，经典的系统发育方法容易出错。这激发了本项目的基因树校正部分。*协调是基于每个基因家族通过单一的得失事件独立进化的假设。尽管这一假设适用于基因组中相距甚远的基因，但它不适用于出现在共线基因块中的基因，这些基因更有可能是协同进化的结果。在这种情况下，需要结合树和顺序信息来推断片段重复、丢失和HGT的方法。*基因关系预测也存在无树方法。它们主要是基于序列相似性的层次聚类。这些方法的结果是成对的基因关系，可以通过彩色图表(每种类型的关系对应一种颜色)来表示。虽然基因树诱导了一组基因之间的关系，但反之亦然，因为一组关系可能并不代表一个基因家族的有效历史。确定和修正一组与物种树的“可满足性”和“一致性”的关系是我们在这个项目中处理的两个重要问题。总而言之，我们的目标是建立黄金标准基因树，推断准确的基因关系，并预测导致所观察到的基因多样性的实际进化事件，以及祖先基因的含量和顺序。我们将探索字符串、树和图上的优化问题，研究它们的理论复杂性，开发精确、近似和启发式算法，在模拟数据集上测试它们，如果感兴趣的话将它们应用于生物数据集。开发的算法将被实施到免费提供的、用户友好的和文档齐全的软件中。**

This is a computational biology project aiming at developing the appropriate algorithmic tools for inferring the evolution of genes.******Genes are the basic molecular units of heredity, key for understanding biological mechanisms. A first step of most genetic studies is to group genes into families according to sequence similarity, the underlying idea being that similar sequences reflect divergence from a common ancestor. Within a gene family, «orthlogs» genes originating from a speciation event are more likely to preserve the ancestral function than «paralogs» or «xenologs» originating from duplications or Horizontal Gene Transfer (HGT). This is a major motivation for inferring gene evolution, as it is a prerequisite for functional prediction purposes.******Tree-based methods for gene relation prediction consist in reconstructing a phylogenetic tree for the gene family, and then inferring the nature of internal nodes (speciation, duplication or HGT) from a «reconciliation», i.e. an embedding of the gene tree into the species tree. The accuracy of these methods strongly depend on the accuracy of the considered gene tree. However, for various reasons, classical phylogenetic methods are error prone. This motivates the gene tree correction part of this project.******Reconciliation is based on the assumption that each gene family evolves independently through single gain and loss events. Although this hypothesis holds for genes that are far apart in the genome, it is not appropriate for genes appearing grouped into blocs of co-linear genes, which are more plausibly the result of a concerted evolution. Methods for inferring segmental duplication, loss and HGT, combining both tree and order information, are required in this case.******Tree-free methods also exist for gene relation prediction. They are mainly based on hierarchical clustering according to sequence similarity. Results of these methods are pairwise gene relations that can be represented by means of a coloured graph (a colour for each type of relation). While a gene tree induces a set of relations between genes, the converse is not always true, as a set of relations may not represent a valid history for a gene family. Determining and correcting a set of relation for «satisfiability» and «consistency» with a species tree are two important problematics that we handle in this project.******In summary, our goal is to produce gold standard gene trees, infer accurate gene relations and predict the actual evolutionary events that have led to the observed gene diversity, as well as ancestral gene contents and orders. We will explore optimization problems on strings, trees and graphs, study their theoretical complexity, develop exact, approximation and heuristic algorithms, test them on simulated datasets and apply them to the biological datasets if interest. Developed algorithms will be implemented into freely available user-friendly and well documented software.**