Evolution Of Genes Neighborhood Within Reconciled Phylogenies: An Ensemble Approach

We consider a recently introduced dynamic programming scheme to compute parsimonious evolutionary scenarios for gene adjacencies. We extend this scheme to sample evolutionary scenarios from the whole solution space under the Boltzmann distribution. We apply our algorithms to a dataset of mammalian gene trees and adjacencies, and observe a significant reduction of the number of syntenic inconsistencies observed in the resulting ancestral gene adjacencies.88264956Associação Brasileira de Bioinformática e Biologia Computacional,Intel Corporation,Sociedade Brasileira de ComputaçãoBansal, M.S., Alm, E.J., Kellis, M., Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss (2012) Bioinformatics, 28 (12), pp. 283-291Bansal, M.S., Alm, E.J., Kellis, M., Reconciliation revisited: Handling multiple optima when reconciling with duplication, transfer, and loss (2013) Journal of Computational Biology, 20 (10), pp. 738-754Bérard, S., Gallien, C., Boussau, B., Szöllosi, G.J., Daubin, V., Tannier, E., Evolution of gene neighborhoods within reconciled phylogenies (2012) Bioinformatics, 28 (18), pp. 382-388Clote, P., Lou, F., Lorenz, W.A., Maximum expected accuracy structural neighbors of an RNA secondary structure (2012) BMC Bioinformatics, 13 (S5)Csűrös, M., Ancestral reconstruction by asymmetric wagner parsimony over continuous characters and squared parsimony over distributions (2008) RECOMB-CG 2008. LNCS (LNBI), 5267, pp. 72-86. , Nelson, C.E., Vialette, S. (eds.),. Springer, HeidelbergCsürös, M., How to infer ancestral genome features by parsimony: Dynamic programming over an evolutionary tree (2013) Models and Algorithms for Genome Evolution, pp. 29-45. , SpringerDoyon, J.-P., Hamel, S., Chauve, C., An efficient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework (2012) IEEE/ACM Trans. Comput. Biology Bioinform, 9 (1), pp. 26-39Doyon, J.-P., Scornavacca, C., Gorbunov, K.Y., Szöllősi, G.J., Ranwez, V., Berry, V., An efficient algorithm for gene/Species trees parsimonious reconciliation with losses, duplications and transfers (2010) RECOMB-CG 2010. LNCS, 6398, pp. 93-108. , Tannier, E. (ed.),. Springer, HeidelbergLiberles, D.A., (2007) Ancestral Sequence Reconstruction, , (ed.), Oxford University PressLibeskind-Hadas, R., Wu, Y.-C., Bansal, M.S., Kellis, M., Pareto-optimal phylogenetic tree reconciliation (2014) Bioinformatics, 30 (12), pp. 87-95Pachter, L., Sturmfels, B., Parametric inference for biological sequence analysis (2004) PNAS, 101 (46), pp. 16138-16143Patterson, M., Szöllosi, G.J., Daubin, V., Tannier, E., Lateral gene transfer, rearrangement, reconciliation (2013) BMC Bioinformatics, 14 (S15)Ponty, Y., Saule, C., A combinatorial framework for designing (Pseudoknotted) RNA algorithms (2011) WABI 2011. LNCS, 6833, pp. 250-269. , Przytycka, T.M., Sagot, M.-F. (eds.),. Springer, HeidelbergScornavacca, C., Paprotny, W., Berry, V., Ranwez, V., Representing a set of reconciliations in a compact way (2013) J. Bioinformatics and Computational Biology, 11 (2