New applications of interval generators to genome comparison. (English) Zbl 1236.92023

Summary: We address two different problems related to conserved regions in \(K\geqslant 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 A. Bergeron et al. [see Lect. Notes Computer Sci. 2697, 68–79 (2003; Zbl 1236.92020)] 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)\) time the \(N\) conserved intervals of \(K\) such permutations on n elements, and (2) a method to enumerate in \(O(Kn)\) time the irreducible conserved intervals of those \(K\) permutations. Secondly, it may be used to solve in \(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.


92C40 Biochemistry, molecular biology
92D10 Genetics and epigenetics
05A05 Permutations, words, matrices
68W32 Algorithms on strings
92-08 Computational methods for problems pertaining to biology
92-04 Software, source code, etc. for problems pertaining to biology


Zbl 1236.92020


Full Text: DOI


[1] Angibaud, S.; Fertin, G.; Rusu, I.; Thevenin, A.; Vialette, S., On the approximability of comparing genomes with duplicates, J. graph algorithms appl., 13, 19-53, (2009) · Zbl 1170.68049
[2] Bergeron, A.; Stoye, J., On the similarity of sets of permutations and its applications to genome comparison, J. comput. biol., 13, 1340-1354, (2006)
[3] Bergeron, A.; Heber, S.; Stoye, J., Common intervals and sorting by reversals: a marriage of necessity, Bioinformatics, 18, S54-S63, (2002)
[4] Bergeron, A.; Chauve, C.; de Montgolfier, F.; Eaffinot, M., Computing common intervals of k permutations, with applications to modular decomposition of graphs, SIAM J. discrete mathematics, 22, 1022-1039, (2008) · Zbl 1190.05044
[5] Bernt, M.; Merkle, D.; Eamsch, K.; Fritzsch, G.; Perseke, M.; Bernhard, D.; Schlege, M.; Stadler, P.F.; Middendorf, M., Crex: inferring genomic rearrangements based on common intervals, Bioinformatics, 23, 2957-2958, (2007)
[6] G. Fertin, I. Rusu, Computing genomic distances: An algorithmic viewpoint, in: M. Elloumi, A.Y. Zomaya (Eds.), Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, Wiley Series in Bioinformatics, 2011, pp. 773-798 (Chapter 34).
[7] Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S., Combinatorics of genome rearrangements, (2009), MIT Press · Zbl 1170.92022
[8] Schmidt, T.; Stoye, J., Quadratic time algorithms for finding common intervals in two and more sequences, (), 347-358 · Zbl 1104.92025
[9] Uno, T.; Yagiura, M., Fast algorithms to enumerate all common intervals of two permutations, Algorithmica, 26, 290-309, (2000) · Zbl 0949.68168
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.