(3.230.173.249) 您好!臺灣時間:2021/04/21 02:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:潘世璋
研究生(外文):Pan Shih Chang
論文名稱:使用字尾樹解決迴文偵測問題
論文名稱(外文):Solving the Palindrome Detection Problem Based upon Suffix Trees
指導教授:李家同李家同引用關係
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:生物醫學科技研究所
學門:醫藥衛生學門
學類:醫學技術及檢驗學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:32
中文關鍵詞: 字尾樹 迴文
外文關鍵詞:PalindromeSuffix Tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:146
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
給定一字串 , 被稱為字串 的倒轉。 是ㄧ個非空的字串。字串 被稱為精確迴文,而字串 被稱為間隔迴文。我們這篇論文要解決的問題定義如下:給定一長度為 的字串 ,找尋在字串 中所有的精確迴文及間隔迴文。
  在這篇論文中,我們提出一個基於字尾樹的演算法來解決這個迴文找尋問題。以下是我們演算法的描述:ㄧ開始,我們反轉給定的字串 ,並稱這新的字串為 。我們為這兩字串 及 建造ㄧ字尾數。我們在這字尾數上標定前收集,後收集和 之後,我們提出兩公式來找尋迴文。使用第一個公式 ,我們將找出精確迴文。近一步地,我們使用第二個公式 來找尋間隔迴文。這兩公式是幫助我們解決這迴文找尋問題的主要技巧。
Given a string , is called the reverse of is a non-empty string. The string is called an exact palindrome and the string is called a gaped palindrome. The problem of the thesis is defined as follows: Given a string of length , find all exact and gaped palindromes in .
In the thesis, we propose an algorithm based on suffix trees to solve the problem. The algorithm is described as follows. At the beginning, we reverse the given string and denote the new string as . We construct the suffix tree for and . After labeling the forward collections, backward collections and s on the constructed suffix tree, we propose two formulas to find palindromes. By using the first formula , we will find all exact palindromes. Furthermore, we can find all gaped palindromes by using second formula . The two formulas are the main tricks for helping us to solve the problem.
List of Figures v
List of Tables vi
Chapter 1 Introduction 1-1
1.1 Motivations and Previous Works 1-1
1.2 Thesis Organization 1-2
Chapter 2 Manacher Algorithm 2-1
2.1 The Brute Force Algorithm 2-1
2.2 The Manacher Algorithm 2-3
2.3 A Full Example of Manacher Algorithm 2-7
Chapter 3 Solving the Palindrome Detection Problem Based upon Suffix Trees 3-1
3.1 Term Definitions 3-1
3.2 Finding Exact Palindromes 3-6
3.3 Finding Gaped Palindromes 3-10
3.4 Full Example for Finding All Palindromes 3-17
Chapter 4 Conclusion 4-1
Bibliography 5-1
[A2000] Frequency-Domain Analysis of Biomolecular Sequences, Anastassiou, D., Bioinformatics, Vol. 16, 2000, pp. 1073-1081.
[A2001] Genomic Signal Processing, Anastassiou, D., IEEE Signal Processing Magazine, Vol. 18, 2001, pp. 8-20.
[B2003] Hypermutable Minisatellites, a Human Affair?, Bois, P. R. J., Genomics, Vol. 81, 2003, pp. 349-355.
[B99] Tandem Repeats Finder: a Program to Analyze DNA Sequences, Benson, G., Oxford University Press, Vol. 27, 1999, pp. 573-580.
[BJ2003] Detection and Visualization of Tandem Repeats in DNA Sequences, Buchner, M. and Janjarasjitt, S., IEEE Transactions on Signal Processing, Vol. 51, 2003, pp. 2280-2287.
[BR2003] Comparison of Minisatellites, Berard, S. and Rivals, E., Journal of Computational Biology, Vol. 10, 2003, pp. 357-372.
[C81] An Optimal Algorithm for Computing the Repetitions in a Word, Crochemore, M., Information Processing Letters, Vol. 12, 1981, pp. 244-250.
[CR2003] Jewels of Stringology, Crochemore, M. and Rytter, W., World Scientific Publishing Company, 2003.
[FS98] How Many Squares Can a String Contain?, Fraenkel, A. S. and Simpson, J., Journal of Combinatorial Theory, Vol. 82, 1998, pp. 112-120.
[G97] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Gusfield, D., Cambridge University Press, 1997.
[GS2004] Linear Time Algorithms for Finding and Representing All the Tandem Repeats in a String, Gusfield, D. and Stoye, J., Journal of Computer and System Sciences, Vol. 69, 2004, pp. 525-546.
[KK99] Finding Maximal Repetitions in a Word in Linear Time, Kolpakov, R. and Kucherov, G., IEEE 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 596-604.
[KMP77] Fast Pattern Matching in Strings, Knuth, D. E., Morris, J. H. and Pratt, V. R., SIAM Journal on Computing, Vol. 6, 1977, pp. 323-350.
[M75] A New linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String, Manacher, G., Journal of the Association for Computing Machinery, 1975.
[M2000] Understanding the Human Genome, Moore, S. K., IEEE Spectrum, Vol. 37, 2000, pp. 33-35.
[ML84] An O(nlogn) Algorithm for Finding All Repetitions in a String, Main, M. and Lorentz, R., Journal of Algorithms, Vol. 5, 1984, pp. 422-432.
[PB2002] Finding Approximate Palindromes in Strings, Porto, A. and Barbosa, V., Pattern Recognition, 2002.
[SG2002] Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree, Stoye, J. and Gusfield, D., Theoretical Computer Science, Vol. 270, 2002, pp. 843-856.
[SS99] Periodicity Transforms, Sethares, W. A. and Staley, T. W., IEEE Transactions on Signal Processing, Vol. 47, 1999, pp. 2953-2964.
[WYKG2004] Finding Approximate Tandem Repeats in Genomic Sequences, Wexler, Y., Yakhini, Z., Kashi, Y. and Geiger, D., Proceedings of the eighth annual international conference on Computational molecular biology, 2004, pp. 223-232.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