Return to search

An Approach for Solving the Constrained Longest Common Subsequence Problem

A subsequence is obtained by deleting zero or more symbols from a given sequence. For given two sequences, the longest common subsequence problem is to find a common subsequence whose length is the longest. The constrained longest common subsequence (CLCS) problem is to find a longest common subsequence that contains a specific subsequence. Note a CLCS may be shorter than an LCS.
In this thesis, we propose a dynamic programming algorithm for solving the CLCS problem. The time complexity is O(pmn), where m and n are the lengths of the given sequences and p is the length of the constraint sequence. Our algorithm
can also be applied to solve the constrained sequence alignment problem, which is a sequence alignment problem with the requirement that some specific symbols must be aligned together.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0828103-125439
Date28 August 2003
CreatorsPeng, Chao-Li
ContributorsD. J. Guan, Chang-Biau Yang, Bang-Ye Wu, none, none
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0828103-125439
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.0021 seconds