Title page for etd-0022117-230149


[Back to Results | New Search]

URN etd-0022117-230149
Author Tzu-Chiang Hsu
Author's Email Address No Public.
Statistics This thesis had been viewed 5352 times. Download 243 times.
Department Computer Science and Engineering
Year 2016
Semester 1
Degree Master
Type of Document
Language English
Title An Algorithm for Computing the Distance of the Non-overlapping Inversion and Transposition
Date of Defense 2017-01-16
Page Count 47
Keyword
  • Non-Overlapping
  • Genome Rearrangement
  • Inversion
  • Transposition
  • Dynamic Programming
  • Run
  • Abstract Reacting to the growing interest in large-scale mutation events, Ta et al. introduced the non-overlapping inversion and transposition distance problem in 2015, which is to calculate the mutation distance between two strings of the same length n. The allowed operations include non-overlapping inversions and transpositions. They presented an algorithm with O(n^3) time. In this thesis, we propose an efficient algorithm to solve the same problem in O(n^2) time. Our algorithm depends on a strong connection between the non-overlapping transposition and the run structure.
    Advisory Committee
  • Yi-Hsing Chang - chair
  • Hsing-Yen Ann - co-chair
  • Kuo-Tsung Tseng - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0022117-230149.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2017-01-24

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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