Topics on the longest common subsequences: Simulations, computations, and Variance
- Series
- Dissertation Defense
- Time
- Friday, June 22, 2018 - 13:30 for 2 hours
- Location
- Skiles 005
- Speaker
- Qingqing Liu – Georgia Tech
The study of the longest common subsequences (LCSs) of two random words is a classical problem 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 LCS as the length of the random words grows without bounds. This dissertation studies the problem using both Monte-Carlo simulation and theoretical analysis. The specific problems studied include estimating the growth order of the variance, LCS based hypothesis testing method for sequences similarity, theoretical upper bounds for the Chv\'atal-Sankoff constant of multiple sequences, and theoretical growth order of the variance when the two random words have asymmetric distributions.