EUCALYPT: efficient tree reconciliation enumerator

Algorithms for Molecular Biology

Beatrice Donati²  Christian Baudet¹  Blerina Sinaimeri¹  Pierluigi Crescenzi²  Marie-France Sagot¹ 

[1] Université de Lyon, F-69000, Lyon; Université Lyon 1; CNRS, UMR5558; 43 Boulevard du 11 Novembre 1918, Villeurbanne cedex 69622, France

[2] Università di Firenze, Dipartimento di Ingegneria dell’Informazione; Via Santa Marta, 3, Firenze 50139, Italy

关键词: Host-parasite systems;    Polynomial delay;    Enumeration algorithm;    Reconciliation;    Cophylogeny;   

Others  :  1126878
DOI  :  10.1186/s13015-014-0031-3

 received in 2013-11-29, accepted in 2014-07-04,  发布年份 2015

【 摘 要 】

Background

Phylogenetic tree reconciliation is the approach of choice for investigating the coevolution of sets of organisms such as hosts and parasites. It consists in a mapping between the parasite tree and the host tree using event-based maximum parsimony. Given a cost model for the events, many optimal reconciliations are however possible. Any further biological interpretation of them must therefore take this into account, making the capacity to enumerate all optimal solutions a crucial point. Only two algorithms currently exist that attempt such enumeration; in one case not all possible solutions are produced while in the other not all cost vectors are currently handled. The objective of this paper is two-fold. The first is to fill this gap, and the second is to test whether the number of solutions generally observed can be an issue in terms of interpretation.

Results

We present a polynomial-delay algorithm for enumerating all optimal reconciliations. We show that in general many solutions exist. We give an example where, for two pairs of host-parasite trees having each less than 41 leaves, the number of solutions is 5120, even when only time-feasible ones are kept. To facilitate their interpretation, those solutions are also classified in terms of how many of each event they contain. The number of different classes of solutions may thus be notably smaller than the number of solutions, yet they may remain high enough, in particular for the cases where losses have cost 0. In fact, depending on the cost vector, both numbers of solutions and of classes thereof may increase considerably. To further deal with this problem, we introduce and analyse a restricted version where host switches are allowed to happen only between species that are within some fixed distance along the host tree. This restriction allows us to reduce the number of time-feasible solutions while preserving the same optimal cost, as well as to find time-feasible solutions with a cost close to the optimal in the cases where no time-feasible solution is found.

Conclusions

We present EUCALYPT, a polynomial-delay algorithm for enumerating all optimal reconciliations which is freely available at http://eucalypt.gforge.inria.fr/ webcite.

【 授权许可】

   
2015 Donati et al.; licensee BioMed Central.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

【 参考文献 】

