Longest common subsequences of two random sequences

From MaRDI portal
Publication:4072574

DOI10.2307/3212444zbMath0313.60008OpenAlexW1991983464WikidataQ30050275 ScholiaQ30050275MaRDI QIDQ4072574

Václav Chvátal, David Sankoff

Publication date: 1975

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/3212444



Related Items

Periodic words, common subsequences and frogs, Maximal success durations for a semi-Markov process, Average-case analysis via incompressibility, On the variance of the optimal alignments score for binary random words and an asymmetric scoring function, Combinatorial algorithms for DNA sequence assembly, Novel evolutionary models and applications to sequence alignment problems, Lower bounds on the generalized central moments of the optimal alignments score of random sequences, Optimality regions and fluctuations for Bernoulli last passage models, Asymptotic expected number of base pairs in optimal secondary structure for random RNA using the Nussinov--Jacobson energy model, Increasing sequences of independent points on the planar lattice, Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets, Theoretical lower bound for border length minimization problem, Longest common subsequences, Rate of convergence of the mean for sub-additive ergodic sequences, Optimal alignments of longest common subsequences and their path properties, A Probabilistic Analysis of a String Editing Problem and its Variations, On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words, On an alternative sequence comparison statistic of Steele, A central limit theorem for the length of the longest common subsequences in random words, Longest Common Subsequence with Gap Constraints, On finding a longest common palindromic subsequence, Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays, The rate of the convergence of the mean score in random sequence comparison, Letter change bias and local uniqueness in optimal sequence alignments, An efficient algorithm for LCS problem between two arbitrary sequences, On the approximation of shortest common supersequences and longest common subsequences, Thermodynamical approach to the longest common subsequence problem, Large deviations-based upper bounds on the expected relative length of longest common subsequences, Universal arrays, On a Speculated Relation Between Chvátal–Sankoff Constants of Several Sequences, Distribution of the length of the longest common subsequence of two multi-state biological sequences, Lower bounds for moments of global scores of pairwise Markov chains, Sparse long blocks and the micro-structure of the longuest common subsequences, Approximation to the mean curve in the LCS problem, Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment, Unnamed Item, Standard deviation of the longest common subsequence, Order of the variance in the discrete Hammersley process with boundaries, Subsequence numbers and logarithmic concavity, A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance, Microscopic path structure of optimally aligned random sequences, On the number of coincidences of two homogeneous random walks with positive increments, Quasi-random words and limits of word sequences, Some limit results for longest common subsequences, Length of the Longest Common Subsequence between Overlapping Words, On the rate of convergence for the length of the longest common subsequences in hidden Markov models, Computing a longest common subsequence for a set of strings, An analytic study of the phase transition line in local sequence alignment with gaps, A Formula for the Mean Length of the Longest Common Subsequence, Expected length of the longest common subsequence for large alphabets, Anytime algorithms for the longest common palindromic subsequence problem, Cross-monotone subsequences, An Erdős-Rényi law with shifts, On the security margin of MAC striping, Stanislaw M. Ulam's contributions to theoretical biology, New algorithms for the LCS problem