English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Common intervals of K permutations over the same set of n elements werefirstly investigated by T. Uno and M.Yagiura (Algorithmica, 26:290:309, 2000),who proposed an efficient algorithm to find common intervals when K=2. Severalparticular classes of intervals have been defined since then, e.g. conservedintervals and nested common intervals, with applications mainly in genomecomparison. Each such class, including common intervals, led to the developmentof a specific algorithmic approach for K=2, and - except for nested commonintervals - for its extension to an arbitrary K.  In this paper, we propose a common and efficient algorithmic framework forfinding different types of common intervals in a set P of K permutations, witharbitrary K. Our generic algorithm is based on a global representation of theinformation stored in P, called the MinMax-profile of P, and an efficient datastructure, called an LR-stack, that we introduce here. We show that commonintervals (and their subclasses of irreducible common intervals and same-signcommon intervals), nested common intervals (and their subclass of maximalnested common intervals) as well as conserved intervals (and their subclass ofirreducible conserved intervals) may be obtained by appropriately setting theparameters of our algorithm in each case. All the resulting algorithms run inO(Kn+N)-time and need O(n) additional space, where N is the number ofsolutions. The algorithms for nested common intervals and maximal nested commonintervals are new for K>2, in the sense that no other algorithm has been givenso far to solve the problem with the same complexity, or better. The otheralgorithms are as efficient as the best known algorithms.

MinMax-Profiles: A Unifying View of Common Intervals, Nested Common Intervals and Conserved Intervals of K Permutations