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