Generalisations of the symmetric inverse monoid and their applications to phylogenetics

Abstract

Combinatorial optimisation problems that arise when investigating sequences of largescale DNA rearrangement operations play an important role in phylogenetic tree reconstruction and the understanding of biological mechanisms that cause these rearrangements. Such problems generally consider a group G and an appropriate generating set X, where one aims to calculate minimum distances between elements (or subsets) of G with respect to the word metric on G induced by X. Also of interest is enumerating and investigating, in conjunction with feasible biological assumptions, sets of generator sequences u such that gu = h or ug = h given g, h ∈ G. While much attention has been given to these problems for groups such as the symmetric group, the hyperoctahedral group and the braid group, this thesis considers new biologically motivated combinatorial problems and models involving symmetric inverse monoids, categories, and related structures instead of groups.

Chapter 3 investigates these monoidal structures from a purely algebraic perspective. In particular, letting M be an arbitrary monoid and In be the symmetric inverse monoid on n elements, we deduce presentations by generators and relations for the transformational wreath product M ≀ In, an analogously defined generalisation M ≀ I of the symmetric inverse category I, and the subsemigroup M ≀ (In \ Sn) of M ≀ In. We also introduce the wreath product M ≀ IBn where IBn denotes the inverse braid monoid on n introduced by Easdown and Lavers.

Chapter 4 introduces an algebraic sequence-based model for reconstructing a most recent common ancestor of two bacterial genomes arising by the inversion and deletion DNA rearrangement operations. We show that the distance to this most recent common ancestor corresponds to the solution of a new combinatorial optimisation problem involving the symmetric inverse category, briefly discuss the complexity of this problem, and provide a polynomial time algorithm for a special case of this problem where one of the genomes arises by deletions only.

We finish with Chapter 5, which provides an algebraic framework that generalises the topological models of bacterial genomes introduced by Ernst and Sumners. These knotbased models are used to investigate the physical mechanisms of site-specific recombination processes by representing them as operations acting on tangles or braids. However, just as sequence-based approaches omit considerations of genome topology, these topologically motivated models of bacterial genomes omit considerations of DNA sequence information. With this in mind we introduce an algebraic model of bacterial genomes that accounts for both genome topology and genome sequence information simultaneously, and use this model to algebraically describe the action of the Gin recombination system of bacteriophage µ.

Date of Award	2024
Original language	English
Awarding Institution	Western Sydney University
Supervisor	Andrew Francis (Supervisor) & James East (Supervisor)