## Common intervals and permutation reconstruction from MinMax-betweenness constraints.(English)Zbl 1400.68150

Summary: The MinMax-Betweenness problem is defined as follows. We are given a positive integer $$n$$ and, for each $$t = 0, 1, 2, \dots, n$$, two integers $$m_t$$ and $$M_t$$ with $$m_t \leq t$$ and $$t + 1 \leq M_t$$ (this is called a MinMax-profile). The question is: Is there a permutation $$P$$ on $$\{0, 1, 2, \dots, n + 1 \}$$ such that $$m_t$$ is the minimum and $$M_t$$ is the maximum element of $$P$$ located between $$t$$ (included) and $$t + 1$$ (included), assuming 0 is the leftmost and $$n + 1$$ is the rightmost element of $$P$$?
We consider here the directed variant of the problem, where the left-to-right order of $$t$$ and $$t + 1$$ on $$P$$ is known for each $$t = 0, 1, 2, \dots, n$$. Whereas the complexity of the general directed or undirected problem is open, the particular case of the directed variant where the intervals $$[m_t . . M_t]$$ ($$t \neq 0, n + 1$$), containing the integers between $$m_t$$ (included) and $$M_t$$ (included), are linearly ordered by inclusion is polynomially solvable. In this case, the MinMax-profile is called linear.
In this paper, we use separable MinMax-subprofiles, that are intimately related to common intervals, to deal with MinMax-profiles – that we name L-reducible – which are not linear, but present decomposition properties allowing us to handle them using linear MinMax-(sub)profiles. We show that for L-reducible MinMax-profiles the Directed MinMax-Betweenness problem is solvable in polynomial time. We also give a polynomial algorithm to recognize L-reducible MinMax-profiles, with running time of $$O(n^2)$$.
Moreover, we show that the DirectedMin-Betweenness (resp. DirectedMax-Betweenness) problem, where only $$m_t$$ (resp. only $$M_t$$) is given for each $$t = 0, 1, 2, \dots, n$$, is polynomial.

### MSC:

 68R05 Combinatorics in computer science 05A05 Permutations, words, matrices 68Q25 Analysis of algorithms and problem complexity 68W05 Nonnumerical algorithms

### Keywords:

betweenness; permutation; algorithm; common intervals

CREx
Full Text:

### References:

  Adam, Zaky; Turmel, Monique; Lemieux, Claude; Sankoff, David, Common intervals and symmetric difference in a model-free phylogenomics, with an application to streptophyte evolution, J. Comput. Biol., 14, 4, 436-445, (2007)  Angibaud, Sébastien; Fertin, Guillaume; Rusu, Irena; Thévenin, Annelyse; Vialette, Stéphane, A pseudo-Boolean programming approach for computing the breakpoint distance between two genomes with duplicate genes, (RECOMB International Workshop on Comparative Genomics, (2007), Springer), 16-29 · Zbl 1170.68049  Bergeron, Anne; Chauve, Cédric; de Montgolfier, Fabien; Raffinot, Mathieu, Computing common intervals of k permutations, with applications to modular decomposition of graphs, SIAM J. Discrete Math., 22, 3, 1022-1039, (2008) · Zbl 1190.05044  Bergeron, Anne; Stoye, Jens, On the similarity of sets of permutations and its applications to genome comparison, J. Comput. Biol., 13, 7, 1340-1354, (2006) · Zbl 1236.92020  Bernt, Matthias; Merkle, Daniel; Ramsch, Kai; Fritzsch, Guido; Perseke, Marleen; Bernhard, Detlef; Schlegel, Martin; Stadler, Peter F.; Middendorf, Martin, Crex: inferring genomic rearrangements based on common intervals, Bioinformatics, 23, 21, (2007)  Blin, Guillaume; Faye, David; Stoye, Jens, Finding nested common intervals efficiently, J. Comput. Biol., 17, 9, 1183-1194, (2010)  Bui Xuan, Binh-Minh; Habib, Michel; Paul, Christophe, Revisiting T. uno and M. Yagiura’s algorithm, (International Symposium on Algorithms and Computation, (2005), Springer), 146-155 · Zbl 1173.68836  Heber, Steffen; Mayr, Richard; Stoye, Jens, Common intervals of multiple permutations, Algorithmica, 60, 2, 175-206, (2011) · Zbl 1215.68163  Opatrny, Jaroslav, Total ordering problem, SIAM J. Comput., 8, 1, 111-114, (1979) · Zbl 0395.68065  Rusu, Irena, Minmax-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of K permutations, Theor. Comput. Sci., 543, 90-111, (2014) · Zbl 1417.68143  Rusu, Irena, Permutation reconstruction from minmax-betweenness constraints, Discrete Appl. Math., 207, 106-119, (2016) · Zbl 1337.05005  Uno, Takeaki; Yagiura, Mutsunori, 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.