Title page for etd-0806116-215529


[Back to Results | New Search]

URN etd-0806116-215529
Author Shian-liang Lin
Author's Email Address No Public.
Statistics This thesis had been viewed 5351 times. Download 391 times.
Department Computer Science and Engineering
Year 2016
Semester 1
Degree Master
Type of Document
Language English
Title A Survey on the Algorithms of the Edit Distance Problem and Related Variants
Date of Defense 2016-09-06
Page Count 174
Keyword
  • Genome Rearrangement
  • Similarity
  • Dynamic Programing
  • Longest Common Subsequence
  • Edit Distance
  • Block Edit
  • Abstract Abstract
    The edit distance problem has been studied for several decades. Given sequences
    (strings) A and B with length m and n, respectively, m ≤ n, the edit distance
    problem is to find the minimum cost of operations required to transform A to B.
    According to different models of cost functions, operations and input sequences, the
    problem has several variants. The edit distance on run-length encoding sequences and
    cyclic sequences are the variants on the input aspect. The block edit problem is a
    variant on the operation aspect. The edit distance considering consecutive insertions
    and deletions is another variant on the cost function. Besides, the genome
    rearrangement problem can also be viewed as a variant, whose operations include
    inversions, reversals and transpositions. In this thesis, we survey some algorithms for
    the edit distance problem, its variants and the genome rearrangement problem. We
    also perform some experiments to illustrate the execution efficiency of various
    algorithms.
    Keywords: Edit Distance, Block Edit, Genome Rearrangement, Longest Common
    Subsequence, Dynamic Programing, Similarity
    Advisory Committee
  • Kuo-Si Huang - chair
  • Hsing-Yen Ann - co-chair
  • Yung-Hsing Peng - co-chair
  • Kuo-Tsun Tseng - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0806116-215529.pdf
  • indicate access worldwide
    Date of Submission 2016-09-07

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys