title: Reconciliation revisited: handling multiple optima when reconciling with duplication, transfer, and loss.
abstract: Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication-loss (DL) reconciliation leads to a unique maximum-parsimony solution, duplication-transfer-loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn(2)) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution.
authors.affiliation: 1 Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology , Cambridge, Massachusetts.
authors.forename: Mukul S
authors.initials: MS
authors.lastname: Bansal
authors.forename: Eric J
authors.initials: EJ
authors.lastname: Alm
authors.forename: Manolis
authors.initials: M
authors.lastname: Kellis
mesh_terms: D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D019143:Evolution, Molecular; D017353:Gene Deletion; D020440:Gene Duplication; D022761:Gene Transfer, Horizontal; D008957:Models, Genetic
references.citation: Mol Biol (Mosk). 2009 Sep-Oct;43(5):946-58
references.pmid: 19899641
references.citation: Algorithms Mol Biol. 2010 Feb 03;5:16
references.pmid: 20181081
references.citation: Nature. 2011 Jan 6;469(7328):93-6
references.pmid: 21170026
references.citation: Syst Biol. 2011 Mar;60(2):117-25
references.pmid: 21186249
references.citation: J Comput Biol. 2000;7(3-4):429-47
references.pmid: 11108472
references.citation: Theory Biosci. 2005 Apr;123(4):277-99
references.pmid: 18202869
references.citation: Bioinformatics. 2012 Sep 15;28(18):i409-i415
references.pmid: 22962460
references.citation: J Comput Biol. 2008 Oct;15(8):1007-27
references.pmid: 18774902
references.citation: Nature. 2007 Sep 6;449(7158):54-61
references.pmid: 17805289
references.citation: J Comput Biol. 2011 Jan;18(1):59-65
references.pmid: 20715926
references.citation: Bioinformatics. 2002 Jan;18(1):92-9
references.pmid: 11836216
references.citation: J Bioinform Comput Biol. 2013 Apr;11(2):1250025
references.pmid: 23600816
references.citation: Mol Biol Evol. 2011 Jan;28(1):273-90
references.pmid: 20660489
references.citation: Syst Biol. 2009 Aug;58(4):411-24
references.pmid: 20525594
references.citation: BMC Bioinformatics. 2007 Mar 08;8:83
references.pmid: 17346331
references.citation: Annu Rev Genet. 2005;39:309-38
references.pmid: 16285863
references.citation: J Comput Biol. 2009 Jan;16(1):105-17
references.pmid: 19119995
references.citation: Genome Res. 2009 Feb;19(2):327-35
references.pmid: 19029536
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):517-35
references.pmid: 21233529
references.citation: Nucleic Acids Res. 2010 Jan;38(Database issue):D204-10
references.pmid: 20015972
references.citation: J Comput Biol. 1995 Winter;2(4):493-507
references.pmid: 8634901
references.citation: Math Biosci. 1998 May;149(2):191-223
references.pmid: 9621683
references.citation: J Comput Biol. 2008 Oct;15(8):1043-62
references.pmid: 18781833
references.citation: J Comput Biol. 2006 Mar;13(2):320-35
references.pmid: 16597243
references.citation: BMC Bioinformatics. 2010 Jan 18;11 Suppl 1:S60
references.pmid: 20122236
references.citation: Bioinformatics. 2012 Jun 15;28(12):i283-91
references.pmid: 22689773
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2012 Sep-Oct;9(5):1515-28
references.pmid: 22641711