Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach

Cedric Chauve 1 Yann Ponty 2, 3, 1 João Paulo Pereira Zanetti 4
3 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Reconstruction of the evolutionary history of genomic characters along a given species tree is a long-standing problem in computational biology, with efficient algorithms to compute parsimonious scenarios for many types of characters, as in the cases of genes and genomes sequences, gene content, and gene family evolution. Recently, Bérard et al. extended the corpus of such results to syntenic characters, as they introduced the notion of adjacency forest, that models the evolution of gene adjacencies within a phylogeny, and described an efficient dynamic programming (DP) algorithm, called DeCo (Berard et al, ECCB 2012), to compute parsimonious adjacency evolutionary histories. Applying the classical parsimony-based approach of DeCo to a dataset of over 6,000 pairs of mammalian gene trees yielded a significant number of ancestral genes involved in more than two adjacencies, which correspond to syntenic inconsistencies. Recently, more general approaches for parsimony problems have been analyzed, either exploring a wider range of parameters, or considering several alternate histories for a given instance. Our work seeks to address the syntenic inconsistencies of DeCo by extending their DP scheme toward an exploration of the whole solution space of adjacency histories, under the Boltzmann probability distribution, that assigns a probability to each solution defined in terms of its parsimony score. This principle has been applied in several contexts and is sometimes known as the “Boltzmann ensemble approach”. While this Boltzmann ensemble approach has been used for a long time in RNA structure analysis, to the best of our knowledge it is not the case in comparative genomics, where exact probabilistic models have been favored as increasing computational capacities allow them to handle realistic datasets. However, such a probabilistic model does not exist so far for gene adjacencies, which motivates our work. We first show that by sampling adjacencies histories under a Boltzmann distribution that favors co-optimal histories and conserving only frequent ancestral adjacencies, we can reduce significantly the number of syntenic inconsistencies. We also implement a inside/outside variant for DeCo, that computes the actual probabilities of each individual adjacency considered under the Boltzmann distribution.
Type de document :
RECOMB-CG'14, Oct 2014, Cold Spring HArbour, United States. 〈http://cs.nyu.edu/~parida/RECOMB-CG2014/〉
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

Contributeur : Yann Ponty <>
Soumis le : samedi 17 octobre 2015 - 02:01:45
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08
Document(s) archivé(s) le : lundi 18 janvier 2016 - 10:12:41


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01216782, version 1


Cedric Chauve, Yann Ponty, João Paulo Pereira Zanetti. Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach. RECOMB-CG'14, Oct 2014, Cold Spring HArbour, United States. 〈http://cs.nyu.edu/~parida/RECOMB-CG2014/〉. 〈hal-01216782〉



Consultations de la notice


Téléchargements de fichiers