Sampling rare events: statistics of local sequence alignments.

A method to calculate probability distributions in regions where the events are very unlikely (e.g., p approximately 10(-40)) is presented. The basic idea is to map the underlying model on a physical system. The system is simulated at a low temperature, such that preferably configurations with originally low probabilities are generated. Since the distribution of such a physical system is known, the original unbiased distribution can be obtained. As an application, local alignment of protein sequences is studied. The deviation of the distribution p(S) of optimum scores from the extreme-value distribution is quantified. This deviation decreases with growing sequence length.

• Publication year

  2001

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2001-08-13

• Fields of study

  Biology, Physics, Computer Science, Mathematics, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.65.056102arXiv cond-mat/0108201PMID 12059642
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Phase Transitions and Critical Phenomena

  2021cited by this paper
• The estimation of statistical parameters for local alignment score distributions.

  2001cited by this paper
• Initial sequencing and analysis of the human genome

  2001cited by this paper
• Transport on an annealed disordered lattice.

  1999cited by this paper
• Geometric Sums: Bounds for Rare Events with Applications: Risk Analysis, Reliability, Queueing

  1997cited by this paper
• Local alignment statistics.

  1996cited by this paper
• Rapid and accurate estimates of statistical significance for sequence data base searches.

  1994cited by this paper
• Maximum-likelihood estimation of the statistical distribution of Smith-Waterman local sequence similarity scores

  1992cited by this paper
• Amino acid substitution matrices from protein blocks.

  1992cited by this paper
• Multicanonical ensemble: A new approach to simulate first-order phase transitions.

  1992cited by this paper
• Distribution of glutamine and asparagine residues and their near neighbors in peptides and proteins.

  1991cited by this paper
• Dynamics of ordering processes in annealed dilute systems: Island formation, vacancies at domain boundaries, and compactification.

  1990cited by this paper
• The statistical distribution of nucleic acid similarities.

  1985cited by this paper
• C. W. Horton, Jr. and L. E. Reichl 編: Statistical Physics and Chaos in Fusion Plasmas, John Wiley & Sons, New York, 1984, 362ページ, 24×17cm, 25,500円.

  1985cited by this paper
• Optimization by Simulated Annealing

  1983cited by this paper
• An improved algorithm for matching biological sequences.

  1982cited by this paper
• Identification of common molecular subsequences.

  1981cited by this paper
• A modern course in statistical physics

  1980cited by this paper
• A general method applicable to the search for similarities in the amino acid sequence of two proteins.

  1970cited by this paper
• Methods in Enzymology

  1968cited by this paper

• The distribution of the moment of inertia for harmonically trapped noninteracting Bosons at finite temperature: large deviations

  2025cites this paper
• Distribution of the Number of Paths in Two-Dimensional Directed Percolation

  2025influential citation
• Confined run-and-tumble particles with non-Markovian tumbling statistics.

  2024cites this paper
• In and beyond the Griffiths phase: A large-deviation study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model.

  2024influential citation
• Numerical aspects of large deviations

  2024cites this paper
• Importance sampling for counting statistics in one-dimensional systems.

  2024cites this paper
• Designing a Data Science simulation with MERITS: A Primer

  2024cites this paper
• First-passage area distribution and optimal fluctuations of fractional Brownian motion.

  2023cites this paper
• Probing the large deviations for the beta random walk in random medium.

  2023cites this paper
• Current fluctuations in stochastically resetting particle systems.

  2023cites this paper
• Optimal finite-differences discretization for the diffusion equation from the perspective of large-deviation theory

  2023cites this paper
• Occupation time of a system of Brownian particles on the line with steplike initial condition.

  2023cites this paper
• Local time of a system of Brownian particles on the line with steplike initial condition.

  2023cites this paper
• Large deviations in chaotic systems: Exact results and dynamical phase transition.

  2022cites this paper
• Anomalous scaling and first-order dynamical phase transition in large deviations of the Ornstein-Uhlenbeck process.

  2021cites this paper
• Rare-event properties in a classical stochastic model describing the evolution of random unitary circuits.

  2021cites this paper
• New Approximate Statistical Significance of Gapped Alignments Based on the Greedy Extension Model

  2020cites this paper
• Similarity of extremely rare nonequilibrium processes to equilibrium processes.

  2020cites this paper
• Number of longest increasing subsequences.

  2020cites this paper
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks.

  2019cites this paper
• Beyond the typical fluctuations : a journey to the large deviations in the Kardar-Parisi-Zhang growth model

  2019cites this paper
• Large-deviations of the basin stability of power grids.

  2019cites this paper
• Probing large deviations of the Kardar-Parisi-Zhang equation at short times with an importance sampling of directed polymers in random media.

  2019cites this paper
• Rare-event properties of the Nagel-Schreckenberg model.

  2019cites this paper
• Optimal paths of nonequilibrium stochastic fields: The Kardar-Parisi-Zhang interface as a test case

  2019cites this paper
