Conservation of combinatorial structure in genome rearrangement scenarios

   Cedric Chauve, (LaCIM, Universite du Quebec a Montreal)

We investigate the problem of conservation of combinatorial structures in genome rearrangement scenarios. We characterize an interesting class of signed permutations, called perfect permutations, for which one can compute in polynomial time a reversal scenario that conserves all common intervals and is parsimonious among such scenarios. The general problem has been shown to be NP-hard (Figeac & Varre, 2004) We show that there exists a class of permutations, called commuting permutations, for which this computation can be done in linear time, while in the larger class of perfect permutations, the computation can be achieved in quasi-linear time. Our algorithms rely on an interesting relation between common intervals and the theory of modular decomposition of permutation graphs.

Work in collaboration with Severine Berard, Anne Bergeron and Christophe Paul.

Applied Algebra seminar home