以BWT建立方式解決最大重複子字串問題

在這篇論文中，我們對於以Burrows-Wheeler Transform (簡稱BWT) 來解決字串比對問題有相當大的興趣，使用BWT的問題在於為某個字串產生出BWT非常耗費時間，我們的方法是以KSS的方法為基礎來修改並產生出BWT。我們的方法較KSS更簡單理解並實作，而且我們的實驗結果也顯示出我們產生出BWT的方法相當有效率。同時，我們也對最大重複子字串的問題感到相當大的興趣，也依照我們產生出BWT的方法稍做修改之後並利用到解決此問題上，舉例來說，我們的實驗裡，有一串長度為155606181個字的DNA序列，在這麼長的序列中找到長度大於2000的重複子字串只花了我們226秒，我們也成功找出了55對最大重複子字串。

關鍵字

最大重複子字串；字串比對

並列摘要

In this thesis, we are interested in the Burrows-Wheeler Transform (BWT for short) for exact string matching. The problem of BWT is that it is very time-consuming to construct BWT. We have developed a method which is based upon the KSS Method to construct BWT. Our method is quite easy to comprehend and implement. Experimental results show that our method is efficient. We are also interested in the maximal repeating group problem. We have developed an efficient method to find maximal repeating groups. For example, for a DNA sequence with length 155606181, it took only 226 seconds to find 55 maximal repeating groups with lengths longer than 2000.

並列關鍵字

BWT ； Maximal Repeating Groups ； Exact String Matching

參考文獻

[ARM16] The 3D Folding of Metazoan Genomes Correlates with the Association of Similar Repetitive Elements, Cournac, A., Koszul, R., Mozziconacci, J., Nucleic Acids Research, 2016.

[BM77] Boyer, R. S. and Moore, J. S., A Fast String Searching Algorithm, Communications of ACM, Vol. 20, No. 10, 1977, p.p. 762–772.

[FM2000] Ferragina P. and Manzini G., Opportunistic data structures with applications. Proceedings of the 41st Symposium on Foundations of Computer Science, 2000.

[H2012] Hou, K. W., The Discrete Convolution Method on Solving the Exact String Matching Problem, MS Thesis, 2012, Department of Electrical Engineering, National Tsing Hua University, Hsinchu, Taiwan.

[H75] A Linear Space Algorithm for Computing Maximal Common Subsequences, Hirschberg, D. S., Communications of the ACM, Vol. 18, No. 6, 1975, pp. 341-343.

國際替代計量

以BWT建立方式解決最大重複子字串問題

全文下載

主題瀏覽