Optimality Regions and Fluctuations for Bernoulli Last Passage Models

被引：0
作者：
Nicos Georgiou
Janosch Ortmann
机构：
[1] University of Sussex,Mathematics Department
[2] Université du Québec à Montréal,Département de management et Technologie
来源：
Mathematical Physics, Analysis and Geometry | 2018年 / 21卷
关键词：
Soft edge; Edge results; Optimality regions; Sequence alignment; Discrete Hammersley process; Longest common subsequence; Bernoulli increasing paths; Tracy-Widom distribution; Last passage time; Corner growth models; Flat edge; 60K35;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
相关论文
共 79 条
[1]  
Amsalu S(2008)Thermodynamical approach to the longest common subsequence problem J. Stat. Phys. 131 1103-1120
[2]  
Matzinger H(2001)GUEs queues Prob. Theory Relat. Fields 119 256-274
[3]  
Vachkovskaia M(2016)Discrete Hammersley’s lines with sources and sinks. ALEA Lat Am. J. Probab. Math. Stat 13 33-52
[4]  
Baryshnikov Y(2000)A survey of longest common subsequence algorithms SPIRE 00 39-48
[5]  
Basdevant A-L(2005)A universality property for last-passage percolation close to the axis Electron. Commun. Probab. 10 105-112
[6]  
Enriquez N(1975)Longest common subsequences of two random sequences J. Appl. Probab. 12 306-315
[7]  
Gerin L(1938)Sur un nouveau théorème limite de la probabilité Actualités Sci. Industr 736 5-23
[8]  
Gouéré J-B(2006)Parametric alignment of drosophila genomes PLoS Comput. Biol. 2 e73-198
[9]  
Bergroth L(2002)Bounds for parametric sequence comparison Discrete Appl. Math 118 181-13
[10]  
Hakonen H(2010)Soft edge results for longest increasing paths on the planar lattice Electron. J. Probab. 15 1-779
12345678