# Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment

Saba Amsalu; Heinrich Matzinger; Serguei Popov

ESAIM: Probability and Statistics (2007)

- Volume: 11, page 281-300
- ISSN: 1292-8100

## Access Full Article

top## Abstract

top## How to cite

topAmsalu, Saba, Matzinger, Heinrich, and Popov, Serguei. "Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment." ESAIM: Probability and Statistics 11 (2007): 281-300. <http://eudml.org/doc/250100>.

@article{Amsalu2007,

abstract = {
We investigate the optimal alignment of two
independent random sequences of length n. We provide
a polynomial lower bound for the probability of the optimal alignment
to be macroscopically non-unique. We furthermore establish
a connection between the transversal fluctuation and
macroscopic non-uniqueness.
},

author = {Amsalu, Saba, Matzinger, Heinrich, Popov, Serguei},

journal = {ESAIM: Probability and Statistics},

keywords = {Longest common subsequence; path property; longitudinal fluctuation;
transversed fluctuation.; longest common subsequence; transversed fluctuation},

language = {eng},

month = {6},

pages = {281-300},

publisher = {EDP Sciences},

title = {Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment},

url = {http://eudml.org/doc/250100},

volume = {11},

year = {2007},

}

TY - JOUR

AU - Amsalu, Saba

AU - Matzinger, Heinrich

AU - Popov, Serguei

TI - Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment

JO - ESAIM: Probability and Statistics

DA - 2007/6//

PB - EDP Sciences

VL - 11

SP - 281

EP - 300

AB -
We investigate the optimal alignment of two
independent random sequences of length n. We provide
a polynomial lower bound for the probability of the optimal alignment
to be macroscopically non-unique. We furthermore establish
a connection between the transversal fluctuation and
macroscopic non-uniqueness.

LA - eng

KW - Longest common subsequence; path property; longitudinal fluctuation;
transversed fluctuation.; longest common subsequence; transversed fluctuation

UR - http://eudml.org/doc/250100

ER -

## References

top- D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.)36 (1999) 413–432. Zbl0937.60001
- K.S. Alexander, The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab.4 (1994) 1074–1082. Zbl0812.60014
- R. Arratia and M.S. Waterman, A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Probab.4 (1994) 200–225. Zbl0809.62008
- J. Baik, P. Deift and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc.12 (1999) 1119–1178. Zbl0932.05001
- V. Chvatal and D. Sankoff, Longest common subsequences of two random sequences. J. Appl. Probability12 (1975) 306–315. Zbl0313.60008
- P. Clote and R. Backofen, Computational molecular biology. An introduction. Wiley Series in Mathematical and Computational Biology. John Wiley & Sons Ltd., Chichester (2000). Zbl0955.92013
- R. Hauser and H. Matzinger, Local uniqueness of alignments with af fixed proportion of gaps. Submitted (2006).
- C.D. Howard, Models of first-passage percolation, in Probability on discrete structures, Encyclopaedia Math. Sci.110, Springer, Berlin (2004) 125–173. Zbl1206.82048
- C.D. Howard and C.M. Newman, Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab.29 (2001) 577–623. Zbl1062.60099
- K. Johansson, Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields116 (2000) 445–456. Zbl0960.60097
- J. Lember and H. Matzinger, Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006). Zbl1111.60081
- C.M. Newman and M.S.T. Piza, Divergence of shape fluctuations in two dimensions. Ann. Probab.23 (1995) 977–1005. Zbl0835.60087
- P.A. Pevzner, Computational molecular biology. An algorithmic approach. Bradford Books, MIT Press, Cambridge, MA (2000). Zbl0972.92011
- M.J. Steele, An Efron-Stein inequality for non-symmetric statistics. Annals of Statistics14 (1986) 753–758. Zbl0604.62017
- M.S. Waterman, Estimating statistical significance of sequence alignments. Phil. Trans. R. Soc. Lond. B344 (1994) 383–390.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.