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
topHow 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.
- K.S. Alexander, The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab.4 (1994) 1074–1082.
- 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.
- 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.
- V. Chvatal and D. Sankoff, Longest common subsequences of two random sequences. J. Appl. Probability12 (1975) 306–315.
- P. Clote and R. Backofen, Computational molecular biology. An introduction. Wiley Series in Mathematical and Computational Biology. John Wiley & Sons Ltd., Chichester (2000).
- 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.
- C.D. Howard and C.M. Newman, Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab.29 (2001) 577–623.
- K. Johansson, Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields116 (2000) 445–456.
- J. Lember and H. Matzinger, Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006).
- C.M. Newman and M.S.T. Piza, Divergence of shape fluctuations in two dimensions. Ann. Probab.23 (1995) 977–1005.
- P.A. Pevzner, Computational molecular biology. An algorithmic approach. Bradford Books, MIT Press, Cambridge, MA (2000).
- M.J. Steele, An Efron-Stein inequality for non-symmetric statistics. Annals of Statistics14 (1986) 753–758.
- M.S. Waterman, Estimating statistical significance of sequence alignments. Phil. Trans. R. Soc. Lond. B344 (1994) 383–390.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.