A Monte Carlo approach to the fluctuation problem in optimal alignments of random strings

zbMATH Open1308.60105arXiv1211.5489MaRDI QIDQ5168340FDOQ5168340

Authors: Saba Amsalu, Raphael A. Hauser, Heinrich Matzinger 

Publication date: 3 July 2014

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 that the biased expected effect of a random letter-change on the optimal score implies an order of fluctuation linear in $sqrtn$. 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 $sqrtn$ 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. 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. For this DNA-setting, we show that with a high level of confidence, the fluctuation of the optimal alignment score is of order $Theta(sqrtn)$. An important special case of optimal alignment score is the Longest Common Subsequence (LCS) of random strings. For binary sequences with equiprobable 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. Thus, for many real life situations, our method allows to determine the order of the fluctuation up to a high confidence level.

Full work available at URL: https://arxiv.org/abs/1211.5489

Recommendations

• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison
• Lower bounds on the generalized central moments of the optimal alignments score of random sequences
• Letter change bias and local uniqueness in optimal sequence alignments
• Order of the fluctuation for the LCS and optimal alignment score of binary sequences when the rescaled expectation is not constant
• Statistics of optimal sequence alignments.

zbMATH Keywords

first passage percolationfluctuationlast passage percolationoptimal alignmentsrandom stringsMonte Carlo approachbiased effect

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Rate of convergence, degree of approximation (41A25)

Cited In (5)

• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
• Letter change bias and local uniqueness in optimal sequence alignments
• Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets
• Microscopic path structure of optimally aligned random sequences
• Proportion of Gaps and Fluctuations of the Optimal Score in Random Sequence Comparison

This page was built for publication: A Monte Carlo approach to the fluctuation problem in optimal alignments of random strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168340)