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

  • Date: 03/30/2010
Cedric Chauve (Simon Fraser University)

University of British Columbia


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)


4:00 - 5:00pm, WMAX 216.