請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74234
標題: | 特殊回文序列搜尋演算法 An Efficient Algorithm for Finding Special Palindromes |
作者: | Yin-Chu Chen 陳胤竹 |
指導教授: | 趙坤茂 |
關鍵字: | 回文,重複序列,後綴陣列,最長共同字首陣列, palindrome,repeated sequence,suffix array,longest common prefix array, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 回文序列廣泛存在於基因序列中,重複回文也不例外。因此,在本篇論文中討論了兩個和找尋特殊回文相關的演算法。其一是尋找給定序列中的重複回文,意即找尋出現次數超過一次的回文子序列。其中,我們能對尋找序列的出現次數和長度作為篩選條件。其二是找尋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 |
全文授權: | 有償授權 |
顯示於系所單位: | 生醫電子與資訊學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 510.01 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。