An iterative approach to determining the length of the longest common subsequence of two strings

DOI10.1023/B:MCAP.0000045088.88240.3AzbMATH Open1056.92044OpenAlexW2008462984MaRDI QIDQ1762882FDOQ1762882

Authors: Hilary S. Booth, Shevarl F. MacNamara, Ole M. Nielsen, Susan R. Wilson 

Publication date: 11 February 2005

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

Full work available at URL: https://doi.org/10.1023/b:mcap.0000045088.88240.3a

Recommendations

• Longest common subsequences
• scientific article; zbMATH DE number 2079331
• The rate of convergence of the mean length of the longest common subsequence
• Improved bounds on the average length of longest common subsequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences

zbMATH Keywords

genomicslongest common subsequencesequence alignmentsimiliarity between biological sequencesChvátal-Sankoff constant

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Cited In (7)

• Lower bounds for moments of global scores of pairwise Markov chains
• Longest common subsequences
• Distribution of the length of the longest common subsequence of two multi-state biological sequences
• Dynamic and internal longest common substring
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• The rate of the convergence of the mean score in random sequence comparison
• Approximation to the mean curve in the LCS problem

This page was built for publication: An iterative approach to determining the length of the longest common subsequence of two strings

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