title: Easy identification of generalized common and conserved nested intervals.
abstract: In this article we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or a common (resp. conserved) interval that contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the classical notion of nested interval. We exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. We also explain how to count all b-nested intervals in O(Kn) time. New properties of the family of conserved intervals are proposed to do so.
authors.affiliation: 1 Laboratoire d'Informatique Algorithmique: Fondements et Applications, Univ. Paris Diderot , Paris, France .
authors.forename: Fabien
authors.initials: F
authors.lastname: de Montgolfier
authors.forename: Mathieu
authors.initials: M
authors.lastname: Raffinot
authors.forename: Irena
authors.initials: I
authors.lastname: Rusu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D023281:Genomics / Q000379:methods*; D005810:Multigene Family
keywords: algorithms; alignment; automata; combinatorics; strings