Título: Genome Matrices and the Median Problem
Palestrante: João Meidanis, UNICAMP
Data: 31 de outubro de 2018, 11 h.
Local: Instituto de Computação, Campus Praia Vermelha, UFF.
Resumo: The study of genome rearrangements dates back to the beginning of the twentieth century, with the seminal work by Dobzhansky, Sturtevant, and others. More recently, near the end of the century, computers entered the scene, and the first algorithms to deal with various aspects of genome rearrangements appeared. In particular, the genome median problem, which is an important tool in phylogenetic reconstruction, gained attention. 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. Among the several distances that have been proposed, the Double-Cut and Join (DCJ) distance stands out as the most widely used. In this talk, we briefly review the historic development of DCJ, and of a related distance, called rank distance, proposed by our group. We model genomes as matrices and study the matrix median problem using the rank distance. It is an open problem to find a polynomial algorithm for genomic medians using this distance. We present the state-of-the-art in this problem, with partial results, conjectures, and experimental results.
Clique aqui para saber mais sobre o Brazillian Symposium on Bioinformatics (BSB 2018)