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.
Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0828103-125439 |
Date | 28 August 2003 |
Creators | Peng, Chao-Li |
Contributors | D. J. Guan, Chang-Biau Yang, Bang-Ye Wu, none, none |
Publisher | NSYSU |
Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
Language | English |
Detected Language | English |
Type | text |
Format | application/pdf |
Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0828103-125439 |
Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.002 seconds