Using MCMC to Differentiate Breakpoints that Signal Large-Scale Rearrangements between Complete Bacterial Genomes from Those that Do Not

• Activity Number: 335
• Type: Contributed
• Date/Time: Wednesday, August 6, 2003 : 8:30 AM to 10:20 AM
• Sponsor: Biometrics Section
• Author(s): Robert Mau*+ and Aaron Darling and Fred Blattner and Paul Liss and Nicole Perna
• Companies: University of Wisconsin, Madison and University of Wisconsin, Madison and University of Wisconsin, Madison and University of Wisconsin, Madison and University of Wisconsin
• Keywords: breakpoints ; genome rearrangements ; Gibbs sampler

Abstract

Given a set of common genomic landmarks among a group of taxa, we use Markov chain Monte Carlo to assess the likelihood that each landmark contributes to some locally collinear block. The existence of such blocks mirrors large-scale genomic rearrangements between taxa. A Markov chain is run on a state space of binary random variables located at each node of a directed graph. Each edge defines one-half of the relative position and orientation of landmarks in one genome. A Gibbs Sampler updates the inclusion/exclusion variable at each vertex. A raw feature score is computed from the current configuration of all other states by summing across the longest uninterrupted string of "turned on" mutually collinear features. The raw score is translated into a posterior probability via a one-sided logistic transform, and the current feature's binary state is updated with a draw of a uniform random variate. Breakpoints can then be determined from the subset of features whose marginal posterior probability (the relative frequency of inclusion) exceeds some minimum threshold. Several multiple comparisons, using enterobacterial genomes with varying genomic plasticity, are analyzed.