序列及序列二级结构联配问题的若干算法研究

《序列及序列二级结构联配问题的若干算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA硕士学位论文MASTERTHESIS论文题目序列及序列二级结构联配问题的若干算法研究学科专业计算机软件与理论学号201221060349作者姓名张西洋指导教师__________肖鸣宇教授_________独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而

2、使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：改函咩日期：年/月夕厂日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：>/r年/月Zr日分类号密级注1UDC学位论文序列及序列二级结构

3、联配问题的若干算法研究（题名和副题名）张西洋（作者姓名）指导教师肖鸣宇教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士学科专业计算机软件与理论提交论文日期2015.03.27论文答辩日期2015.05.14学位授予单位和日期电子科技大学2015年06月答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。STUDYOFSEVERALALGORITHMSFORALIGNMENTPROBLEMOFSEQUENCEANDSEQUENCESECONDARYSTRUCTUREAMasterThesisSubmitted

4、toUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerSoftwareandTheoryAuthor:XiyangZhangAdvisor:Prof.MingyuXiaoSchool:SchoolofComputerScience&Engineering摘要摘要序列联配以及序列二级结构联配是生物信息处理中最基本最重要的问题。自1970年Needleman和Wunsch提出的经典的动态规划算法以来，如何获得结果准确，时间空间效率更高的序列联配算法和软件一直

5、是生物信息学研究中的一项重要课题。考虑实际序列联配问题中的序列具有较高的相识度，也就是说在最佳联配中各个序列中插入的空格数将不会太大，本文将待插入的空格数上限作为限制来设计序列联配算法，从而降低算法的运行时间和空间的复杂度。Needleman和Wunsch给出的运行时间和空间为Omn()的动态规划算法至今仍然是最为实用和有效的双序列联配算法之一，其中mn,为两条序列的长度。本文在Needleman和Wunsch的动态规划算法的基础上提出了一种在k插缺数限制下双序列联配的算法，其运行时间和空间复杂度都为Okminmn(),

6、。同时，文中将该思想引入Hirschberg线性空间算法中，给出了一种在k插缺数限制下的双序列联配线性空间算法，其运行时间仍然为Okminmn(),，但只使用线性的内存空间。大量实际数据说明一般最佳联配下插入空格数在序列长度的20%以内，因此在实验中，大部分序列将k规定在序列长度的20%，新算法可以将运行时间直接减少近50%的情况下仍然保证找到最优解，对于部分相似度高的序列，甚至可以将运行时间直接减少近85%的情况下仍然保证找到最优解。接下来，文中将参数k的思想应用到三条序列联配算法中，设计了在k插缺2数限制下三条序列联配

7、的算法，时间复杂度和空间复杂度都为Okn()，其中k为参数表示允许插入的最大空格数，三条序列长度均为n。在多序列联配问题中由于序列数量增加而导致计算难度陡增，引入参数k的概念也不能获得实际有效的算法。因此本文给出一种基于双序列联配的快速多序列联配启发式算法。然后以BAliBASE数据库来测试与其他算法比较，实验也验证我们的算法明显比之前的算法的准确性更好。对序列二级结构联配问题，文中同样经典的Bafna算法中引入参数k的概念。322将原本时间和空间复杂度都为Omnmn()的算法改进为时间和空间复杂度都222为Okmn()k

8、n的算法，其中mn、为两条序列长度，k是序列中允许插入的111最大空格数。最后本文总结了引入参数k的概念的序列联配及序列二级结构联配问题的研究结果，并对相关工作的未来的研究方向做了展望及提出了一些问题可能的解决方法。关键词：序列联配，多序列联配，动态规划，分治算