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

• Publication:3731417
• 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)

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

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)