Sorting With Forbidden Intermediates

A wide range of applications, most notably in comparative
genomics, involve the computation of a shortest sorting sequence of op-
erations for a given permutation, where the set of allowed operations
is fixed beforehand. Such sequences are useful for instance when recon-
structing potential scenarios of evolution between species, or when trying
to assess their similarity. We revisit those problems by adding a new con-
straint on the sequences to be computed: they must avoid a given set of forbidden intermediates, which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution.

Download link: manuscript.