\textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of K permutations
From MaRDI portal
Publication:2250447
DOI10.1016/J.TCS.2014.06.004zbMATH Open1417.68143arXiv1304.5140OpenAlexW2964173384MaRDI QIDQ2250447FDOQ2250447
Authors: Irena Rusu 
Publication date: 7 July 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: Common intervals of K permutations over the same set of n elements were firstly investigated by T. Uno and M.Yagiura (Algorithmica, 26:290:309, 2000), who proposed an efficient algorithm to find common intervals when K=2. Several particular classes of intervals have been defined since then, e.g. conserved intervals and nested common intervals, with applications mainly in genome comparison. Each such class, including common intervals, led to the development of a specific algorithmic approach for K=2, and - except for nested common intervals - for its extension to an arbitrary K. In this paper, we propose a common and efficient algorithmic framework for finding different types of common intervals in a set P of K permutations, with arbitrary K. Our generic algorithm is based on a global representation of the information stored in P, called the MinMax-profile of P, and an efficient data structure, called an LR-stack, that we introduce here. We show that common intervals (and their subclasses of irreducible common intervals and same-sign common intervals), nested common intervals (and their subclass of maximal nested common intervals) as well as conserved intervals (and their subclass of irreducible conserved intervals) may be obtained by appropriately setting the parameters of our algorithm in each case. All the resulting algorithms run in O(Kn+N)-time and need O(n) additional space, where N is the number of solutions. The algorithms for nested common intervals and maximal nested common intervals are new for K>2, in the sense that no other algorithm has been given so far to solve the problem with the same complexity, or better. The other algorithms are as efficient as the best known algorithms.
Full work available at URL: https://arxiv.org/abs/1304.5140
Recommendations
- Common intervals of multiple permutations
- scientific article; zbMATH DE number 1786460
- New applications of interval generators to genome comparison
- Fast algorithms to enumerate all common intervals of two permutations
- Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
Permutations, words, matrices (05A05) Genetics and epigenetics (92D10) Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Data structures (68P05)
Cites Work
- On the Approximability of Comparing Genomes with Duplicates
- Recursive Star-Tree Parallel Data Structure
- Title not available (Why is that?)
- Computing and Combinatorics
- Fast algorithms to enumerate all common intervals of two permutations
- Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
- New applications of interval generators to genome comparison
- Combinatorial Pattern Matching
- Automata, Languages and Programming
- Common intervals of multiple permutations
- Algorithms for Finding Gene Clusters
Cited In (8)
- Common intervals of trees
- New applications of interval generators to genome comparison
- Permutation reconstruction from MinMax-betweenness constraints
- Fast algorithms to enumerate all common intervals of two permutations
- Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
- Extending common intervals searching from permutations to sequences
- Algorithms for Finding Gene Clusters
- Title not available (Why is that?)
This page was built for publication: \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2250447)
