We investigate the optimal alignment of two independent random sequences of length . 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.
Mots-clés : longest common subsequence, path property, longitudinal fluctuation, transversed fluctuation
@article{PS_2007__11__281_0,
author = {Amsalu, Saba and Matzinger, Heinrich and Popov, Serguei},
title = {Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment},
journal = {ESAIM: Probability and Statistics},
pages = {281--300},
publisher = {EDP-Sciences},
volume = {11},
year = {2007},
doi = {10.1051/ps:2007014},
mrnumber = {2320822},
zbl = {1181.60141},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ps:2007014/}
}
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 PY - 2007 SP - 281 EP - 300 VL - 11 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ps:2007014/ DO - 10.1051/ps:2007014 LA - en ID - PS_2007__11__281_0 ER -
%0 Journal Article %A Amsalu, Saba %A Matzinger, Heinrich %A Popov, Serguei %T Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment %J ESAIM: Probability and Statistics %D 2007 %P 281-300 %V 11 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ps:2007014/ %R 10.1051/ps:2007014 %G en %F PS_2007__11__281_0
Amsalu, Saba; Matzinger, Heinrich; Popov, Serguei. Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment. ESAIM: Probability and Statistics, Tome 11 (2007), pp. 281-300. doi : 10.1051/ps:2007014. http://www.numdam.org/articles/10.1051/ps:2007014/
[1] and, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 (1999) 413-432. | Zbl
[2] , The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab. 4 (1994) 1074-1082. | Zbl
[3] and, A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Probab. 4 (1994) 200-225. | Zbl
[4] , and, On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 (1999) 1119-1178. | Zbl
[5] and, Longest common subsequences of two random sequences. J. Appl. Probability 12 (1975) 306-315. | Zbl
[6] and, Computational molecular biology. An introduction. Wiley Series in Mathematical and Computational Biology. John Wiley & Sons Ltd., Chichester (2000). | MR | Zbl
[7] and, Local uniqueness of alignments with af fixed proportion of gaps. Submitted (2006).
[8] , Models of first-passage percolation, in Probability on discrete structures, Encyclopaedia Math. Sci. 110, Springer, Berlin (2004) 125-173.
[9] and, Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab. 29 (2001) 577-623. | Zbl
[10] , Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445-456. | Zbl
[11] and, Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006).
[12] and, Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977-1005. | Zbl
[13] , Computational molecular biology. An algorithmic approach. Bradford Books, MIT Press, Cambridge, MA (2000). | MR | Zbl
[14] , An Efron-Stein inequality for non-symmetric statistics. Annals of Statistics 14 (1986) 753-758. | Zbl
[15] , Estimating statistical significance of sequence alignments. Phil. Trans. R. Soc. Lond. B 344 (1994) 383-390.
Cité par Sources :
