探索motif finding及其closest string相关问题的算法研究

《探索motif finding及其closest string相关问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南大学硕士学位论文MotifFinding及其ClosestString相关问题的算法研究姓名：王丽申请学位级别：硕士专业：交通信息工程及控制指导教师：张祖平20070510摘要生物信息学(又称生物计算学)是一门生物学与计算机科学以及应用数学等学科相互交叉而形成的一门新兴学科，其主要任务是揭示海量生物学数据中蕴含的生物学意义、探索生命活动的奥秘。MotifFinding和ClosestString问题都是生物计算中基础而重要的研究问题，在很多领域得到了广泛的应用，甚至生物计算以外的编码理论。近年来这两个问题得到了广泛的研究，如何应用最新的研究技术，如分布式系统和固定参数理论，为这两

2、个问题提出更好的解决方案是本文研究的重点。论文在深入分析已有算法的基础上，提出了MotifFinding问题的分布式算法，并设计与实现了分布式系统，对问题进行有效求解，实际测试结果表明分布式算法是正确且高效的；综合已有算法的优点，提出了计算广义ClosestString问题最优上界的新方法，对ClosestString问题的下界进行了推导，设计并优化了下界相关算法，弥补了固定参数算法在d较大且不存在结果时运行时间太长的缺憾，为判断在下界是否存在结果和求所有解提供了快速有效的方法。论文对算法的设计思想及实现作了详细的说明，对测试结果也作了深入的分析，实验结果表明这些算法是可行且高效的。

3、关键词生物计算；MotifFinding问题；ClosestString问题；分布式算法；固定参数算法ABSTRACTBioinformatics(computationalbiologyinanotherword)isanewsciencefield．Researchinthisfieldinvolvesmulti-disciplinessuchasbiology,computerscience，appliedmathematics，etc．Computationalbiologyissubjecttoexposethebiologicalsignificationoflargea

4、mountofbiologicaldataandexplorethemysteryoflifeactivities．MotifFindingproblemandClosestStringproblemarebasicandimportantintheresearchofcomputationalbiology,whichfindapplicationsinmanyfields，even，outsidecomputationalbiology,incodingtheory．Bothofthemalewidelyanddeeplystudiedinthelastfewyears，andh

5、owtocreatebettersolutionstrategywithlatestresearchtechnology,suchasdistributedsystemandFixed—Parametertheory,i8thekeypointofthisthesis．Afterthedeepanalysisofexistentalgorithms，thisthesispresentsanewdistributedparameterizedalgorithmtosolveMotifFindingproblem，anddesignofthedistributedsystemcooper

6、atingwiththealgorithmaswell，thenprovesit’Srightandefficientbyanalysingtestresultsonthedistributedsystem；anewstrategy,combiningadvantagesofabranch—and—boundalgorithmandaFixed-Parameteralgorithm，tocomputeoptimalupperboundofgeneralClosestStringproblem；formulaofdeducinglowerboundandthedesignandopti

7、mizationofnewalgorithmsonlowerbound．ThealgorithmscomplementtheconsumingtoomuchtimedisadvantageoftheFixed-Parameteralgorithmwhendisalittlelargerandthereisnosolution,andaresuitabletocheckwhetherthereexistssolutiononthelowerboundandc