Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment

DOI10.1051/ps:2007014zbMath1181.60141OpenAlexW2035879455MaRDI QIDQ5429605

Saba Amsalu, Heinrich III Matzinger, Serguei Popov

Publication date: 30 November 2007

Published in: ESAIM: Probability and Statistics (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=PS_2007__11__281_0

zbMATH Keywords

longest common subsequencepath propertylongitudinal fluctuationtransversed fluctuation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Related Items

Optimal alignments of longest common subsequences and their path properties, Thermodynamical approach to the longest common subsequence problem, Standard deviation of the longest common subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstruction of periodic sceneries seen along a random walk
• An Efron-Stein inequality for nonsymmetric statistics
• 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
• Transversal fluctuations for increasing subsequences on the plane
• Geodesics and spanning trees for Euclidean first-passage percolation.
• Divergence of shape fluctuations in two dimensions
• Longest common subsequences of two random sequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem