以混合0-1變數線性規劃方法尋找基因轉錄因子結合位點

Abstract

基因轉錄因子結合位點 (Transcription factor binding site, TFBS) 的搜尋在基因組的功能性分析上扮演關鍵性的角色。在眾多搜尋方法之中，以共同序列(consensus sequence)為基礎的窮舉法相對最為準確，但其指數成長的運算量卻讓這類方法無法搜尋較長的序列。藉由預先給定的樣版來輔助搜尋能顯著地減少運算量，只是這類資訊較難以取得，也因此目前TFBS的搜尋大多仍仰賴準確率低但速度較快的啟發式方法。 為了能有效準確搜尋TFBS，本研究發展一套混合0-1線性規劃法來求解三種不同類型的TFBS搜尋問題。這包括固定樣版TFBS搜尋，模糊樣版TFBS搜尋，以及無樣版TFBS搜尋。本方法的優點包括：(1)以共同序列為基礎的設計，(2)可得到全域最佳解，以及(3)可套用結構性的限制以加速運算並提高準確率。而在無樣版TFBS搜尋中，本方法更可以成功找到因結構鬆散而難以發現的TFBS。本研究以多個範例來針對三種不同類型的TFBS搜尋問題進行一系列實驗，也都在可接受的時間下成功找到了實際存在的TFBS。

The discrimination of transcription factor binding sites (TFBS) in multiple DNA sequences is an essential work for function analysis of gene expression. Enumeration methods that search all possible patterns have best precision among all current algorithms but require an exponential computational time and have difficulties to search for longer patterns. A predefined shared pattern can notably prunes the searching space but such information is often unavailable. Finding unframed TFBS today still relies on heuristic approaches which compromise to accuracy. To effectively find TFBS, this study develops a mixed 0-1 linear programming approach to solve a series of problems for issues including fixed-pattern TFBS finding, ambiguous spacer TFBS finding and pattern-free TFBS finding. The proposed method has the following advantages over current methods: (1) A pattern-driven instead of sample-driven (or sequence-driven) design; (2) A global optimal solution is promised; (3) Structural features of motifs are embeddable to help facilitate search process. And with pattern-free approaches we can successfully determine TFBS within dispersed spacers. We apply several experiments on every kind of TFBS finding programs and in these examples the real TFBS are successfully determined in an acceptable computational time.