ESAIM: P&S, June 2007, Vol. 11, pp. 281-300
DOI: 10.1051/ps:2007014

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

Saba Amsalu¹, Heinrich Matzinger² and Serguei Popov<sup>3

1</sup>  University of Bielefeld, Postfach 10 01 31, 33501 Bielefeld, Germany; saba@uni-bielefeld.de
²  School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA; matzi@math.gatech.edu
³  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

(Received November 25, 2005. Revised June 22, 2006. Published online 19 June 2007.)

Abstract
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