Critical phenomena in sequence matching

DOI10.1214/AOP/1176992808MaRDI QIDQ1064665zbMATH OpenOpenAlexWikidataFDO

Authors Richard Arratia, Michael S. Waterman

Publication date 1985

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

Full work available at URL https://doi.org/10.1214/aop/1176992808

zbMATH Keywords

entropyKullback-Leibler distancephase transitionsequence matching

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Measures of information, entropy (94A17)

Recommendations

• scientific article; zbMATH DE number 3963627
• An Erdős-Rényi law with shifts
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• A Phase Transition for the Distribution of Matching Blocks
• An extreme value theory for sequence matching

Cited in

(26)

• Matching with shift for one-dimensional Gibbs measures
• An Erdős-Rényi law with shifts
• String matching: The ergodic case
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• Rényi entropy and pattern matching for run-length encoded sequences
• A Probabilistic Analysis of a String Editing Problem and its Variations
• Runs, scans and urn model distributions: A unified Markov chain approach
• A comparison of scores of two protein structures with foldings
• Path reversal, islands, and the gapped alignment of random sequences
• First Occurrence in Pairs of Long Words: A Penney-ante Conjecture of Pevzner
• A Phase Transition for the Distribution of Matching Blocks
• scientific article; zbMATH DE number 3963627 (Why is no real title available?)
• Critical phenomena for sequence matching with scoring
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• Matching of observations of dynamical systems, with applications to sequence matching
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• Non-parametric change-point estimation using string matching algorithms
• Significance levels for biological sequence comparison using non-linear similarity functions
• Weak runs in sequences of binary trials
• A note on the longest matching consecutive subsequence
• Longest common substring for random subshifts of finite type
• An extreme value theory for sequence matching
• On the shortest distance between orbits and the longest common substring problem
• A nonlinear measure of subalignment similarity and its significance levels
• Matching strings in encoded sequences
• A phase transition for the minimum free energy of secondary structures of a random RNA

This page was built for publication: Critical phenomena in sequence matching

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