Repetition-free longest common subsequence of random sequences

DOI10.1016/J.DAM.2015.07.005zbMATH Open1339.05004arXiv1305.4883OpenAlexW1867483677MaRDI QIDQ299053FDOQ299053

Marcos Kiwi, Cristina G. Fernandes

Publication date: 22 June 2016

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

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.

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

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

zbMATH Keywords

common subsequencerandom sequencesrepetition-free subsequence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Small Longest Tandem Scattered Subsequences
• Repetition-free longest common subsequence
• Title not available (Why is that?)
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Sparse long blocks and the micro-structure of the longuest common subsequences
• Longest common substring for random subshifts of finite type

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)