Data: 19/12/2017

Título: Genome Matrices and the Median Problem

Palestrante: João Meidanis, IC-UNICAMP.
Data: 19 de dezembro de 2017, 14 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.

Resumo: 

The genome median problem is an important problem in phylogenetic reconstruction under rearrangement models. It can be stated as follows: Given three genomes, find a fourth that minimizes the sum of the pairwise rearrangement distances between it and the three input genomes. In this talk, we model genomes as orthogonal matrices and study the matrix median problem using the rank distance. Perhaps surprisingly, this yields a biologically significant distance. We present the first polynomial-time algorithms to compute medians with respect to a sophisticated distance. In addition to approximation and exact algorithms, we suggest heuristics to get a genome from an arbitrary square matrix. This is useful to translate the results of our median algorithms back to genomes, and it shows good results in our tests. To assess the relevance of our approach in the biological context, we ran simulated evolution tests and compare to those of an exact DCJ median solver. The results show that our our method is capable of solving practical problems of a thousand genes within seconds.

Confira aqui a apresentação