Topics on the longest common subsequences: Simulations, computations, and variance

Longest common subsequences;Monte-Carlo simulations;Variance;Lower bound

Liu, Qingqing ; Houdré, Christian Mathematics Damron, Michael Koltchinskii, Vladimir Mei, Yajun Zhilova, Mayya ; Houdré, Christian

University:Georgia Institute of Technology

Department:Mathematics

关键词: Longest common subsequences;    Monte-Carlo simulations;    Variance;    Lower bound;   

Others  :  https://smartech.gatech.edu/bitstream/1853/60772/1/LIU-DISSERTATION-2018.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The study of the longest common subsequences (LCSs) of two random words/strings is classical in computer science and bioinformatics. A problem of particular probabilistic interest is to determine the limiting behavior of the expectation and variance of the length of the LCSs, as the length of the random words grows without bound. This dissertation studies this problem using both Monte-Carlo simulation and theoretical analysis. The specific questions studied here include estimating the growth order of the variance, LCSs based hypothesis testing methods for sequences similarity, theoretical upper bounds on the Chvátal-Sankoff constant of multiple sequences, and theoretical growth order of the variance when the two random words have asymmetrical distributions.