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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ps:2007014/
[1] Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 (1999) 413-432. | Zbl
and ,[2] The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab. 4 (1994) 1074-1082. | Zbl
,[3] A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Probab. 4 (1994) 200-225. | Zbl
and ,[4] On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 (1999) 1119-1178. | Zbl
, and ,[5] Longest common subsequences of two random sequences. J. Appl. Probability 12 (1975) 306-315. | Zbl
and ,[6] Computational molecular biology. An introduction. Wiley Series in Mathematical and Computational Biology. John Wiley & Sons Ltd., Chichester (2000). | MR | Zbl
and ,[7] Local uniqueness of alignments with af fixed proportion of gaps. Submitted (2006).
and ,[8] Models of first-passage percolation, in Probability on discrete structures, Encyclopaedia Math. Sci. 110, Springer, Berlin (2004) 125-173.
,[9] Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab. 29 (2001) 577-623. | Zbl
and ,[10] Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445-456. | Zbl
,[11] Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006).
and ,[12] Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977-1005. | Zbl
and ,[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 :