EUCALYPT: efficient tree reconciliation enumerator

详细信息    查看全文

• 作者：Beatrice Donati (1) (2) (3)
  Christian Baudet (1) (2)
  Blerina Sinaimeri (1) (2)
  Pierluigi Crescenzi (3)
  Marie-France Sagot (1) (2)
  
  1. Inria Grenoble - Rh么ne-Alpes ; Inovall茅e 655 ; avenue de l鈥橢urope ; Montbonnot ; Saint Ismier cedex ; 38334 ; France
  2. Universit茅 de Lyon ; F-69000 ; Lyon ; Universit茅 Lyon 1 ; CNRS ; UMR5558 ; 43 Boulevard du 11 Novembre 1918 ; Villeurbanne cedex ; 69622 ; France
  3. Universit脿 di Firenze ; Dipartimento di Ingegneria dell鈥橧nformazione ; Via Santa Marta ; 3 ; Firenze ; 50139 ; Italy
  
• 关键词：Cophylogeny ; Reconciliation ; Enumeration algorithm ; Polynomial delay ; Host ; parasite systems
• 刊名：Algorithms for Molecular Biology
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：10
• 期：1
• 全文大小：582 KB
• 参考文献：1. Charleston MA. Jungles: a new solution to the host/parasite phylogeny reconciliation problem. Math Biosci. 1998; 149(2):191鈥?23. CrossRef
  2. Charleston MA. Recent results in cophylogeny mapping. Adv Parasit. 2003; 54:303鈥?0. CrossRef
  3. Merkle D, Middendorf M. Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information. Theor Biosci. 2005; 123(4):277鈥?99. CrossRef
  4. Doyon JP, Ranwez V, Daubin V, Berry V. Models, algorithms and programs for phylogeny reconciliation. Brief Bioinform. 2011; 12(5):392鈥?00. CrossRef
  5. Hallett MT, Lagergren J. Efficient algorithms for lateral gene transfer problems In: Lengauer T, editor. Proceedings of the fifth annual international conference on computational biology (RECOMB 2001). New York, USA: ACM: 2001. p. 149鈥?6.
  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鈥?5. CrossRef
  7. Rosen DE. Vicariant patterns and historical explanation in biogeography. Syst Biol. 1978; 27(2):159鈥?8.
  8. Page RDM. Maps between trees and Cladistic analysis of historical associations among genes, organisms, and areas. Syst Biol. 1994; 43:58鈥?7.
  9. Maddison PW. Gene trees in species trees. Syst Biol. 1997; 46(3):523鈥?6. CrossRef
  10. Ronquist F. Parsimony analysis of coevolving species associations. In: Tangled trees: Phylogeny, cospeciation and coevolution. Chicago: University of Chicago Press: 2002. p. 22鈥?4.
  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. France: Spring-Verlag Berlin Heidelberg: 2013. p. 200鈥?4.
  12. Page RD, Charleston MA. Trees within trees: phylogeny and historical associations. Trends Ecol Evol. 1998; 13(9):356鈥?. CrossRef
  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鈥?1. CrossRef
  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鈥?5. CrossRef
  15. Libeskind-Hadas R, Charleston MA. On the computational complexity of the reticulate cophylogeny reconstruction problem. J Comput Biol. 2009; 16:105鈥?7. CrossRef
  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. 748-7188-5-16" target="_blank" title="It opens in new window">CrossRef
  17. David LA, Alm EJ. Rapid evolutionary innovation during an Archaean Genetic Expansion. Nature. 2011; 469:93鈥?. CrossRef
  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. Ottawa, Canada: Spring-Verlag Berlin Heidelberg: 2011. p. 93鈥?08.
  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鈥?3. Berlin: Heidelberg Springer-Verlag: 2013. p. 1鈥?3.
  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鈥?8.
  22. Poulin R, Mouillot D. Parasite specialization from a phylogenetic perspective: a new index of host specificity. Parasitology. 2003; 126:473鈥?0. CrossRef
  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. CrossRef
  24. Hafner M, Nadler S. Phylogenetic trees support the coevolution of parasites and their hosts. Nature. 1988; 332:258鈥?. CrossRef
  25. Paterson A, Palma R, Gray R. Drowning on arrival, missing the boat, and x-events: How likely are sorting events? In: Page R D M, editor. Tangled trees: Phylogeny, cospeciation, and coevolution. Chicago: USA: UC Press: 2003. p. 287鈥?07.
  26. Hugot JP. New evidence for hystricognath rodent monophyly from the phylogeny of their pinworms In: Page R D M, editor. Tangled trees: Phylogeny, cospeciation, and coevolution. Chicago: USA: UC Press: 2003. p. 144鈥?3.
  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. CrossRef
  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鈥?1. CrossRef
  29. Ramsden C, Holmes E, Charleston M. Hantavirus evolution in relation to its rodent and insectivore hosts. Mol Biol Evol. 2009; 26:143鈥?3. CrossRef
  30. Hugot JP. Primates and their pinworm parasites: the Cameron hypothesis revisited. Syst Biol. 1999; 48(3):523鈥?46. CrossRef
  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. CrossRef
  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鈥?2. CrossRef
  33. Sim玫es PM. Diversity and dynamics of Wolbachia-host associations in arthropods from the society archipelago, French Polynesia, PhD thesis. France: University of Lyon 1; 2012.
  34. Bruni V. Algoritmi per la ricostruzione cofilogenetica, Master鈥檚 thesis. Florence, Italy: University of Florence, Faculty of Mathematical, Physical and Natural Sciences; 2013. [In Italian].
  
• 刊物主题：Bioinformatics; Computational Biology/Bioinformatics; Physiological, Cellular and Medical Topics; Algorithms;
• 出版者：BioMed Central
• ISSN：1748-7188

文摘

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/.