• [1]Charleston MA: Jungles: a new solution to the host/parasite phylogeny reconciliation problem. Math Biosci 1998, 149(2):191-223.
• [2]Charleston MA: Recent results in cophylogeny mapping. Adv Parasit 2003, 54:303-30.
• [3]Merkle D, Middendorf M: Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information. Theor Biosci 2005, 123(4):277-299.
• [4]Doyon JP, Ranwez V, Daubin V, Berry V: Models, algorithms and programs for phylogeny reconciliation. Brief Bioinform 2011, 12(5):392-400.
• [5]Hallett MT, Lagergren J: Efficient algorithms for lateral gene transfer problems. In Proceedings of the fifth annual international conference on computational biology (RECOMB 2001). Edited by Lengauer T. ACM, New York, USA; 2001.
• [6]Tofigh A, Hallett M, Lagergren J: Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans Comput Biol Bioinf 2011, 8(2):517-35.
• [7]Rosen DE: Vicariant patterns and historical explanation in biogeography. Syst Biol 1978, 27(2):159-88.
• [8]Page RDM: Maps between trees and Cladistic analysis of historical associations among genes, organisms, and areas. Syst Biol 1994, 43:58-77.
• [9]Maddison PW: Gene trees in species trees. Syst Biol 1997, 46(3):523-36.
• [10]Ronquist F: Parsimony analysis of coevolving species associations. In Tangled trees: Phylogeny, cospeciation and coevolution. University of Chicago Press, Chicago; 2002.
• [11]Wieseke N, Bernt M, Middendorf M: Unifying parsimonious tree reconciliation. In 13th workshop on algorithms in bioinformatics (WABI 2013), Volume 8126 of lecture notes in computer science Sophia Antipolis. Spring-Verlag Berlin Heidelberg, France; 2013.
• [12]Page RD, Charleston MA: Trees within trees: phylogeny and historical associations. Trends Ecol Evol 1998, 13(9):356-9.
• [13]Bansal MS, Alm E, Kellis M: Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 2012, 28(12):i283-91.
• [14]Stolzer ML, Lai H, Xu M, Sathaye D, Vernot B, Durand D: Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees. Bioinformatics 2012, 28(18):i409-15.
• [15]Libeskind-Hadas R, Charleston MA: On the computational complexity of the reticulate cophylogeny reconstruction problem. J Comput Biol 2009, 16:105-17.
• [16]Conow C, Fielder D, Ovadia Y, Libeskind-Hadas R: Jane: a new tool for the cophylogeny reconstruction problem. Algorithm Mol Biol 2010, 5:16. BioMed Central Full Text
• [17]David LA, Alm EJ: Rapid evolutionary innovation during an Archaean Genetic Expansion. Nature 2011, 469:93-6.
• [18]Doyon JP, Scornavacca C, Gorbunov KY, Szöllősi GJ, Ranwez V, Berry V, Tannier E: An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers. In Proceedings of the 8th annual RECOMB satellite workshop on comparative genomics (RECOMB-CG 2010), Volume 6398 of lecture notes in bioinformatics. Spring-Verlag Berlin Heidelberg, Ottawa, Canada; 2011.
• [19]Merkle D, Middendorf M, Wieseke N: A parameter-adaptive dynamic programming approach for inferring cophylogenies. BMC Bioinformatics 2010, 11(Supplementary 1):10.
• [20]Bansal MS, Alm EJ, Kellis M: Reconciliation revisited: handling multiple optima when reconciling with duplication, transfer, and loss. In Proceedings of the 17th international conference on research in computational molecular biology, RECOMB’13. Heidelberg Springer-Verlag, Berlin; 2013.
• [21]Vienne DMD, Giraud T, Skyhoff JA: When can host shifts produce congruent host and parasite phylogenies? A simulation approach. JEvol Biol 2007, 20(4):1428-38.
• [22]Poulin R, Mouillot D: Parasite specialization from a phylogenetic perspective: a new index of host specificity. Parasitology 2003, 126:473-80.
• [23]Deng J, Yu F, Li HB, Gebiola M, Desdevises Y, Wu SA, et al.: Cophylogenetic relationships between Anicetus parasitoids (Hymenoptera: Encyrtidae) and their scale insect hosts (Hemiptera Coccidae). BMC Evol Biol 2013, 13:275. BioMed Central Full Text
• [24]Hafner M, Nadler S: Phylogenetic trees support the coevolution of parasites and their hosts. Nature 1988, 332:258-9.
• [25]Paterson A, Palma R, Gray R: Drowning on arrival, missing the boat, and x-events: How likely are sorting events? In Tangled trees: Phylogeny, cospeciation, and coevolution. Edited by Page R D M. USA: UC Press, Chicago; 2003.
• [26]Hugot JP: New evidence for hystricognath rodent monophyly from the phylogeny of their pinworms. In Tangled trees: Phylogeny, cospeciation, and coevolution. Edited by Page R D M. USA: UC Press, Chicago; 2003.
• [27]Refrégier G, Gac M, Jabbour F, Widmer A, Shykoff J, Yockteng R, et al.: Cophylogeny of the anther smut fungi and their caryophyllaceous hosts: Prevalence of host shifts and importance of delimiting parasite species for inferring cospeciation. BMC Evol Biol 2008, 8:100. BioMed Central Full Text
• [28]Hughes J, Kennedy M, Johnson KP, Palma RL, Page RDM: Multiple cophylogenetic analyses reveal frequent cospeciation between pelecaniform birds and pectinopygus lice. Syst Biol 2007, 56(2):232-51.
• [29]Ramsden C, Holmes E, Charleston M: Hantavirus evolution in relation to its rodent and insectivore hosts. Mol Biol Evol 2009, 26:143-53.
• [30]Hugot JP: Primates and their pinworm parasites: the Cameron hypothesis revisited. Syst Biol 1999, 48(3):523-546.
• [31]Balbuena JA, Mí-guez-Lozano R, Blasco-Costa I: PACo: a novel procrustes application to cophylogenetic analysis. PLoS ONE 2013, 8(4):e61048. http://dx.doi.org/10.1371%2Fjournal.pone.0061048
• [32]Simões PM, Mialdea G, Reiss D, Sagot MF, Charlat S: Wolbachia detection: an assessment of standard PCR protocols. Mol Ecol Resour 2011, 11(3):567-72.
• [33]Simões PM: Diversity and dynamics of Wolbachia-host associations in arthropods from the society archipelago, French Polynesia, PhD thesis. University of Lyon 1, France; 2012.
• [34]Bruni V: Algoritmi per la ricostruzione cofilogenetica, Master’s thesis. University of Florence, Faculty of Mathematical, Physical and Natural Sciences, Florence, Italy; 2013.