生物序列模式发现算法的研究

《生物序列模式发现算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西安电子科技大学硕士学位论文生物序列模式发现算法的研究姓名：赵丽华申请学位级别：硕士专业：计算机应用技术指导教师：高琳20070101摘要20世纪90年代以来，生命科学研究取得了突破性的进展，随着人类基因组计划的开展与现代生物技术的发展，人类积累的大量的生物信息数据为揭开生命奥秘提供了数据基础。而怎样从海量的生物数据中提炼出有用的生物学知识，弄清楚他们所蕴涵的结构和功能信息，是目前生物信息学领域中的一个重要的研究方向。模式发现技术正是揭示生物序列数据中所蕴涵的生物学意义的基本方法之一，它通过寻找不同序列间的相似片段来归结出这些序列片段中所蕴涵的特征模式。近年来，在模式发现的算法研究方面

2、，人们已经探索出了一些有效的算法，这些算法在解决较小规模的生物序列模式发现问题时都表现出了良好的性能。但是，随着数据规模的不断扩大，很多算法都己无法适应问题的需要。所以，积极探索更加有效的模式发现算法已成为目前生物序列模式发现研究领域中的重大课题，并受到越来越广泛的关注。本文首先对在模式发现算法中所常用的模式模型进行了分析，并且对基于不同模式模型的模式发现算法进行了研究和分析；然后在分析已有的序列模式发现算法的基础上，又提出了一种基于图的模式发现算法，该算法首先通过一些约束条件将生物序列数据集转化为一系列的子图，假如数据集中存在某一个模式，那么模式实例必然可以通过子图中某个团的节点来表

3、示，然后在这些子图中查找有效团，并从有效团中恢复出模式的一致序列。通过对算法进行的理论分析和仿真试验研究表明，它能够很好得发现序列中所蕴涵的模式。关键词：模式发现序列图算法AbstractSinccthe90’sinthe2叫lcentury，thercisa黟eatbrcakthroughilIthepm伊e鼹oflifesciencercscarch．w“hthebe酉衄ingoftlleHumanGenomeP加jed锄dthedcvelopmentofmodembiotcchnology，peopleaccIlmulatealotofdataaboutbiolo酉calinfo

4、帆atioll'whichprovidefoundati∞forcxploringthelifcsecrcty．But，howt0extmdu∞fIIlbiolo舀calknowledgefmmmassivebiol呼caldata柚dclarifythestmctu坤柚dfIlndionhjdedinthcmis姐impOnamrcsearchfieldiIlbiojnfbnllatics．1nhemotifdis∞ve『ytcchnologyisexactlyoneofthebasicmetllodswhich托Vealthebjologicalme锄inghidedinthese

5、quencc．n莎tsthechafacIeristicmotifhidcdintIle∞quenccbyfindingthesimilarsegmeminthedif￡efent辩quences．hrecentyca瑙，peopleh弱pfescntedsomee侬埘ivealgoritllIIIsinmestlldyofmotifdi咖er)，algofitllIns，lhesealgorithmshaveshOwnabcttcrpedo眦柚ccin∞lVingthemotifdisc0Verypmblems岫defsmalldatascale．HOwcver，alongwitht

6、heexpansi吨Ofthedatascale，m卸yalgorithms啪not∞lvethemotifdi洲eryproblemsinthisca∞．so，stIldyingmorceffcctivealgorithmsformotifdis∞VeryilIlaFgcscaleh嬲bccome锄ilIIpon卸t哦乒oninthebio∞quenccre∞archalldattractcdmo比卸dmorcattentio璐inthewodd．hlthisthesis，wefirsnyfcview山emotifmodelswhicharcusedindi拖remkindsofmo

7、tifdiscoVcryalg嘶thn坞．砧so，westudy蛳d咖p盯cthemotifdiscoVefyalgorithmsbascd∞di虢rentmodels．Thcnwepfes％t锄appmachformotifdisooveryba∞donthegraphtlleory．The印proachconVensthc∞quenccsdatab舔etoaser{esofsub．舯phundersomefestrictions．Ifthe