On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions

DOI10.1007/s11009-010-9206-7zbMath1253.60032MaRDI QIDQ2276418

Jüri Lember, Märt Toots, Stanislaw Barder, Heinrich III Matzinger

Publication date: 5 November 2012

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11009-010-9206-7

zbMATH Keywords

longest common subsequence; large deviation inequality; suboptimal alignment

Mathematics Subject Classification ID

60C05: Combinatorial probability

60F10: Large deviations

92D20: Protein sequences, DNA sequences

Related Items

Optimal alignments of longest common subsequences and their path properties, Lower bounds for moments of global scores of pairwise Markov chains

Cites Work

• Unnamed Item
• A phase transition for the score in matching random sequences allowing deletions
• The rate of convergence of the mean length of the longest common subsequence
• Sequence comparison significance and Poisson approximation
• An iterative approach to determining the length of the longest common subsequence of two strings
• Standard deviation of the longest common subsequence
• Approximation to the mean curve in the LCS problem
• Expected length of the longest common subsequence for large alphabets
• Biological Sequence Analysis
• Computational Genome Analysis