Most compact parsimonious trees

Abstract

Phylogeny is the evolutionary history of a set of species, represented in the form of a tree. Construction of phylogenetic trees has traditionally focused on binary trees where all species appear on leaves. However, certain domains such as viral evolution, paleontology, linguistics, and stemmatics, often involve phylogeny inference where extant species are placed on internal nodes and polytomies are present. Previous work on this project involved designing and implementing algorithms to find the most compact most parsimonious trees that allow for extant ancestors and multifurcations. Our work expands upon this, investigating mixed-weight parsimony using Sankoff’s algorithm (see middle section). Our work also involved optimizing the existing codebase to collect data and apply the method to stemmatics.