Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T23:40:38.576Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  19 June 2007

Saba Amsalu ,
Heinrich Matzinger  and
Serguei Popov
Saba Amsalu
Affiliation:
University of Bielefeld, Postfach 10 01 31, 33501 Bielefeld, Germany; saba@uni-bielefeld.de
Heinrich Matzinger
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332–0160, USA; matzi@math.gatech.edu
Serguei Popov
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, rua do Matão 1010, CEP 05508–090, São Paulo SP, Brasil; popov@ime.usp.br
Get access

Abstract

We investigate the optimal alignment of two independent random sequences of length n. We providea polynomial lower bound for the probability of the optimal alignmentto be macroscopically non-unique. We furthermore establisha connection between the transversal fluctuation andmacroscopic non-uniqueness.

Keywords

Longest common subsequencepath propertylongitudinal fluctuationtransversed fluctuation.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Aldous, D. and Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 (1999) 413–432. CrossRef
Alexander, K.S., The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab. 4 (1994) 1074–1082.
Arratia, R. and Waterman, M.S., A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Probab. 4 (1994) 200–225.
Baik, J., Deift, P. and Johansson, K., On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 (1999) 1119–1178. CrossRef
Chvatal, V. and Sankoff, D., Longest common subsequences of two random sequences. J. Appl. Probability 12 (1975) 306–315. CrossRef
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.
Howard, C.D. and Newman, C.M., Geodesics and spanning trees for euclidian first-passage percolation. Ann. Probab. 29 (2001) 577–623.
Johansson, K., Transversal fluctuations for increasing subsequences on the plane. Probab. Theory Related Fields 116 (2000) 445–456. CrossRef
J. Lember and H. Matzinger, Variance of the LCS for 0 and 1 with different frequencies. Submitted (2006).
Newman, C.M. and Piza, M.S.T., Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 (1995) 977–1005. CrossRef
P.A. Pevzner, Computational molecular biology. An algorithmic approach. Bradford Books, MIT Press, Cambridge, MA (2000).
Steele, M.J., Efron-Stein, An inequality for non-symmetric statistics. Annals of Statistics 14 (1986) 753–758. CrossRef
Waterman, M.S., Estimating statistical significance of sequence alignments. Phil. Trans. R. Soc. Lond. B 344 (1994) 383–390.