Matching with shift for one-dimensional Gibbs measures

DOI10.1214/08-AAP588MaRDI QIDQ835071zbMATH OpenFDO

Authors Cristian Giardinà, P. Collet, F. Redig

Publication date 27 August 2009

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.2165

zbMATH Keywords

Gibbs measuresstatistical mechanicssequence alignment

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider matching with shifts for Gibbsian sequences. We prove that the maximal overlap behaves as $clogn$, where $c$ is explicitly identified in terms of the thermodynamic quantities (pressure) of the underlying potential. Our approach is based on the analysis of the first and second moment of the number of overlaps of a given size. We treat both the case of equal sequences (and nonzero shifts) and independent sequences.

Recommendations

• Critical phenomena in sequence matching
• An Erdős-Rényi law with shifts
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• Critical phenomena for sequence matching with scoring
• On approximate pattern matching for a class of Gibbs random fields

Cites work

• scientific article; zbMATH DE number 3622081 (Why is no real title available?)
• scientific article; zbMATH DE number 3005966 (Why is no real title available?)
• scientific article; zbMATH DE number 783366 (Why is no real title available?)
• Critical phenomena for sequence matching with scoring
• Equilibrium states and the ergodic theory of Anosov diffeomorphisms
• Exponential approximation for hitting times in mixing processes
• Exponential distribution for the occurrence of rare patterns in Gibbsian random fields
• Gibbs measures and phase transitions
• Limit distribution of maximal non-aligned two-sequence segmental score
• Local alignment of Markov chains
• Repetition times for Gibbsian sources

Cited in

(3)

• Closest distance between iterates of typical points
• Rényi entropy and pattern matching for run-length encoded sequences
• Longest common substring for random subshifts of finite type

This page was built for publication: Matching with shift for one-dimensional Gibbs measures

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