Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
University of Bielefeld, Postfach 10 01 31,
33501 Bielefeld, Germany; email@example.com
2 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332–0160, USA; firstname.lastname@example.org
3 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; email@example.com
Revised: 22 June 2006
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.
Mathematics Subject Classification: 60K35 / 60J20
Key words: Longest common subsequence / path property / longitudinal fluctuation / transversed fluctuation.
© EDP Sciences, SMAI, 2007