A General Method for Common Intervals

Given an elementary chain of vertex set V, seen as a labelling of V by the set {1,..., n = |V |}, and another discrete structure over V, say a graph G, the problem of common intervals is to compute the induced subgraphs G[I], such that I is an interval of [1, n] and G[I] satisfies some property Π (as for example Π = ”being connected”). This kind of problems comes from comparative genomic in bioinformatics, mainly when the graph G is a chain or a tree [11, 10, 2]. When the family of intervals is closed under intersection, we present here the combination of two approaches, namely the idea of potential beginning developed in [13, 6] and the notion of generator as defined in [4]. This yields a very simple generic algorithm to compute all common intervals, which gives optimal algorithms in various applications. For example in the case where G is a tree, our framework yields the first linear time algorithms for the two properties: ”being connected ” and ”being a path”. In the case where G is a chain, the problem is known as: common intervals of two permutations [13], our algorithm provides not only the set of all common intervals but also with some easy modifications a tree structure that represents this set