Algebraic and statistical methods for estimating evolutionary time in the bacterial genome

Abstract

The contribution of this thesis is 3-pronged. First, a method of computing pairwise expected distance under a generalised rearrangement system is introduced, inspired by the generating functions and Feynman integrals of statistical mechanics. The aim is to provide a statistically consistent estimator of evolutionary time. While precise, there is a crucial shortcoming arising from the calibration of the underlying stochastic model.

The second contribution moves towards a maximum likelihood approach for pair- wise rearrangement distances. This approach, previously articulated separately by Mikl´os [2003], Larget et al. [2002], and York et al. [2002], is the next step forward from the method of moments estimators presented by Wang and Warnow. The likelihood estimates are sensitive to path structure and distinguish between elements with equal minimal distance. We explore the properties and consequences of this construction concerning the induced total order over the set of arrangements and the effects on phylogenetic inference under the Neighbor-Joining algorithm. Sufficient conditions for equality of the Maximum Likelihood Estimate (MLE) of true evolutionary distance are given, and we explore impacts of generating sets and probability measures. Chapter 5 addresses the dihedral symmetry of circular arrangements by introducing a paradigm shift from genomes are group elements to genomes are cosets. Although there exists somewhat of a natural frame of reference due to the origin/terminus of replication, this assumption can present artefacts with specific models and metrics. We introduce a method for addressing the issue without making any frame of reference assumptions. The impacts are assessed by again considering changes to the induced total order and how it affects phylogenetic inference under Neighbor-Joining.

The final piece is a stand-alone method for computing the minimal weighted distance between two genome arrangements. Given a set of legal rearrangements and a weighting function, we generate a library of rewriting rules to allow us to rewrite any unreduced word as an equivalent word of reduced weight. This method can compute the minimal weighted distance and a particular word that realises this distance. To the best of our knowledge, this application of confluence and terminating rewriting systems has not been applied previously to genome rearrangement problems.

Date of Thesis submission	2025
Original language	English
Awarding Institution	Western Sydney University
Supervisor	Andrew Francis (Supervisor)