Tools for Computational Biology. Brauer Monoid and Phylogenetic Networks

In this thesis, we explore the Brauer monoid and phylogenetic networks. The former is an algebraic structure of interest in semigroup theory which is closely related to perfect matchings and has been adapted as a tool for studying RNA secondary structures, while the latter is a model for evolutionary relationships between a given set of species. We begin by exploring the factorization problem for the Brauer monoid, i.e. how its elements could be decomposed into simpler ones. In particular, we present two methods: a naive one that uses heuristics, which was useful for bootstrapping the research for the paper [Marchei and Merelli, 2022], but did not always return the optimal solution, and another method that solves this problem optimally in O(N4 ) and, according to our knowledge, is the first one to run in polynomial time. We then use these methods to extend a work, introduced in 1993 by Kauffman and Magarshak, and show how some RNA secondary structures are reflected in the Brauer monoid factorization. We then move on to study phylogenetic networks and describe how they can be encoded using the language of set covers (a generalization of perfect matchings). This turns out to be a useful tool not only for describing well-known classes of networks by just imposing new axioms to the covers, but also useful for studying new classes that have non-trivial intersections with existing ones. We explore one of such classes and name it spinal networks.