A phase transition for the score in matching random sequences allowing deletions
type: Item
instance of: scholarly article
title: A phase transition for the score in matching random sequences allowing deletions
zbMATH Open document ID: 0809.62008
author: Richard Arratia
author: Michael S. Waterman
published in: The Annals of Applied Probability
publication date: 1995-04-02T00:00:00Z
review text: The paper examines a sequence matching problem (known as string matching in the computer science literature) involving the optional alignment score for contiguous subsequences, rewarding matches and penalizing for deletions and mismatches. This score is used by biologists comparing pairs of DNA or protein sequences. It is proved that for two sequences of length \(n\), as \(n \to \infty\), there is a phase transition between linear growth in \(n\), when the penalty parameters are small, and logarithmic growth in \(n\), when the penalties are large. The results are valid for independent sequences with iid or Markov letters. The phase transition is also established for more general scoring schemes allowing general letter-to-letter alignment penalties and block deletion penalties. A general method for applying the bounded increments martingale method to Lipschitz functionals of marked processes is given.
Mathematics Subject Classification ID: 62E20
Mathematics Subject Classification ID: 62P10
Mathematics Subject Classification ID: 62P99
zbMATH DE Number: 591428
zbMATH Keywords: longest common subsequence
zbMATH Keywords: large deviations
zbMATH Keywords: Azuma-Hoeffding
zbMATH Keywords: percolation
zbMATH Keywords: sequence matching problem
zbMATH Keywords: string matching
zbMATH Keywords: optional alignment score
zbMATH Keywords: contiguous subsequences
zbMATH Keywords: rewarding matches
zbMATH Keywords: deletions
zbMATH Keywords: mismatches
zbMATH Keywords: DNA
zbMATH Keywords: protein sequences
zbMATH Keywords: phase transition
zbMATH Keywords: linear growth
zbMATH Keywords: logarithmic growth
zbMATH Keywords: general letter-to-letter alignment penalties
zbMATH Keywords: block deletion penalties
zbMATH Keywords: bounded increments martingale method
zbMATH Keywords: Lipschitz functionals of marked processes
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1177005208
OpenAlex ID: W2041976742
DOI: 10.1214/AOAP/1177005208
description: scientific article; zbMATH DE number 591428