Computing the Partition Function of a Gibbs Distribution on a Sequence of Phylogenetic Trees

• Activity Number: 126
• Type: Contributed
• Date/Time: Monday, July 30, 2012 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Yujin Chung*+ and Cécile Ané
• Companies: University of Wisconsin-Madison and University of Wisconsin-Madison
• Keywords: Gibbs distribution ; phylogenetics ; evolution ; partition function ; recombination ; tree metric

Abstract

The Robinson-Foulds (RF) distance is widely used in phylogenetics for comparing tree-like evolutionary histories of a group of organisms. Because of biological processes and recombination events, the topologies of phylogenetic trees of neighboring genes may be different, as one moves along a chromosome. A Gibbs distribution can be used to describe the dissimilarities among gene trees in terms of the RF distances between neighboring gene trees. When the partition function of the Gibbs distribution is overlooked or miscalculated, an incorrect maximum likelihood estimate or an incorrect Bayesian posterior distribution can be obtained. Calculating the partition function in the naive way is computationally prohibitive. We derive here an algorithm to calculate the partition function exactly, based on the calculation of the joint distribution of the tree shapes and the RF distance between two random trees. We derive this joint distribution through a system of generating functions. We also propose approximations to the partition function, which are computationally fast and very accurate.