论文部分内容阅读
系统发生分析领域的多序列比对和系统发生树构建等问题都是NP-难问题。本文针对这些问题,对蚁群算法进行性能改进及参数分析,提出两种改进蚁群算法;并基于蚁群算法提出两种多序列比对方法和四种系统发生树构建方法,为系统发生分析研究提供了良好的算法工具,也为该领域的研究提供了一种新思路。
本文首先引入免疫选择、免疫记忆、免疫代谢、浓度控制操作及小生境技术,提出基于免疫机制的小生境蚁群算法,加快了算法收敛速度的同时解决了早熟停滞问题;进而,提出求解多目标优化问题的超蚂蚁种群参数自适应算法,利用不同蚂蚁种群的信息量调控不同类型的目标指标要求,既考虑单个目标指标的个别特性,又考虑不同目标指标之间的相互影响,另外还自适应调整算法中参数的配置,提高蚁群算法性能的同时也发现各项参数取值具有规律性:针对特定问题在合适范围内调整不同参数取值,可有效提高算法性能,从而在解的质量、多样性及收敛速度之间取得较好平衡。
本文后续研究工作也证明,上述两种算法解决了传统算法容易陷入局部最优造成早熟停滞现象的问题,简化了传统蚁群算法的参数调节过程,加深了本文在旅行商(TSP)、多目标优化问题领域的研究,使本文不但可以借鉴求解TSP问题的成功经验,将系统发生分析问题转化为TSP问题或其类似问题,计算基因序列间的相似度进行多序列比对并构建系统发生树,还可以利用蚁群算法作为群体优化策略对系统发生分析过程进行全局优化。
生物序列通常较长,针对传统算法对长序列进行多序列比对效果一般不理想的问题,本文提出基于分治、剪枝策略的蚁群多序列比对算法:划分蚂蚁种群将较长序列分段成若干短序列,超蚂蚁种群求解各个短序列比对,并组装每个短序列比对形成原始序列的多序列比对。算法根据超蚂蚁各自内部不同蚂蚁的信息量及所有蚂蚁的整体信息量、字符间的匹配程度、位置等信息搜索序列中与基准序列匹配的字符,运用剪枝策略有效剔除部分非优解缩小问题求解规模,比较适合求解较长序列的多序列比对问题。
在求解多序列比对问题的大部分算法中,算法求解过程早期形成的错误一般在后期很难得到纠正。针对此问题,本文提出星形渐进多序列比对蚁群算法:利用超蚂蚁种群计算所有序列两两比对的选择概率和某一序列被选为核心序列的核心概率,选取若干个较优序列分别作为核心序列,将其他所有序列与核心序列的两两比对合并得到若干组多序列比对。算法不但考虑直接选择序列提供的相关信息,还考虑所有其它序列提供的一致性参考信息,有效预防了超蚂蚁种群搜索过程早期比对不一致的发生,增加了找到最优比对的搜索空间和概率,可以找到比一般渐进方法更准确的比对且不影响计算时间。
受蚁群算法在TSP问题中应用的启发,本文将待研究的物种、物种之间的距离分别看作TSP问题的城市及城市之间的边的长度,建立带权完全图,基于蚁群算法提出四种构建系统发生树的方法:(1)基于哈密顿回路,将系统发生树构建问题转化为TSP问题,通过人工蚂蚁搜索哈密顿回路得到一条最优路径和若干较优路径,生成物种进化的一组线性序列从而构建一组系统发生树;(2)基于蚁群聚类思想,人工蚂蚁遍历图建立信息量正反馈系统,完成遍历后删除信息量浓度低于阀值的边,得到更新后图的各个强连通分量构成若干聚类,合并这些聚类为两个差别最大的聚类作为根节点的两个孩子节点,对孩子节点构成的图继续遍历生成新的孩子节点逐步构建系统发生树;(3)基于划分思想,将给定基因序列集合划分为内部序列具有极大相似性、且不同类之间序列具有极大差异性的两个类作为根节点的两个孩子节点;自适应更新孩子节点的类中心优化孩子节点,并对孩子节点进一步递归划分构建系统发生树,直至每个类中只有一个基因序列为止;(4)基于字符串组成信息,利用基准序列中可变长度的字符串组成信息在其他序列中出现的频率和蚁群信息量反馈系统,确定序列间的相似性概率,基于原始序列生成一组聚类方案,选取具有最远距离的两个聚类的方案作为当前根节点的孩子节点,然后对孩子节点分别执行相同操作,从根节点到叶节点自上而下构建系统发生树。
上述四种系统发生树构建方法在多种不同数据集上进行的测试结果,及与NJ、FITCH、CCVP和遗传算法等方法、NCBI标准分类树进行的比较结果证明,它们能够在不影响甚至是更节约计算时间的前提下,构建出更准确、更符合进化历史的最优系统发生树。