Repetition-free longest common subsequence of random sequences

DOI10.1016/J.DAM.2015.07.005MaRDI QIDQ299053zbMATH OpenOpenAlexFDO

Authors Cristina G. Fernandes, Marcos Kiwi

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4883

zbMATH Keywords

common subsequencerandom sequencesrepetition-free subsequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Special sequences and polynomials (11B83)

Abstract: A repetition free Longest Common Subsequence (LCS) of two sequences x and y is an LCS of x and y where each symbol may appear at most once. Let R denote the length of a repetition free LCS of two sequences of n symbols each one chosen randomly, uniformly, and independently over a k-ary alphabet. We study the asymptotic, in n and k, behavior of R and establish that there are three distinct regimes, depending on the relative speed of growth of n and k. For each regime we establish the limiting behavior of R. In fact, we do more, since we actually establish tail bounds for large deviations of R from its limiting behavior. Our study is motivated by the so called exemplar model proposed by Sankoff (1999) and the related similarity measure introduced by Adi et al. (2007). A natural question that arises in this context, which as we show is related to long standing open problems in the area of probabilistic combinatorics, is to understand the asymptotic, in n and k, behavior of parameter R.

Recommendations

• Repetition-free longest common subsequence
• Repetition-free longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• LATIN 2004: Theoretical Informatics
• Exact algorithms for the bounded repetition longest common subsequence problem

Cites work

• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• A spectral heuristic for bisecting random graphs
• Algorithms for graph partitioning on the planted partition model
• Expected length of the longest common subsequence for large alphabets
• On the Approximability of Comparing Genomes with Duplicates
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the parameterized complexity of the repetition free longest common subsequence problem
• Repetition-free longest common subsequence
• Variants of constrained longest common subsequence

Cited in

(7)

• Repetition-free longest common subsequence
• Small Longest Tandem Scattered Subsequences
• Longest common substring for random subshifts of finite type
• scientific article; zbMATH DE number 5873671 (Why is no real title available?)
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Repetition-free longest common subsequence
• Sparse long blocks and the micro-structure of the longuest common subsequences

This page was built for publication: Repetition-free longest common subsequence of random sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299053)