Georgia Institute of Technology
Topics on the longest common subsequences: Simulations, computations, and variance
Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Mathematics
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Liu, Qingqing
- Advisors dc:contributor.advisor
-
- Houdré, Christian
- Houdré, Christian
- Committee members dc:contributor.committeemember
-
- Damron, Michael
- Koltchinskii, Vladimir
- Mei, Yajun
- Zhilova, Mayya
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/60772