Counts of long aligned word matches among random letter sequences

DOI10.2307/1427422MaRDI QIDQ3757093zbMATH OpenOpenAlexFDO

Authors Samuel Karlin, Friedemann Ost

Publication date 1987

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/1427422

zbMATH Keywords

compound Poisson distributionlongest success runfirst-passage problemblock matchasymptotic properties of the length of the longest wordmatching word locationsspectral properties of the Markov transition matricesstrong mixing stationary Markov chains

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Miscellaneous inequalities involving matrices (15A45)

Recommendations

• Distributional regimes for the number of k -word matches between two random sequences
• Maximal length of common words among random letter sequences
• Exact distribution of word occurrences in a random sequence of letters
• Approximate word matches between two random sequences
• Exact distribution of word counts in shuffled sequences
• On the number of word occurrences in a semi-Markov sequence of letters
• A new method of approximating the probability of matching common words in multiple random sequences
• scientific article; zbMATH DE number 850337

Cited in

(27)

• String matching: The ergodic case
• On coincidences of tuples in a \(q\)-ary tree with random labels of vertices
• Maximal length of common words among random letter sequences
• Approximate word matches between two random sequences
• Generic properties of subgroups of free groups and finite presentations
• Matching among multiple random sequences
• On the height of digital trees and related problems
• An Erdős-Rényi law with shifts
• scientific article; zbMATH DE number 3963627 (Why is no real title available?)
• Improvements on the distribution of maximal segmental scores in a Markovian sequence
• scientific article; zbMATH DE number 806869 (Why is no real title available?)
• A Probabilistic Analysis of a String Editing Problem and its Variations
• Compound Poisson approximation of word counts in DNA sequences
• An accurate approximation to the distribution of the length of the longest matching word between two random DNA sequences
• A note on repeated sequences in Markov chains
• Limit distributions of extremal distances to the nearest neighbor
• Shortest distance between multiple orbits and generalized fractal dimensions
• On coincidences of tuples in a binary tree with random labels of vertices
• Maximal success durations for a semi-Markov process
• On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
• Markov Additive Processes and Repeats in Sequences
• An extreme value theory for sequence matching
• Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons
• 1-dependent stationary sequences for some given joint distributions of two consecutive random variables
• A Phase Transition for the Distribution of Matching Blocks
• Exact distribution of word counts in shuffled sequences
• Pattern matching between two non-aligned random sequences

This page was built for publication: Counts of long aligned word matches among random letter sequences

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