Site Search
Computer Science


Imran Ahmad, Ph.D.Dr. Imran Ahmad
Dr. Imran Ahmad
Dr. Robert KentDr. Robert Kent
Dr. Robert Kent
Windsor WaterfrontWindsor Waterfront Park
Windsor Waterfront Park
Dr. Luis RuedaDr. Luis Rueda
Dr. Luis Rueda
Jessica Chen, Ph.D.Dr. Jessica Chen
Dr. Jessica Chen
Lambton TowerLambton Tower
Lambton Tower
Dr. Scott GoodwinDr. Scott Goodwin
Dr. Scott Goodwin
Dr. Ziad Kobti lecturingDr. Ziad Kobti
Dr. Ziad Kobti
Xiaobu Yuan, Ph.D.Dr. Xiaobu Yuan
Dr. Xiaobu Yuan
Robin Gras, Ph.D.Dr. Robin Gras
Dr. Robin Gras
Christie Ezeife, Ph.D.Dr. Christie Ezeife
Dr. Christie Ezeife
Arunita Jaekel, Ph.D.Dr. Arunita Jaekel
Dr. Arunita Jaekel
Alioune Ngom, Ph.D.Dr. Alioune Ngom
Dr. Alioune Ngom

Genome Matrices and the Median Problem

Add this event into your calendar using the iCAL format
  • Thu, 05/18/2017 - 2:00pm - 3:00pm

Dr. Joao Meidanis
Joint work with JPP Zanetti and P Biller

Date:  Thursday, May 18th, 2017
Time: 2:00 pm
Location: Lambton Tower, 3105

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 paper, we model genomes as matrices and study the matrix median problem using the rank distance. It is known that, for any metric distance, at least one of the corners is a 4/3-approximation of the median. Our results allow us to compute up to three additional matrix median candidates, all of them with approximation ratios at least as good as the best corner, when the input matrices come from genomes. We also show a class of instances where our candidates are optimal. From the application point of view, it is usually more interesting to locate medians farther from the corners, and therefore, these new candidates are potentially more useful. In addition to the approximation algorithm, we suggest a heuristic to get a genome from an arbitrary square matrix. This is useful to translate the results of our median approximation algorithm back to genomes, and it has good results in our tests. To assess the relevance of our approach in the biological context, we ran simulated evolution tests and compared our solutions to those of an exact DCJ median solver. The results show that our method is capable of producing very good candidates.


Bio: Joao Meidanis received his Ph.D from the University of Wisconsin-Madison, with a thesis on algorithms for DNA fragment assembly and gene functional prediction. He is a faculty member of the University of Campinas, where he founded the Computational Biology group. He has coordinated the bioinformatic analysis for several genome projects and is the director of the consulting enterprise Scylla Bioinformatics.

See More: