New applications of interval generators to genome comparison

In this paper, we address two different problems related to conserved regions in K⩾2K⩾2 genomes represented as permutations. The first one requires to enumerate the conserved regions, whereas the second one asks only to count them. We show that the generator-based technique, introduced by Bergeron et al. to enumerate common intervals of K   genomes represented as permutations, may be extended following two directions. Firstly, it may be applied to signed permutations, yielding (1) a method to enumerate in O(Kn+N)O(Kn+N) time the N conserved intervals of K such permutations on n   elements, and (2) a method to enumerate in O(Kn)O(Kn) time the irreducible conserved intervals of those K   permutations. Secondly, it may be used to solve in O(Kn)O(Kn) time the counting problem, for every class of intervals which admits a so-called canonical generator. Both common and conserved intervals of K (signed) permutations admit such a generator. Although some (not all) of the above running times have already been reached by previous algorithms, it is the first time that the features shared by common and conserved intervals are exploited under a common efficient framework.