Similarity-Detection and Localization

Abstract

The detection of similarities between long DNA and protein sequences is studied using concepts of statistical physics. It is shown that mutual similarities can be detected by sequence alignment methods only if their amount exceeds a threshold value. The onset of detection is a continuous phase transition which can be viewed as a localization-delocalization transition. The ``fidelity'' of the alignment is the order parameter of that transition; it leads to criteria for the selection of optimal alignment parameters.

4 pages including 4 figures (308kb post-script file)

References in corpus (2)

• Disorder-Induced Depinning Transition
• Depinning in a Random Medium

Cited by in corpus (32)

• Free-energy distribution of the directed polymer at high temperature
• An exact solution for the KPZ equation with flat initial conditions
• Directed polymer near a hard wall and KPZ equation in the half-space
• Extremes of N vicious walkers for large N: application to the directed polymer and KPZ interfaces
• RNA secondary structure formation: a solvable model of heteropolymer folding
• Non-parametric Determination of Real-Time Lag Structure between Two Time Series: the "Optimal Thermal Causal Path" Method
• Exact Asymptotic Results for a Model of Sequence Alignment
• Static and Dynamic Properties of Inhomogeneous Elastic Media on Disordered Substrate
• Directed random polymers via nested contour integrals
• Nature of the glassy phase of RNA secondary structure
• On Growth, Disorder, and Field Theory
• On integrable directed polymer models on the square lattice
• Probability Distributions of Line Lattices in Random Media from the 1D Bose Gas
• Polymer Reptation in Disordered Media
• The crossing probability for directed polymers in random media
• Mean-Field Approximations to the Longest Common Subsequence Problem
• A New Simulated Annealing Algorithm for the Multiple Sequence Alignment Problem: The approach of Polymers in a Random Media
• Bethe Ansatz in the Bernoulli Matching Model of Random Sequence Alignment
• Crossing probability for directed polymers in random media: exact tail of the distribution
• Non-Linear Stochastic Equations with Calculable Steady States
• Directed Polymers on a Factorized Disorder Landscape
• Mutually avoiding paths in random media and largests eigenvalues of random matrices
• Unzipping of two random heteropolymers: Ground state energy and finite size effects
• Surprises in approximating Levenshtein distances
• Kurtosis of height fluctuations in $(1+1)$ dimensional KPZ Dynamics
• Significance analysis and statistical mechanics: an application to clustering
• Hyperskewness of $(1+1)$-dimensional KPZ Height Fluctuations
• Scaling Laws and Similarity Detection in Sequence Alignment with Gaps
• Probabilistic sequence alignments: realistic models with efficient algorithms
• Steady-state skewness and kurtosis from renormalized cumulants in $(2+1)$-dimensional stochastic surface growth
• Optimal Detection of Sequence Similarity by Local Alignment
• Optimizing Smith-Waterman alignments