Common intervals of trees (Q834996)

From the introduction: In this paper we consider the problem of finding common intervals of trees, a generalization of the concept of common intervals in permutations. Common intervals have applications in many dif- ferent fields. Some genetic algorithms using subtour exchange crossover based on common intervals have been proposed for sequencing problems such as the traveling salesman problem or the single machine scheduling problem. In a bioinformatical context, common intervals are used to detect possible functional associations between genes, to compute the reversal distance between genomes, and to define a similarity measure for gene order permutations. A related problem is the consecutive arrangement problem, defined as follows: Given a finite set \(X\) and a collection \(S\) of subsets of \(X\), find all permu- tations of \(X\) where the members of each subset \(S \in \mathcal S\) occur consecutively. Finding all common intervals of a set of permutations reverses this problem. Here we further generalize to find common intervals in a family of labeled trees. The notion of intervals in permutations is replaced by connected components in trees. If we represent permu- tations as paths, both definitions coincide. Many of the results remain unchanged, but in contrast to the case for permutations, a tree can have exponentially many intervals. Common intervals in trees could be used as a measure of consensus among trees, and to mine tree-structured data like XML documents, or chemical compounds. A similar problem is the leaf-agree subtree problem [Y.-L- Lin and T.-S. Hsu, ''Efficient algorithms for descendent subtrees comparison of phylogenetic trees with applications to co-evolutionary classifications in bacterial genome,'' Lect. Notes Comput. Sci. 2906, 339-351 (2003; Zbl 1205.92055)], also mentioned as the common subtree problem in [ M. Yagiura, ''Studies on metaheuristic algorithms for combinatorial optimization problems, '' Ph.D. thesis, Dept. Appl. Math. Phys., Graduate School of Informatics, Kyoto University, Kyoto, Japan, 1999]. Starting from k rooted trees of size n with only leaves carrying labels, the problem is to find all k-tuples of induced subtrees with the same set of leaf labels (leaf-agree subtrees). The major difference be- tween common intervals and leaf-agree subtrees is that the latter do not consider interior nodes. The number of non-trivial leaf-agree subtrees is bounded by the number of interior nodes, and they can be found in O(kn) time in the paper cited above.