Related problems of string indexing and sequence analysis have been widely studied for a long time. Recently, researchers turn to consider extended versions of these problems, which provides more realistic applications. In this dissertation, we focus on three problems of recent interest, which are (1)the
indexing problem for scaled strings, (2)the merged longest common subsequence problem and its variant with blocks, and (3)the sequence alignment
problem with weighted constraints.
The indexing problem for scaled strings asks one to preprocess a text string T, so that the matched positions of a pattern string P in T, with some
scales £\ applied to P, can be reported efficiently. In this dissertation, we propose efficient algorithms for indexing real scaled strings, discretely scaled
strings, and proportionally scaled strings. Our indexing algorithms achieve either significant improvements to previous results, or the best known results. The merged longest common subsequence (merged LCS) problem aims to detect the interleaving relationship between sequences, which has important applications to genomic and signal comparison. In this dissertation, we propose improved algorithms for finding the merged LCS. Our
algorithms for finding the merged LCS are also more efficient than the previous results, especially for large alphabets. Finally, the sequence alignment problem with weighted constraints is a newly proposed problem in this dissertation. For this new problem, we first propose an efficient solution, and then show that the concept of weighted constraints can be further used to solve many constraint-related problems on sequences. Therefore, our results in this dissertation have significant contributions to the field of string indexing and sequence analysis.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0720110-150614 |
| Date | 20 July 2010 |
| Creators | Peng, Yung-Hsing |
| Contributors | Yaw-Ling Lin, Chang-Biau Yang, Rong-Jaye Chen, Yue-Li Wang, Biing-Feng Wang, Tzung-Pei Hong, Sun-Yuan Hsieh, Maw-Shang Chang |
| 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-0720110-150614 |
| Rights | off_campus_withheld, Copyright information available at source archive |
Page generated in 0.0175 seconds