Data Mining and Web Search Group

Genome Rearrangements Mini-Workshop

Thursday, January 27, 2011
Location: Kende building, 5th floor 507

9:00-9:45 Eric Tannier: Ohnologons and ancestral genome reconstructions

9:45-10:30 Istvan Miklos: Computational complexity of sampling genome rearrangement scenarios

10:30-11:00 Coffee break

11:00-11:45 Haris Gavranovic: An optimization method and a lower bound for matrix sandwich problem

11:45-12:30 Eszter Friedman: Multiple genome rearrangement with MCMC
Abstracts
Eric Tannier: Ohnologons and ancestral genome reconstructions

Genes, genomic segments or chromosomes are ohnologous (in reference to Susumu Ohno) when they arise from a common ancestor by a whole genome duplication event. When such a duplication is ancient, often paralogous genes are missing but there still remains traces of ohnologous segments, even if they don't show any similarity.
Ancestral genome reconstructions often come up against the shuffling of genes provoked by these events. We devise a tool to detect statistically grounded ohnologons and show how it is possible to integrate the signal they
carry to study genome evolution.
Istvan Miklos: Computational complexity of sampling genome rearrangement scenarios

The computational complexity for most of the optimization/maximum parsimony problems in genome rearrangement are known by now. On the other hand, little is known about sampling and counting problems in genome rearrangement. In this lecture, we give an overview on the sampling and counting most parsimonious rearrangement scenarios.
Haris Gavranovic: An optimization method and a lower bound for matrix sandwich problem

We study the sandwich consecutive ones property problem. In simple terms the problem states : for given 01X ternary matrix find a permutation of columns such that there is no zero element having 1 somewhere on the left and 1 somewhere on the right in the same row.
First, we recall the complexity of the problem and discuss some possible applications (Golumbic, Wassermann). We propose several constructive procedures based on C1P algorithms and TSP-reduction and apply thereafter simple local search. Based on the notion of incompatibility graph (McConnel) we exhibit forbidden structures and propose and study a computational lower bound for the problem. At the end, we discuss computational efficiency of the method applied on some real world instances.
Eszter Friedman: Multiple genome rearrangement with MCMC

We introduce a novel method for MCMC sampling Hannenhalli-Pevzner genome rearrangement scenarios on evolutionary trees by cooling down DCJ (double cut and join) scenarios. This is an extension of the recently published method by Miklos and Tannier. Their method worked for pair of genomes, here we extend it to phylogenetic trees.