IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On the Computational Complexity of Genome Rearrangement

  • April 3, 2015
  • 2:30 p.m.
  • LeConte 312

Abstract

Single cut-or-join is perhaps the simplest mathematical model of genome rearrangement, prescribing a set of allowable moves to model evolution. Parsimony is a measure of the time required to "rearrange" one genome into another.

Given a collection of observed genomes related by a phylogenetic tree, let S be the set of most parsimonious labelings of the ancestors equipped with an ordering in which the rearrangements occurred. We are interested in the size of S as well as a method to quickly and uniformly sample from S.

When the phylogenetic tree is binary, Miklós, Kiss, and Tannier (2014) discovered that no polynomial-time randomized algorithm exists for sampling S unless RP=NP. In this talk, I will present some computational complexity results for the star phylogenetic tree. We will also explore similar questions for mathematically motivated problems which arose from this project.

(This is joint work with István Miklós.)

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC