Thermodynamical approach to the longest common subsequence problem

DOI10.1007/s10955-008-9533-zzbMath1214.82066OpenAlexW1977583019MaRDI QIDQ937112

Saba Amsalu, Marina Vachkovskaia, Heinrich III Matzinger

Publication date: 20 August 2008

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10955-008-9533-z

zbMATH Keywords

interacting particle systemslongest common subsequenceoptimal sequence alignment

Mathematics Subject Classification ID

Combinatorics on words (68R15) Interacting particle systems in time-dependent statistical mechanics (82C22) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Related Items (1)

Optimality regions and fluctuations for Bernoulli last passage models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• General methods of sequence comparison
• On the longest common increasing binary subsequence
• An Efron-Stein inequality for nonsymmetric statistics
• Some limit results for longest common subsequences
• Large deviations for increasing sequences on the plane
• Bounding the expected length of longest common subsequences and forests
• Exact limiting shape for a simplified model of first-passage percolation on the plane
• 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
• Hammersley's interacting particle process and longest increasing subsequences
• 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
• Longest common subsequences of two random sequences
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
• On the connection between oriented percolation and contact process

This page was built for publication: Thermodynamical approach to the longest common subsequence problem