Abstract: Graphical pressing sequences have applications in computational phylogenetics: when the genes of two species are compared, the length of sequence reversals that transforms one species’s genes into the other’s measures the evolutionary distance between the two species. In this work we study “pressing sequences,” or series of operations performed on a bicolored graph (as each node is either black or white) that represent the number of gene sequence reversals required to transform the genes of one specie to another.  While a fast algorithm for finding one pressing sequence is known, it would be useful to those who study phylogenetics to know all valid pressing sequences in order to learn the sequences’ statistical properties. In this work we seek to classify how difficult it is to enumerate all possible pressing sequences from the graph by first examining the number of pressing sequences associated with random graphs.

This work is presently ongoing. 

Story of Contribution: Thus far, my contribution to the project has included reframing the the problem in terms of the Erdos-Renyi random graph model, G(n,p). I ask, what are the number of pressing sequences for G(n,p,q) where p  represents the probability of a given edge being added to the graph and where q represents the probability a node is colored black? I developed software in Sage to generate these random graphs applied a Monte Carlo simulation in order to estimate the number of pressing sequences. Currently, I am learning about the Slurm workload manager in order to run this computation heavy code on a high performance computer. 

gnpqs

Heatmaps corresponding to the average number of pressing sequences for  n = 2...7 across 10 trials. The x-axis corresponds to the "darkness" (probability of black nodes occuring) and the y-axis corresponds to the density (probability of a given edge being inserted) of the graph.

Lessons Learned: This project has furthered my understanding of areas such as linear algebra, abstract algebra, and graph theory by introducing me to material beyond the typical undergraduate curriculum as well as highlighting the interplay between fields. It has also been an exercise in reading mathematics and understanding state-of-the-art proofs and formulating helpful questions from the literature. Additionally, I have learned about computational techniques such a Monte Carlo methods and gained software development skills in Sage. 

Check out this interactive pressing game made by our colleagues at CUNY!

Team: Prof. J. Cooper, Hays Whitlatch