Motif Finding及其Closest String相關(guān)問題的算法研究.pdf

1、生物信息學(xué)(又稱生物計(jì)算學(xué))是一門生物學(xué)與計(jì)算機(jī)科學(xué)以及應(yīng)用數(shù)學(xué)等學(xué)科相互交叉而形成的一門新興學(xué)科，其主要任務(wù)是揭示海量生物學(xué)數(shù)據(jù)中蘊(yùn)含的生物學(xué)意義、探索生命活動(dòng)的奧秘。MotifFinding和Closest String問題都是生物計(jì)算中基礎(chǔ)而重要的研究問題，在很多領(lǐng)域得到了廣泛的應(yīng)用，甚至生物計(jì)算以外的編碼理論。近年來這兩個(gè)問題得到了廣泛的研究，如何應(yīng)用最新的研究技術(shù)，如分布式系統(tǒng)和固定參數(shù)理論，為這兩個(gè)問題提出更好的解決方案是本

2、文研究的重點(diǎn)。 論文在深入分析已有算法的基礎(chǔ)上，提出了MotifFinding問題的分布式算法，并設(shè)計(jì)與實(shí)現(xiàn)了分布式系統(tǒng)，對問題進(jìn)行有效求解，實(shí)際測試結(jié)果表明分布式算法是正確且高效的；綜合已有算法的優(yōu)點(diǎn)，提出了計(jì)算廣義Closest String問題最優(yōu)上界的新方法，對ClosestString問題的下界進(jìn)行了推導(dǎo)，設(shè)計(jì)并優(yōu)化了下界相關(guān)算法，彌補(bǔ)了固定參數(shù)算法在d較大且不存在結(jié)果時(shí)運(yùn)行時(shí)間太長的缺憾，為判斷在下界是否存在結(jié)果和求