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)

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