請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74234
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂 | |
dc.contributor.author | Yin-Chu Chen | en |
dc.contributor.author | 陳胤竹 | zh_TW |
dc.date.accessioned | 2021-06-17T08:25:34Z | - |
dc.date.available | 2024-08-18 | |
dc.date.copyright | 2019-08-18 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-08-12 | |
dc.identifier.citation | [1] M. Dumitran and F. Manea. Longest gapped repeats and palindromes. In International Symposium on Mathematical Foundations of Computer Science, pages 205–217. Springer, 2015.
[2] J. Fischer. Optimal succinctness for range minimum queries. In Latin American Symposium on Theoretical Informatics, pages 158–169. Springer, 2010. [3] T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longest-commonprefix computation in suffix arrays and its applications. In Annual Symposium on Combinatorial Pattern Matching, pages 181–192. Springer, 2001. [4] R. Kolpakov and G. Kucherov. Searching for gapped palindromes. Theoretical Computer Science, 410(51):5365–5373, 2009. [5] R. Kolpakov, M. Podolskiy, M. Posypkin, and N. Khrapov. Searching of gapped repeats and subrepetitions in a word. Journal of Discrete Algorithms, 46:1–15, 2017. [6] G. Manacher. A new linear-time on-line algorithm for finding the smallest initial palindrome of a string. Journal of the ACM (JACM), 22(3):346–351, 1975. [7] U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. siam Journal on Computing, 22(5):935–948, 1993. [8] F. Zhang, Y. Wen, and X. Guo. CRISPR/Cas9 for genome editing: progress, implications and challenges. Human Molecular Genetics, 23(R1):R40–R46, 2014. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74234 | - |
dc.description.abstract | 回文序列廣泛存在於基因序列中,重複回文也不例外。因此,在本篇論文中討論了兩個和找尋特殊回文相關的演算法。其一是尋找給定序列中的重複回文,意即找尋出現次數超過一次的回文子序列。其中,我們能對尋找序列的出現次數和長度作為篩選條件。其二是找尋k次不匹配回文。k次不匹配回文是指一個子字串經由k個字母的修改之後可以變成一個回文。這個可以應用在生物序列中有點突變的回文尋找上。
兩個演算法都應用在後綴陣列和最長共同字首陣列之上,這也是本篇論文獨特之處,使演算法變的有效率,並且讓演算法簡單易懂。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T08:25:34Z (GMT). No. of bitstreams: 1 ntu-108-R06945028-1.pdf: 522254 bytes, checksum: d3c245994424e0eb1cb1ddee2dc8f27c (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 誌謝ii
摘要iii Abstract iv 1 Introduction 1 1.1 Motivation 2 1.2 An overview of this thesis 2 1.3 Related Work 3 1.3.1 Finding longest palindromic substrings 3 1.3.2 Finding repeated substrings 4 2 Preliminaries and Problem Definitions 6 2.1 Definition of problems 6 2.2 Preliminaries 7 2.3 Suffix array 8 2.4 Longest common prefix array (LCP array) 8 3 Finding palindromic repeats 9 3.1 Finding maximal length of palindromic substring from each position 9 3.2 Finding all palindromic repeats 14 4 The K-mismatch Palindrome Problem 18 5 Discussion 21 6 Conclusion 23 Bibliography 25 | |
dc.language.iso | en | |
dc.title | 特殊回文序列搜尋演算法 | zh_TW |
dc.title | An Efficient Algorithm for Finding Special Palindromes | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王弘倫,吳彥緯 | |
dc.subject.keyword | 回文,重複序列,後綴陣列,最長共同字首陣列, | zh_TW |
dc.subject.keyword | palindrome,repeated sequence,suffix array,longest common prefix array, | en |
dc.relation.page | 25 | |
dc.identifier.doi | 10.6342/NTU201903028 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-08-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 生醫電子與資訊學研究所 | zh_TW |
顯示於系所單位: | 生醫電子與資訊學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 510.01 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。