Evan MacKinnon
Computer Science Department
Okanagan College

and

Dakota Joiner
Computer Science Department
Okanagan College

An approach towards generating k-leaf powers for phylogenetic tree construction

Time & Date:  4 p.m., Wednesday, April 27, 2022
Location: Room E102 and via Zoom (see email and registration information), Computer Science Department, Okanagan College
Registration is open now: https://events.vtools.ieee.org/m/312801

Abstract:

Phylogeny is the evolutionary history of a species or group of organisms. Evolutionary trees can be analogized to graph trees, thus determination of these structures aids in inferring the evolutionary history of groups of organisms, extant and extinct. K-leaf power graphs enhance the ability of researchers to map paralogous and xenologous speciation events in what is a considerably difficult area to correctly predict past relationships.

Forbidden subgraph characterization is a method by which to characterize a graph class with a set of graphs that do not belong to that class. Identification of minimal forbidden induced
subgraphs is one method of characterizing the k-leaf powers of graph trees. A tree is a k-leaf power if, and only if, the leaves are connected by at most distance k. Structures for 2-leaf, 3-leaf, and 4-leaf powers are well understood, however, there does not exist a published list of forbidden subgraph leaf powers for values of k ≥ 4. In service of cladistics, k-leaf powers are frequently edited by adding or removing nodes and edges to the closest “proper” representation of a pairwise comparison of groups of organisms.

We demonstrate a deterministic, reductionist approach to generating 4-leaf, 5-leaf, and 6-leaf powers using Python, the graph library Networkx, and the Nauty suite of graph generation and labelling programs. The list of non-k-leaf powers in this range has not been proven finite, so this approach does not cover all possible structures should the list be infinite.

Speakers Bio:

• Evan MacKinnon is currently studying computer science at Okanagan College and will receive his bachelor’s degree in June 2022.
• Dakota Joiner graduated with a Bachelor of Science in Chemistry and a Bachelor of Science in Medical Biochemistry from the University of British Columbia in 2014. He is currently studying computer science and data science at Okanagan College.

For further information please contact: Youry Khmelevsky (email: Youry at IEEE.org) and subscribe for the news at https://listserv.ieee.org/cgi-bin/wa?SUBED1=okanagan&A=1)
Pizza and Refreshments will be provided