×

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

Software:

CREx
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 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)
[2] 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
[3] 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
[4] 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
[5] 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)
[6] Blin, Guillaume; Faye, David; Stoye, Jens, Finding nested common intervals efficiently, J. Comput. Biol., 17, 9, 1183-1194, (2010)
[7] 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
[8] Heber, Steffen; Mayr, Richard; Stoye, Jens, Common intervals of multiple permutations, Algorithmica, 60, 2, 175-206, (2011) · Zbl 1215.68163
[9] Opatrny, Jaroslav, Total ordering problem, SIAM J. Comput., 8, 1, 111-114, (1979) · Zbl 0395.68065
[10] 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
[11] Rusu, Irena, Permutation reconstruction from minmax-betweenness constraints, Discrete Appl. Math., 207, 106-119, (2016) · Zbl 1337.05005
[12] 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.