結合演化式策略和完整式搜尋在DNA 序列中尋找有意義的基因片段

Abstract

由於Motif Finding這一類的問題已經出現多時，吸引了許多的人投入這一方面的研究，也提出了許多不同的方法。但是由於這些方法在設計上多半有著一些限制，例如只能用在找尋較短的字串，或是不允許資料中含有雜訊等，使得在應用上面也減少了不少的實用性。雖然在之後也有不少兼具實用性和效能的方法被提出來，但是部份的方法在面對由Pevnzer 和 Sze所提出的The Challenge Problem時卻不法順利而正確的解出答案。而本研究的目的即是針對The Challenge Problem進行研究，使用人工智慧方面的方法來解這一個問題。 雖說使用演化式計算的方法可以對這種需要大量計算的問題，以這種方法的特性來快速的算出答案來，但也因為要求要快速的解出答案，伴隨的就是不甚令人滿意的正確性。而和演化式計算相反的則是完整式搜尋。這種方法可以算出幾進百分之百的正確答案，可是卻要花上上百小時，以及大量的記憶體資源。因而我們嘗試將這兩者結合一起，希望可以融合二者的優點，並改善它們本身的缺點。 而最後研究的結果可說是相當的符合期待，可以在正確性上以及效能上獲得一個不錯的平衡點。而本研究的貢獻就是在結合了兩種不同演算法，並得到一個不錯的結果。此外，由於方法觀念並不複雜，並可以和不同的方法進行搭配，進而改進雙方面的成果。

Motif finding is a fundamental problem in Bioinformatics, and have been investigated for the last decade. Several algorithms for finding motif have been developed, but most of them were restricted in solving special types of motif finding problems. Therefore, those algorithms might fail while the DNA sequences length increasing, motif length increasing or noise increasing. Pevnzer and Sze defined a problem named the Challenge Problem. They used this problem to test the existing motif finding algorithms and found that most algorithms can not effectively solve the Challenge problem. This thesis proposes a novel approach, which synthesize evolutionary strategy and exhausted search, to solve the Challenge Problem. In this thesis, we tested the algorithm with the Challenge Problem. The experimental results indicate that the proposed approach have the advantages both on efficiency and solving this problem correctly. Furthermore, the proposed approach can also be easily extended to other motif finding problems.