Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
ESAIM: Probability and Statistics, Tome 11 (2007), pp. 281-300.

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.

DOI : 10.1051/ps:2007014
Classification : 60K35, 60J20
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] 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. | Zbl

[2] K.S. Alexander, The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab. 4 (1994) 1074-1082. | Zbl

[3] 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. | Zbl

[4] 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. | Zbl

[5] V. Chvatal and D. Sankoff, Longest common subsequences of two random sequences. J. Appl. Probability 12 (1975) 306-315. | Zbl

[6] P. Clote and R. Backofen, Computational molecular biology. An introduction. Wiley Series in Mathematical and Computational Biology. John Wiley & Sons Ltd., Chichester (2000). | MR | Zbl

[7] R. Hauser and H. Matzinger, Local uniqueness of alignments with af fixed proportion of gaps. Submitted (2006).

[8] C.D. Howard, Models of first-passage percolation, in Probability on discrete structures, Encyclopaedia Math. Sci. 110, Springer, Berlin (2004) 125-173.

[9] C.D. Howard and C.M. Newman, Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab. 29 (2001) 577-623. | Zbl

[10] K. Johansson, Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445-456. | Zbl

[11] J. Lember and H. Matzinger, Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006).

[12] C.M. Newman and M.S.T. Piza, Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977-1005. | Zbl

[13] P.A. Pevzner, Computational molecular biology. An algorithmic approach. Bradford Books, MIT Press, Cambridge, MA (2000). | MR | Zbl

[14] M.J. Steele, An Efron-Stein inequality for non-symmetric statistics. Annals of Statistics 14 (1986) 753-758. | Zbl

[15] M.S. Waterman, Estimating statistical significance of sequence alignments. Phil. Trans. R. Soc. Lond. B 344 (1994) 383-390.

Cité par Sources :