生物信息学中序列比较的一些问题及其算法

摘要

序列比较是生物信息学研究中一类重要的、基础的问题,通过序列比较可以挖掘序列相似性、物种同源性等等重要的生物信息.生物信息学中的序列比较问题实质上体现为字符串比较的问题,已经证明了许多该类问题都是组合优化NP难问题,同时由于生物信息学中的问题规模一般较大,因而要是能够找到快速、有效的算法解决序列比较的问题,将有力的推动生物信息学的发展,同时给其他组合优化NP难问题提供解决思路.

目录

文摘

英文文摘

华南理工大学学位论文原创性声明及学位论文版权使用授权书

第一章绪论

1.1课题背景

1.1.1生物信息与生物信息学

1.1.2生物信息学的现状与发展

1.2生物序列比较

1.2.1两序列比较

1.2.2多序列比较

1.3本文的研究内容及组织

第二章序列联配问题与算法

2.1生物信息学数据库

2.1.1基因与基因组数据库

2.1.2蛋白质数据库

2.1.3功能数据库

2.2序列联配问题

2.2.1序列联配问题描述

2.2.2序列联配算法

2.2.3多序列联配问题的算法

2.3序列联配问题的上界

2.4本章小结

第三章模拟进化过程的进化算法

3.1生物进化过程

3.2模拟进化算法

3.3遗传算法

3.4演化计算解决组合优化难题、NP难问题的优点

3.5本章小结

4.1 Closest String问题描述

4.2 LCRA算法

4.2.1 LCRA算法执行步骤

4.2.2算法分析

4.3 LCRA算法实践及其与遗传算法求解的对比

4.3.1遗传算法设计

4.3.2结果对比

4.3.3实验结果分析

4.4概率矩阵演化算法

4.4.1概率矩阵演化算法过程

4.4.2算法的分析与证明

4.4.3算法实践与结果分析

4.5本章小结

第五章Sub Closest String问题

5.1 Sub Closest String问题的描述

5.1.1 Sub Closest String的算法选择

5.2 Sub Closest String问题的遗传算法设计

5.2.1问题基于进制的编、解码

5.2.2适应函数

5.2.3选择算子设计

5.2.4交叉算子的设计

5.2.5变异算子的设计

5.2.6各种参数的选择

5.2.7算法流程图

5.3面向对象的C++对象设计与算法实现

5.3.1实验结果分析

5.4本章小结

结论

参考文献

攻读学位期间发表论文

致谢