Modul:   MAT591  Discrete mathematics

Decomposition trees of permutations, and how to use them for a (realistic?) study of perfect sorting by reversals.

Vortrag von Prof. Dr. Mathilde Bouvel

Datum: 03.05.16  Zeit: 11.15 - 12.15  Raum: Y27H28

I will present the problem of perfect sorting by reversals. This is a problem on (signed) permutations, but which is motivated by the study of genome rearrangements. I will show an algorithm solving this problem, due to Bérard-Bergeron-Chauve-Paul. It uses the strong interval trees of permutations (whose definition will be recalled in the talk). Those trees are also known as (substitution) decomposition trees of permutations. I will present some results and a research project related to those trees. The results are of combinatorial nature, and date back a few years. The project is more turned towards the biology application, and a lot of work is still to be done here.

This talk is based on joint works and ongoing projects with C. Chauve, M. Mishna, C. Nicaud, C. Pivoteau and D. Rossin.

It is an adaptation of my talk at the workshop "Genome rearrangement and permutation patterns" in Feb. 2016.