title: EUCALYPT: efficient tree reconciliation enumerator.
abstract: 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/.
authors: Inria Grenoble - Rhône-Alpes; Inovallée 655, avenue de l'Europe, Montbonnot, Saint Ismier cedex, 38334 France.|Université de Lyon, F-69000, Lyon; Université Lyon 1; CNRS, UMR5558; 43 Boulevard du 11 Novembre 1918, Villeurbanne cedex, 69622 France.|Università di Firenze, Dipartimento di Ingegneria dell'Informazione; Via Santa Marta, 3, Firenze, 50139 Italy.
authors: Beatrice
authors: B
authors: Donati
authors: Inria Grenoble - Rhône-Alpes; Inovallée 655, avenue de l'Europe, Montbonnot, Saint Ismier cedex, 38334 France.|Université de Lyon, F-69000, Lyon; Université Lyon 1; CNRS, UMR5558; 43 Boulevard du 11 Novembre 1918, Villeurbanne cedex, 69622 France.
authors: Christian
authors: C
authors: Baudet
authors: Inria Grenoble - Rhône-Alpes; Inovallée 655, avenue de l'Europe, Montbonnot, Saint Ismier cedex, 38334 France.|Université de Lyon, F-69000, Lyon; Université Lyon 1; CNRS, UMR5558; 43 Boulevard du 11 Novembre 1918, Villeurbanne cedex, 69622 France.
authors: Blerina
authors: B
authors: Sinaimeri
authors: Università di Firenze, Dipartimento di Ingegneria dell'Informazione; Via Santa Marta, 3, Firenze, 50139 Italy.
authors: Pierluigi
authors: P
authors: Crescenzi
authors: Inria Grenoble - Rhône-Alpes; Inovallée 655, avenue de l'Europe, Montbonnot, Saint Ismier cedex, 38334 France.|Université de Lyon, F-69000, Lyon; Université Lyon 1; CNRS, UMR5558; 43 Boulevard du 11 Novembre 1918, Villeurbanne cedex, 69622 France.
authors: Marie-France
authors: MF
authors: Sagot
keywords: Cophylogeny; Enumeration algorithm; Host-parasite systems; Polynomial delay; Reconciliation
references: BMC Evol Biol. 2013 Dec 23;13:275
references: 24365056
references: Adv Parasitol. 2003;54:303-30
references: 14711089
references: BMC Evol Biol. 2008 Mar 27;8:100
references: 18371215
references: BMC Bioinformatics. 2010 Jan 18;11 Suppl 1:S60
references: 20122236
references: Mol Ecol Resour. 2011 May;11(3):567-72
references: 21481216
references: Bioinformatics. 2012 Jun 15;28(12):i283-91
references: 22689773
references: Brief Bioinform. 2011 Sep;12(5):392-400
references: 21949266
references: Mol Biol Evol. 2009 Jan;26(1):143-53
references: 18922760
references: IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):517-35
references: 21233529
references: Trends Ecol Evol. 1998 Sep 1;13(9):356-9
references: 21238340
references: J Comput Biol. 2013 Oct;20(10):738-54
references: 24033262
references: Bioinformatics. 2012 Sep 15;28(18):i409-i415
references: 22962460
references: Algorithms Mol Biol. 2010 Feb 03;5:16
references: 20181081
references: Syst Biol. 1999 Sep;48(3):523-46
references: 12066292
references: Nature. 2011 Jan 6;469(7328):93-6
references: 21170026
references: PLoS One. 2013 Apr 08;8(4):e61048
references: 23580325
references: Math Biosci. 1998 May;149(2):191-223
references: 9621683
references: J Evol Biol. 2007 Jul;20(4):1428-38
references: 17584237
references: Parasitology. 2003 May;126(Pt 5):473-80
references: 12793652
references: Theory Biosci. 2005 Apr;123(4):277-99
references: 18202869
references: Syst Biol. 2007 Apr;56(2):232-51
references: 17464880
references: J Comput Biol. 2009 Jan;16(1):105-17
references: 19119995
references: Nature. 1988 Mar 17;332(6161):258-9
references: 3347269