多序列比对优化方法研究

论文题目: 多序列比对优化方法研究

论文类型: 硕士论文

论文专业: 计算机软件与理论

作者: 张鹏帅

导师: 霍红卫

关键词: 生物信息学,多序列比对,遗传算法,粒子群优化算法,目标函数

文献来源: 西安电子科技大学

发表年度: 2005

论文摘要: 序列比对是生物信息学中一项重要的基础性研究课题，它的最基本任务之一是进行多序列比对，目前还没有一个最佳的多序列比对算法。本文提出使用遗传算法和粒子群优化算法来解决多序列比对问题。首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响，具体实现了SP和COFFEE目标函数。然后研究并实现了双序列比对的精确算法--动态规划算法，并对基于渐进方法构建的多序列比对算法-Clustal w进行了深入分析。接着通过对多序列比对算法的现状的研究以及对遗传算法和粒子群优化算法特点等的分析，提出基于遗传算法的多序列比对算法MSAGA(a Genetic Algorithm dedicated for Multiple SequenceAlignments)和基于粒子群优化算法的多序列比对算法MSAPSO(a Particle SwarmOptimization dedicated for Multiple Sequence Alignments)，并分别实现了基于SP和COFFEE目标函数的MSAGA和MSAPSO，两种算法复杂度都只与进化代数和种群大小有关。最后用基准多序列比对库BAliBASE中的用例对算法进行测试，结果表明MSAGA和MSAPSO算法在解决基因序列比对问题上是有效的。

论文目录:

摘要

Abstract

第一章绪论

1．1 背景及意义

1．2 研究现状

1．3 论文主要工作及安排

第二章序列分析基础

2．1 概论

2．2 空位罚分与相似性计分矩阵

2．2．1 空位罚分

2．2．2 替换矩阵

2．3 目标函数

2．3．1 背景介绍

2．3．2 SP目标函数

2．3．3 COFFEE目标函数

2．4 双序列比对

2．5 多序列比对

2．6 本章小结

第三章经典序列比对法

3．1 研究现状

3．2 动态规划算法

3．3 Clustal W算法

3．4 本章小节

第四章基于遗传算法的多序列比对算法

4．1 遗传算法的基本原理

4．2 基于遗传算法的多序列比对优化算法

4．2．1 MSAGA算法设计

4．2．2 基于SP目标函数的MSAGA实验结果

4．2．3 基于COFFEE目标函数的MSAGA实验结果

4．2．4 实验结果性能分析

4．3 本章小结

第五章基于粒子群的多序列比对优化算法

5．1 PSO算法简介

5．1．1 PSO算法现状

5．1．2 PSO算法原理

5．1．3 PSO的特点

5．1．4 SPO算法的参数选择

5．1．5 PSO算法的应用与发展

5．2 基于粒子群算法的多序列比对优化算法

5．2．1 算法描述

5．2．2 算法实现

5．2．3 基于SP目标函数的MSAPSO实验结果

5．2．4 基于COFFEE目标函数的MSAPSO实验结果

5．2．5 实验结果性能分析

5．3 本章小结

第六章算法比较

6．1 GA与PSO的比较

6．2 MSAGA与MSAPSO比较

结束语

附录A 相似性替换矩阵介绍

致谢

参考文献

在校期间科研成果

发布时间: 2005-04-26

参考文献

[1].生物序列比对问题的研究[D]. 吕艳萍.福州大学2005
[2].双序列比对算法研究[D]. 何万双.国防科学技术大学2006
[3].基于种子的序列比对方法研究[D]. 曹金玲.吉林大学2008
[4].基于混合化学反应优化算法的序列比对研究[D]. 黄丹青.湖南大学2014
[5].基于变长种子的找全测序序列比对算法研究及优化[D]. 郭睿东.中国科学技术大学2018
[6].双序列比对Needleman-Wunsch算法研究[D]. 姜鲜桃.内蒙古农业大学2017
[7].双序列比对算法研究与并行优化[D]. 李川.西安电子科技大学2011
[8].生物同源序列比对算法研究及其实现[D]. 纪文娟.江南大学2009
[9].玉米常见病的生物信息学方法研究[D]. 孙启明.吉林农业大学2016
[10].新一代则序技术中的短序列比对和组装算法[D]. 林敏.福建农林大学2011

多序列比对优化方法研究

猜你喜欢