Sampling rare events: statistics of local sequence alignments

Abstract

A new method to simulate probability distributions in regions where the events are VERY unlikely (e.g. p ~ 10^{-40}) is presented. The basic idea is to represent the underlying probability space by the phase space of a physical system. The system is held at a temperature T, which is chosen such that the system preferably generates configurations which originally have low probabilities. Since the distribution of such a physical system is know from statistical physics, the original unbiased distribution can be obtained. As an application, local alignment of protein sequences based on BLOSUM62 substitution scores with (12,1) affine gap costs are considered The distribution of optimum sequence-alignment scores S is studied numerically over a large range of scores. The deviation of p(S) from the extreme-value (or Gumbel) distribution is quantified. This deviation decreases with growing sequence length.

5 pages, 4 figures, revtex

Cited by in corpus (55)

• Large-deviation properties of largest component for random graphs
• Long time position distribution of an active Brownian particle in two dimensions
• On large deviation properties of Erdos-Renyi random graphs
• High-precision simulation of the height distribution for the KPZ equation
• Partition function of two- and three-dimensional Potts ferromagnets for arbitrary values of q>0
• Large-deviation properties of the largest biconnected component for random graphs
• Computing return times or return periods with rare event algorithms
• Distribution of diameters for Erdös-Rényi random graphs
• Universality-class dependence of energy distributions in spin glasses
• Convex Hulls of Random Walks: Large-Deviation Properties
• Test of quantum thermalization in the two-dimensional transverse-field Ising model
• Anomalous scaling and first-order dynamical phase transition in large deviations of the Ornstein-Uhlenbeck process
• Critical behavior of the Anderson model on the Bethe lattice via a large-deviation approach
• Probing the tails of the ground state energy distribution for the directed polymer in a random medium of dimension $d=1,2,3$ via a Monte-Carlo procedure in the disorder
• Large-deviation properties of resilience of power grids
• Multicanonical sampling of rare events in random matrices
• Probing tails of energy distributions using importance-sampling in the disorder with a guiding function
• Optimal paths of non-equilibrium stochastic fields: the Kardar-Parisi-Zhang interface as a test case
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Multicanonical MCMC for Sampling Rare Events
• Ground state energy of noninteracting fermions with a random energy spectrum
• Large deviations in chaotic systems: exact results and dynamical phase transition
• Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media
• Large-deviation properties of resilience of transportation networks
• Sampling fractional Brownian motion in presence of absorption: a Markov Chain method
• Observing symmetry-broken optimal paths of stationary Kardar-Parisi-Zhang interface via a large-deviation sampling of directed polymers in random media
• Current fluctuations in stochastically resetting particle systems
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Rare-Event Properties of the Nagel-Schreckenberg Model
• Distribution of Lee-Yang zeros and Griffiths singularities in the $\pm J$ model of spin glasses
• Testing Error Correcting Codes by Multicanonical Sampling of Rare Events
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Local time of a system of Brownian particles on the line with steplike initial condition
• Typical and large-deviation properties of minimum-energy paths on disordered hierarchical lattices
• Extremely rare ultra-fast non-equilibrium processes can be close to equilibrium: RNA unfolding and refolding
• Occupation time of a system of Brownian particles on the line with steplike initial condition
• Confined run and tumble particles with non-Markovian tumbling statistics
• A Monte Carlo Algorithm for Sampling Rare Events: Application to a Search for the Griffiths Singularity
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Finite-temperature local protein sequence alignment: percolation and free-energy distribution
• How many longest increasing subsequences are there?
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• Large-deviations of the SIR model around the epidemic threshold
• Ground-State and Domain-Wall Energies in the Spin-Glass Region of the 2D $\pm J$ Random-Bond Ising Model
• The Griffiths phase and beyond: A large deviations study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model
• First-passage properties of the jump process with a drift. Two exactly solvable cases
• Score distributions of gapped multiple sequence alignments down to the low-probability tail
• Importance Sampling for counting statistics in one-dimensional systems
• Numerical Aspects of Large Deviations
• Large-deviation properties of the extended Moran model
• Optimal finite-differences discretization for the diffusion equation from the perspective of large-deviation theory
• Large deviations of a random walk model with emerging territories
• Rare-event properties in a classical stochastic model describing the evolution of random unitary circuits
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs