Microscopic path structure of optimally aligned random sequences (Q2278651)

This paper studies the microscopic path structure of optimally aligned random sequences, for an alignment \(\pi\) with gaps of two sequences \(x=x_1,\cdots,x_n\) and \(y=y_1,\cdots,y_n\) of equal length \(n\). The vector \(p_{\pi}(x,y)\) of all such ratios collected in lexicographical order is the empirical distribution vector of \(\pi\). Let \(SET(x,y)=\{p_{\pi}(x,y)\}_{\pi}\) be the set of all empirical distribution vectors related to \(x\) and \(y\). For two independent random sequences \(X=X_1,\ldots, X_n\) and \(Y=Y_1,\ldots,Y_n\) with i.i.d. components. The convex hull of \(SET(X,Y)\) is given by \(SET^n=\mathrm{conv}(SET(X,Y))\). Given a scoring function \(S\), let \(f_S\) be some associated linear functional. It is shown that \(SET^n\) almost surely converges to the set \(SET\) in the topology of the Hausdorff distance as \(n\) tends to infinity. Moreover, the empirical distribution of all optimal alignments of \(X\) and \(Y\) almost surely converge to a deterministic distribution when the scoring function \(S\) is selected such that \(f_S\) has a unique maximizer in \(SET\). For Lebesgue-almost every scoring function \(S\), it is proved that the empirical distributions of all optimal alignments almost surely converge to some deterministic distribution.