Back to search

West Virginia University

The Longest Common Subsequence via Generalized Suffix Trees

Abstract

dc:description.abstract

Given two strings S1 and S 2, finding the longest common subsequence (LCS) is a classical problem in computer science. Many algorithms have been proposed to find the longest common subsequence between two strings. The most common and widely used method is the dynamic programming approach, which runs in quadratic time and takes quadratic space. Other algorithms have been introduced later to solve the LCS problem in less time and space. In this work, we present a new algorithm to find the longest common subsequence using the generalized suffix tree and directed acyclic graph.;The Generalized suffix tree (GST) is the combined suffix tree for a set of strings {lcub}S1, S 2, ..., Sn{rcub}. Both the suffix tree and the generalized suffix tree can be calculated in linear time and linear space. One application for generalized suffix tree is to find the longest common substring between two strings. But finding the longest common subsequence is not straight forward using the generalized suffix tree. Here we describe how we can use the GST to find the common substrings between two strings and introduce a new approach to calculate the longest common subsequence (LCS) from the common substrings. This method takes a different view at the LCS problem, shading more light at novel applications of the LCS. We also show how this method can motivate the development of new compression techniques for genome resequencing data.

Degree

thesis:*
Name thesis:degree_name
MS
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Afrin, Tazin
Contributors dc:contributor
  • Donald Adjeroh
  • Elaine M Eschen
  • Katerina-Goseva Popstojanova

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Afrin, Tazin. The Longest Common Subsequence via Generalized Suffix Trees. Thesis thesis, https://doi.org/10.33915/etd.5031