Genome Matrices and the Median Problem

Data
Add to Calendin 2017-11-10 00:00:00 2017-11-10 00:00:00 Genome Matrices and the Median Problem 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 matrices and study the matrix median problem using the rank distance.  We present the first polynomial-time algorithms to compute medians with respect to a sophisticated distance.  In addition to the approximation algorithm, 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. Auditório do IC Auditório do IC Auditório do IC America/Sao_Paulo public
Horário
14:00
Local
Auditório do IC
Palestrante
Prof. João Meidanis
Descrição

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 matrices and study the matrix median problem using the rank distance.  We present the first polynomial-time algorithms
to compute medians with respect to a sophisticated distance.  In addition to the approximation algorithm, 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.

Sobre o Palestrante

João Meidanis possui graduação em Bacharelado em Matemática pela Universidade de São Paulo (1980), mestrado em Ciência da Computação - University of Wisconsin - Madison (1989), mestrado em Matemática pela Universidade de São Paulo (1985) e doutorado em Ciência da Computação - University of Wisconsin - Madison (1992). Atualmente é diretor da Scylla Informática e professor titular da Universidade Estadual de Campinas. Suas áreas de atuação incluem análise de algoritmos, teoria dos grafos, biologia computacional e otimização.