Thermodynamical approach to the longest common subsequence problem

DOI10.1007/S10955-008-9533-ZMaRDI QIDQ937112zbMATH OpenOpenAlexFDO

Authors Saba Amsalu, M. Vachkovskaia, Heinrich 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

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

Recommendations

• The longest common subsequence problem revisited
• Distribution of the length of the longest common subsequence of two multi-state biological sequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• scientific article; zbMATH DE number 6161488
• The constrained longest common subsequence problem
• scientific article; zbMATH DE number 6161102
• Multivariate fine-grained complexity of longest common subsequence
• A hyper-heuristic for the longest common subsequence problem
• Hydrodynamical methods for analyzing longest increasing subsequences
• Optimal alignments of longest common subsequences and their path properties

Cites work

• A phase transition for the score in matching random sequences allowing deletions
• An Efron-Stein inequality for nonsymmetric statistics
• Approximation to the mean curve in the LCS problem
• Bounding the expected length of longest common subsequences and forests
• Exact limiting shape for a simplified model of first-passage percolation on the plane
• Expected length of the longest common subsequence for large alphabets
• General methods of sequence comparison
• Hammersley's interacting particle process and longest increasing subsequences
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 5205668 (Why is no real title available?)
• Large deviations for increasing sequences on the plane
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• Longest common subsequences of two random sequences
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
• On the connection between oriented percolation and contact process
• On the longest common increasing binary subsequence
• Some limit results for longest common subsequences
• Standard deviation of the longest common subsequence
• The rate of convergence of the mean length of the longest common subsequence
• Upper bounds for the expected length of a longest common subsequence of two binary sequences

Cited in

(3)

• Optimality regions and fluctuations for Bernoulli last passage models
• Bethe ansatz solution of the finite Bernoulli matching model of sequence alignment
• Distribution of the length of the longest common subsequence of two multi-state biological sequences

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

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