An algorithmic framework for gene family evolution

点击翻译按钮获取中文摘要

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.