Genome Matrices and the Median Problem

Speaker:João Meidanis, IC-UNICAMP.

Date: 19 dec 2017, 14h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: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 compared our to those of an exact DCJ median solver. The results show that our method is capable of solving practical problems of a thousand genes within seconds.