BioGAP

Bacterial Genomics and Computational Group Theory. Bacterial genomes can be modelled as permutations of conserved regions. These regions are sequences of nucleotides that are identified for a set of bacterial genomes through sequence alignment, and are presumed to be preserved through the underlying process, whether through chance or selection. Once a correspondence is established between genomes and permutations, the problem of determining the evolutionary distance between genomes (in order to construct phylogenetic trees) can be tackled by use of group-theoretical tools such as the word distance in Cayley graphs, stabilizer subgroups for modelling biological constraints, using presentations for finding geodesic words, etc. Most of the groups involved in this research are well-studied (symmetric, hyperoctahedral), but the generating sets are derived from models of the biological processes, and often have different properties from standard generating sets. Furthermore, the number of regions we need to calculate with are beyond the limits of simple brute-force methods. In this talk we describe how the computational tools are used in these biological projects, and what are the algorithms that still need to be developed. We also briefly introduce our GAP package BioGAP.