• Large Deviations of Convex Hulls of the “True” Self-Avoiding Random Walk

  2018cites this paper
• Large deviations of convex hulls of self-avoiding random walks.

  2018cites this paper
• Distribution of shortest path lengths in subcritical Erdős-Rényi networks.

  2018cites this paper
• Large-Deviation Properties of Sequence Alignment of Correlated Sequences

  2018cites this paper
• Large-deviation properties of the largest biconnected component for random graphs

  2018cites this paper
• Estimating statistical significance of local protein profile-profile alignments

  2018cites this paper
• Large-deviation properties of the extended Moran model

  2017cites this paper
• Computing return times or return periods with rare event algorithms

  2017cites this paper
• Large-deviation properties of the largest 2-core component for random graphs

  2017cites this paper
• Distribution of diameters for Erdős-Rényi random graphs.

  2017cites this paper
• The Evolution of Third Molar Agenesis and Impaction

  2016cites this paper
• Test of quantum thermalization in the two-dimensional transverse-field Ising model

  2016cites this paper
• (Non-)Thermalization in the 2D transverse field Ising model after quantum quenches

  2016influential citation
• Score distributions of gapped multiple sequence alignments down to the low-probability tail.

  2015cites this paper
• Large-deviation properties of resilience of power grids

  2014cites this paper
• Modeling professional similarity by mining professional career trajectories

  2014cites this paper
• Large-deviation properties of resilience of transportation networks

  2014cites this paper
• Pharmacophore Alignment Search Tool (PhAST): Significance Assessment of Chemical Similarity

  2013cites this paper
• Sampling fractional Brownian motion in presence of absorption: a Markov chain method.

  2013cites this paper
• Typical and large-deviation properties of minimum-energy paths on disordered hierarchical lattices

  2013cites this paper
• Multicanonical MCMC for sampling rare events: an illustrative review

  2013cites this paper
• Significance estimation for sequence-based chemical similarity searching (PhAST) and application to AuroraA kinase inhibitors.

  2012cites this paper
• New finite-size correction for local alignment score distributions

  2012cites this paper
• Text-based similarity searching for hit- and lead-candidate identification

  2012cites this paper
• Objective method for estimating asymptotic parameters, with an application to sequence alignment.

  2011cites this paper
• Accurate statistics for local sequence alignment with position-dependent scoring by rare-event sampling

  2011cites this paper
• Sequence-specific sequence comparison using pairwise statistical significance.

  2011cites this paper
• Pairwise Statistical Significance of Local Sequence Alignment Using Sequence-Specific and Position-Specific Substitution Matrices

  2011cites this paper
• Large-deviation properties of largest component for random graphs

  2010cites this paper
• Pharmacophore alignment search tool: Influence of canonical atom labeling on similarity searching

  2010cites this paper
• Sequence Alignment Statistics

  2010cites this paper
• Finite-temperature local protein sequence alignment: percolation and free-energy distribution.

  2009cites this paper
• Sequence-specific seque nce comparison using pairwise statistical signific ance

  2009cites this paper
• Computational Techniques for Haplotype Inference and for Local Alignment Significance

  2009cites this paper
• Pairwise statistical significance of local sequence alignment using multiple parameter sets and empirical justification of parameter set change penalty

  2008cites this paper
• Significance of Gapped Sequence Alignments

  2008cites this paper
• Minimum-free-energy distribution of RNA secondary structures: Entropic and thermodynamic properties of rare events.

  2008cites this paper
• Pairwise Statistical Significance of Local Sequence Alignment Using Substitution Matrices with Sequence-Pair-Specific Distance

  2008cites this paper
• Pairwise statistical significance and empirical determination of effective gap opening penalties for protein local sequence alignment

  2008cites this paper
• A Monte Carlo algorithm for sampling rare events: application to a search for the Griffiths singularity

  2007cites this paper
• Testing Error Correcting Codes by Multicanonical Sampling of Rare Events(Cross-disciplinary physics and related areas of science and technology)

  2007cites this paper
• Computational Methods for Locating and Analyzing Conserved Gene Regulatory DNA Elements

  2007cites this paper
• The distribution of Lee–Yang zeros and Griffiths singularities in the ±J model of spin glasses

  2007cites this paper
• 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.

  2006cites this paper
• Ground-state and domain-wall energies in the spin-glass region of the two-dimensional ±J random-bond ising model

  2006cites this paper
• Probing tails of energy distributions using importance-sampling in the disorder with a guiding function

  2006influential citation
• Universality-class dependence of energy distributions in spin glasses

  2005cites this paper
• Score statistics of global sequence alignment from the energy distribution of a modified directed polymer and directed percolation problem.

  2005cites this paper
• On Large Deviation Properties of Erdös–Rényi Random Graphs

  2003cites this paper
• for Molecular Biology

  year unknowncites this paper