An extreme value theory for sequence matching
Suppose there are two finite sequences \(X_ 1,X_ 2,...,X_ m\) and \(Y_ 1,Y_ 2,...,Y_ n\) where the letters \(\{X_ i\}\) and \(\{Y_ j\}\) are chosen i.i.d. on a countable alphabet with \(p=P\{X_{\ell}=Y_{\ell}\}\in (0,1)\). This paper studies the distribution of the longest contiguous run of matches between the X's and Y's, allowing at most k mismatches. The distribution is closely approximated by that of the maximum of (1-p)mn i.i.d. negative binomial random variables. The latter is shown to behave like the integer part of an extreme value distribution. Approximations to the expectation and the variance are found. The paper concludes with an example in which segments taken from the DNA sequence of the bacteriophage lambda are compared. The authors attribute the lack of fit from asymptotic prediction to the small sample properties of the distribution of the maximum k-interrupted match run length. However, this reviewer's experience is that the i.i.d. assumption is usually not valid for such data, and so this may be the cause of the lack of fit. Corresponding results for the more difficult case of insertions and deletions are still outstanding.
- Critical phenomena in sequence matching
- A nonlinear measure of subalignment similarity and its significance levels
- Significance levels for biological sequence comparison using non-linear similarity functions
- Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons
- A probabilistic approach to antigen-antibody recognition
- Pattern matching between two non-aligned random sequences
- On the tail probability of the longest well-matching run.
- On the shortest distance between orbits and the longest common substring problem
- A Poisson approximation for sequence comparisons with insertions and deletions
- A comparison of scores of two protein structures with foldings
- Long match patterns in random sequences
- Longest common substring for random subshifts of finite type
- Matching of observations of dynamical systems, with applications to sequence matching
- Extreme value theory in some statistical analysis of genomic sequences
- Approximate word matches between two random sequences
- scientific article; zbMATH DE number 3963627 (Why is no real title available?)
- A Phase Transition for the Distribution of Matching Blocks
- A Probabilistic Analysis of a String Editing Problem and its Variations
- An Eulerian path approach to local multiple alignment for DNA sequences
- Asymptotics for local maximal stack scores with general loop penalty function
- General methods of sequence comparison
- Maximum-likelihood estimation of the statistical distribution of Smith- Waterman local sequence similarity scores
- 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: An extreme value theory for sequence matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1081998)
