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

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

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