An extreme value theory for sequence matching
type: Item
instance of: scholarly article
title: An extreme value theory for sequence matching
zbMATH Open document ID: 0602.62015
author: Richard Arratia
author: Louis Gordon
author: Michael S. Waterman
published in: The Annals of Statistics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 62E20
Mathematics Subject Classification ID: 62P10
Mathematics Subject Classification ID: 92D10
zbMATH DE Number: 3971966
zbMATH Keywords: distribution of the longest contiguous run of matches
zbMATH Keywords: negative binomial
zbMATH Keywords: extreme value distribution
zbMATH Keywords: DNA sequence
zbMATH Keywords: bacteriophage lambda
reviewed by: Susan R. Wilson
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aos/1176350045
OpenAlex ID: W2093189601
Wikidata QID: Q104764149
DOI: 10.1214/AOS/1176350045
description: scientific article; zbMATH DE number 3971966