title: Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees.
abstract: BACKGROUND
  Gene duplication (D), transfer (T), loss (L) and incomplete lineage sorting (I) are crucial to the evolution of gene families and the emergence of novel functions. The history of these events can be inferred via comparison of gene and species trees, a process called reconciliation, yet current reconciliation algorithms model only a subset of these evolutionary processes.
  
  
  RESULTS
  We present an algorithm to reconcile a binary gene tree with a nonbinary species tree under a DTLI parsimony criterion. This is the first reconciliation algorithm to capture all four evolutionary processes driving tree incongruence and the first to reconcile non-binary species trees with a transfer model. Our algorithm infers all optimal solutions and reports complete, temporally feasible event histories, giving the gene and species lineages in which each event occurred. It is fixed-parameter tractable, with polytime complexity when the maximum species outdegree is fixed. Application of our algorithms to prokaryotic and eukaryotic data show that use of an incomplete event model has substantial impact on the events inferred and resulting biological conclusions.
  
  
  BACKGROUND
  Our algorithms have been implemented in Notung, a freely available phylogenetic reconciliation software package, available at http://www.cs.cmu.edu/~durand/Notung.
  
  
  BACKGROUND
  mstolzer@andrew.cmu.edu.
authors.affiliation: Department of Biological Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA. mstolzer@andrew.cmu.edu
authors.forename: Maureen
authors.initials: M
authors.lastname: Stolzer
authors.forename: Han
authors.initials: H
authors.lastname: Lai
authors.forename: Minli
authors.initials: M
authors.lastname: Xu
authors.forename: Deepa
authors.initials: D
authors.lastname: Sathaye
authors.forename: Benjamin
authors.initials: B
authors.lastname: Vernot
authors.forename: Dannie
authors.initials: D
authors.lastname: Durand
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D020440:Gene Duplication; D022761:Gene Transfer, Horizontal; D008957:Models, Genetic; D005810:Multigene Family; D010802:Phylogeny; D012984:Software