模體發(fā)現(xiàn)中的參考序列選擇問(wèn)題研究.pdf

1、在一組生物序列中，通常會(huì)存在一些含有特定功能的短的序列片段，比如DNA序列中的轉(zhuǎn)錄因子結(jié)合位點(diǎn)。這些序列片段之間比較相似，但并不相同，這樣的序列片段被統(tǒng)稱(chēng)為模體。研究者們一般采用計(jì)算的手段，識(shí)別生物序列中的模體。這類(lèi)求解問(wèn)題就是模體發(fā)現(xiàn)問(wèn)題。在生物信息學(xué)和計(jì)算機(jī)科學(xué)中，模體發(fā)現(xiàn)問(wèn)題都是重要且挑戰(zhàn)性的問(wèn)題。植入(l, d)模體發(fā)現(xiàn)(PMS)問(wèn)題是模體發(fā)現(xiàn)的一種常用的研究形式，自被Keich和Pevzner第一次提出至今，已涌現(xiàn)出來(lái)了許多用

2、于求解植入(l, d)模體發(fā)現(xiàn)問(wèn)題的算法。
　　本研究主要關(guān)注于其中的精確算法，它們通過(guò)遍歷整個(gè)搜索空間能夠找出所有的模體，時(shí)間性能是衡量精確算法的最主要指標(biāo)。研究者一般在模體發(fā)現(xiàn)問(wèn)題的挑戰(zhàn)實(shí)例上比較不同精確算法的時(shí)間性能。在目前對(duì)精確算法的研究中，基于模式驅(qū)動(dòng)的精確算法具有最好的時(shí)間性能，無(wú)論是識(shí)別短模體還是微弱信號(hào)的長(zhǎng)模體。這類(lèi)精確算法的基本思路是用t條輸入序列中的k(1≤k

3、進(jìn)行驗(yàn)證，可以找出輸入序列中所有的(l, d)模體。然而，在選擇序列中的參考序列時(shí)，基于模式驅(qū)動(dòng)的精確算法大多數(shù)都是固定地將輸入序列中的前k條作為參考序列，沒(méi)有考慮不同的參考序列對(duì)算法時(shí)間性能的影響。我們?cè)诒疚牡难芯恐邪l(fā)現(xiàn)，對(duì)于同一組數(shù)據(jù)集，不同的參考序列對(duì)候選模體的數(shù)量存在著影響，特別是對(duì)于大的字符集。因此在實(shí)驗(yàn)中，基于模式驅(qū)動(dòng)的精確算法在應(yīng)對(duì)同等規(guī)模的不同輸入時(shí)，時(shí)間性能有時(shí)會(huì)表現(xiàn)出極大的不穩(wěn)定性。本文建立了模體發(fā)現(xiàn)算法中的參考序列