Discrete Math Seminar: Gene trees and species trees: parsimony problems
- Date: 03/30/2010
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.
