Optimality regions and fluctuations for Bernoulli last passage models

DOI10.1007/S11040-018-9276-2zbMATH Open1394.60100arXiv1610.03103OpenAlexW2963472602WikidataQ129430584 ScholiaQ129430584MaRDI QIDQ1664580FDOQ1664580

Nicos Georgiou, Janosch Ortmann

Publication date: 27 August 2018

Published in: Mathematical Physics, Analysis and Geometry (Search for Journal in Brave)

Abstract: We study the sequence alignment problem and its independent version, the discrete Hammersley process with an exploration penalty. We obtain rigorous upper bounds for the number of optimality regions in both models near the soft edge. At zero penalty the independent model becomes an exactly solvable model and we identify cases for which the law of the last passage time converges to a Tracy-Widom law.

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

zbMATH Keywords

longest common subsequencesequence alignmentTracy-Widom distributionlast passage timesoft edgeBernoulli increasing pathscorner growth modelsdiscrete Hammersley processedge resultsflat edgeoptimality regions

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An approximation of partial sums of independent RV's, and the sample DF. II
• Algebraic Statistics for Computational Biology
• Level-spacing distributions and the Airy kernel
• Brownian analogues of Burke's theorem.
• Closeness to the diagonal for longest common subsequences in random words
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• Parametric inference for biological sequence analysis
• Expected length of the longest common subsequence for large alphabets
• GUEs and queues
• The Complexity of Some Problems on Subsequences and Supersequences
• Departures from many queues in series
• Stationary cocycles and Busemann functions for the corner growth model
• Standard deviation of the longest common subsequence
• Longest common subsequences of two random sequences
• A universality property for last-passage percolation paths close to the axis
• Optimal alignments of longest common subsequences and their path properties
• Limiting shape for directed percolation models
• A scaling limit for queues in series
• Variational formulas and cocycle solutions for directed polymer and percolation models
• Geodesics and the competition interface for the corner growth model
• Parametric optimization of sequence alignment
• Parametric analysis of RNA branching configurations
• Parametric analysis of alignment and phylogenetic uncertainty
• Lower bounds for optimal alignments of binary sequences
• Increasing sequences of independent points on the planar lattice
• Soft edge results for longest increasing paths on the planar lattice
• Thermodynamical approach to the longest common subsequence problem
• Bounds for parametric sequence comparison
• Discrete Hammersley's lines with sources and sinks
• Bioinformatics and the Cell

Cited In (4)

• On the Geometry of the Last Passage Percolation Problem
• From stability to chaos in last‐passage percolation
• Order of the variance in the discrete Hammersley process with boundaries
• Longest increasing paths with gaps

This page was built for publication: Optimality regions and fluctuations for Bernoulli last passage models

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