Who are your closest relatives? Algorithms for reconciling non-binary species trees

Reconstruction of trees describing relationships among species is of vital importance to evolutionary studies. Species trees not only reveal the history of life, they also provide a framework for understanding the evolution of physiology, morphology, and cellular circuitry. Although gene sequences have proved a powerful source of evidence for inferring species trees, incorrect species trees can result when the histories of the species and the gene differ. Gene duplications, gene losses and transfer of genes from one species to another can all result in a gene tree which disagrees with the species tree. These events can be inferred and corrected for by comparing the gene and species trees, a process called reconciliation.

While reconciling a binary gene tree with a binary species tree is a well-studied, tractable problem, the standard reconciliation algorithm yields incorrect results when applied to non-binary species trees. Binary reconciliation makes simplifying assumptions about genetic variation in ancestral populations that are not justified when the species tree is non-binary. We present the first formal algorithms for reconciling binary gene trees with non-binary species trees. Our algorithms, which combine models from standard reconciliation and population genetics, have been implemented in Notung, a free, publicly available software tool available at http://www.cs.cmu.edu/~durand/Notung. I will discuss the application of these methods to resolving uncertainty in species trees, with examples from species lineages that are currently debated in the evolutionary biology literature.