Exact solution of the Bernoulli matching model of sequence alignment

Abstract

Through a series of exact mappings we reinterpret the Bernoulli model of sequence alignment in terms of the discrete-time totally asymmetric exclusion process with backward sequential update and step function initial condition. Using earlier results from the Bethe ansatz we obtain analytically the exact distribution of the length of the longest common subsequence of two sequences of finite lengths $X,Y$. Asymptotic analysis adapted from random matrix theory allows us to derive the thermodynamic limit directly from the finite-size result.

13 pages, 4 figures

References in corpus (11)

• Level-Spacing Distributions and the Airy Kernel
• Shape Fluctuations and Random Matrices
• On Orthogonal and Symplectic Matrix Ensembles
• Exact Solution of the Master Equation for the Asymmetric Exclusion Process
• Current Distribution and random matrix ensembles for an integrable asymmetric fragmentation process
• Exact Asymptotic Results for a Model of Sequence Alignment
• Asymmetric Simple Exclusion Process and Modified Random Matrix Ensembles
• The asymmetric exclusion model with sequential update
• Extensive Simulations for Longest Common Subsequences: Finite Size Scaling, a Cavity Solution, and Configuration Space properties
• An Exactly Solvable Anisotropic Directed Percolation Model in Three Dimensions
• Mean-Field Approximations to the Longest Common Subsequence Problem

Cited by in corpus (5)

• Non-equilibrium statistical mechanics: From a paradigmatic model to biological transport
• Some Exact Results for the Exclusion Process
• Determinant representation for some transition probabilities in the TASEP with second class particles
• From stability to chaos in last-passage percolation
• A novel Recurrence-Transience transition and Tracy-Widom growth in a cellular automaton with quenched noise