Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

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.

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 × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/60772

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Qingqing. Topics on the longest common subsequences: Simulations, computations, and variance. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/60772