A Monte Carlo Approach to the Fluctuation Problem in Optimal Alignments of Random Strings

S. Amsalu, R. Hauser, H. Matzinger

2014, v.20, Issue 1, 107-144

ABSTRACT

The problem of determining the correct order of fluctuation of the optimal alignment score of two random strings of length $n$ has been open for several decades. It is known [J. Lember and H. Matzinger, Standard deviation of the longest common subsequence. Ann. Prob., 2009, v.37, N3, 1192-1235] that the biased expected effect of a random letter-change on the optimal score implies an order of fluctuation linear in $\sqrt{n}$. However, in many situations where such a biased effect is observed empirically, it has been impossible to prove analytically. The main result of this paper shows that when the rescaled-limit of the optimal alignment score increases in a certain direction, then the biased effect exists. On the basis of this result one can quantify a confidence level for the existence of such a biased effect and hence of an order $\sqrt{n}$ fluctuation based on simulation of optimal alignments scores. This is an important step forward, as the correct order of fluctuation was previously known only for certain special distributions [J. Lember and H. Matzinger, Standard deviation of the longest common subsequence. Ann. Prob., 2009, v.37, N3, 1192-1235; J. Lembe, H. Matzinger and C. Duringer, Deviation from the mean in sequence comparison with a periodic sequence. ALEA, 2007, v.3, 1-29; F. Bonetto and H. Matzinger, Fluctuations of the longest common subsequence in the case of 2- and 3-letter alphabets. Latin Amer. J. Prob. Math., 2006, v.2, 195-216; C. Houdre, J. Lember and H. Matzinger, On the longest common increasing binary subsequence. C. R. Acad. Sci. Paris, Ser. I, 2006, v. 343, 589-594]. To illustrate the usefulness of our new methodology, we apply it to optimal alignments of strings written in the DNA-alphabet. As scoring function, we use the BLASTZ default-substitution matrix together with a realistic gap penalty. BLASTZ is one of the most widely used sequence alignment methodologies in bioinformatics. (In bioinformatics, the Basic Local Alignment Search Tool (BLAST), and variants there-off such as BLASTZ, are algorithms developed for detecting similarities between genetic sequences. The BLAST program was designed by Altschul, Gish, Miller, Myers, and Lipman at the NIH and was published in 1990, [S.F. Altschul, W. Gish, W. Miller, E.W. Myers and D.J. Lipman, Basic local alignment search tool. J. Molec. Biol., 1990, v.215, 403-410; R.M. Casey, Blast sequences aid in genomics and proteomics. Business Intelligence Network, 2005, http://www.b-eye-network.com/view/1730]. It is based on the Karlin - Altschul statistics [S. Karlin and S.F. Altschul, Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proc. Nat. Acad. Sci. USA, 1990, v.87, 2264-2268]). For this DNA-setting, we show that with a high level of confidence, the fluctuation of the optimal alignment score is of order $\theta(\sqrt{n})$. An important special case of optimal alignment score is the Longest Common Subsequence (LCS) of random strings. For binary sequences with equiprobably symbols the question of the fluctuation of the LCS remains open. The symmetry in that case does not allow for our method. On the other hand, in real-life DNA sequences, it is not the case that all letters occur with the same frequency. So, for many real life situations, our method allows to determine the order of the fluctuation up to a high confidence level.

Keywords: longest commons subsequence,random strings,optimalalignments,last passage percolation,first passage percolation

COMMENTS

Please log in or register to leave a comment