Discrete Math Seminar: Gene trees and species trees: parsimony problems

A gene family is a set of genes, present in the genomes of several genomes, possibly in multiple occurrences in some genomes, that all originates from a single ancestral gene. A gene tree is a binary tree that describes evolutionary relationships between the genes of a same family, in terms of three kinds of events: speciations, duplications and losses. Phylogenomics aims at inferring, from a set of gene trees, a species tree. Here we consider the following NP-complete optimization problem: infer the species tree that minimizes the number of gene duplications. I will present two results:

- a description of tractable sets of gene trees (work with J.-P. Doyon and N. El-Mabrouk, Universite de Montreal)

- approximation algorithms for computing a parsimonious first speciation, based on edge-cut problems in graphs and hypergraphs (work with A. Ouangraoua and K. Swenson, Universite du Quebec a Montreal)