Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74234
Title: | 特殊回文序列搜尋演算法 An Efficient Algorithm for Finding Special Palindromes |
Authors: | Yin-Chu Chen 陳胤竹 |
Advisor: | 趙坤茂 |
Keyword: | 回文,重複序列,後綴陣列,最長共同字首陣列, palindrome,repeated sequence,suffix array,longest common prefix array, |
Publication Year : | 2019 |
Degree: | 碩士 |
Abstract: | 回文序列廣泛存在於基因序列中,重複回文也不例外。因此,在本篇論文中討論了兩個和找尋特殊回文相關的演算法。其一是尋找給定序列中的重複回文,意即找尋出現次數超過一次的回文子序列。其中,我們能對尋找序列的出現次數和長度作為篩選條件。其二是找尋k次不匹配回文。k次不匹配回文是指一個子字串經由k個字母的修改之後可以變成一個回文。這個可以應用在生物序列中有點突變的回文尋找上。
兩個演算法都應用在後綴陣列和最長共同字首陣列之上,這也是本篇論文獨特之處,使演算法變的有效率,並且讓演算法簡單易懂。 The palindrome sequence is widely found in genomic sequences, including palindromic repeats. In this thesis, we provide two algorithms, one for finding palindromic repeats and the other for finding k-mismatch palindromes. In finding palindromic repeats algorithm, we can find all palindromic substrings which appear at least twice with length and frequency constraint efficiently. In k-mismatch problem, we can find substrings which can become palindromes by k characters’ modification. Both algorithms are based on suffix array and longest common prefix array. This is a novel combination and makes the algorithms more efficient and easily to understand. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74234 |
DOI: | 10.6342/NTU201903028 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 生醫電子與資訊學研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-108-1.pdf Restricted Access | 510.01 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.