| 摘要: | Motif Finding 這個問題引起許多人的興趣，因此也造就了許多搜尋演算法的產生。然而許多的演算法在面對Pevnzer 和 Sze所提出的Challenge Problem無法得到一個非常好的結果。而本研究主要目的是利用自行構思的詳盡式搜尋來解決Motif finding的問題，嘗試突破PROJECTION在搜尋(9,2)、(11,3)、(13,4)、(15,5)、(17,6)等信號其結果不佳的問題，以及解決當序列長度(N)增加時所造成搜尋motif執行效率和準確度下降等問題。 一般人認為詳盡搜尋的方式雖然可以準確的找到motif，但是當基因序列和搜尋的motif長度過長的時候，在運算時間容易呈指數的倍數成長，因此本研究透過一些輔助的技巧可以避免因長度的增加使得運算時間的增長，又能夠兼顧效率及精準的方式來找到最好的結果。可以預期的是此方式可以得到不錯的結果外，在方法上更可擴展到其他motif相關的研究領域上。; Recently, motif finding became a very popular area in bioinformatics, thus more and more researches are interested in discover motif. However, many algorithms can not solve the Pevnzer and Szes’ challenge problem. It motivates my algorithm to purpose construct an exhaustive method to improve the motif finding performance in discover signals such as: (9,2),(11,3),(13,4),(15,5), and (17,6) and to solve the problem that accuracy will be descending while sequence length is increasing. Although exhaustive search method could find motifs accuracy, it still needs to face the problem that computing time will be grown exponentially by length increasing of genomic sequence and motif. The research through provide assist skills not only to avoid the length of sequence increasing effect computing time, but also efficiency and accuracy to discover the optimal result. We could expect the research will bring well performance and apply in other bioinformatics domain related motif finding is expandable. |
